All Articles

The Weak Law of Large Numbers

Convergence in probability

Below is a brief discussion on the weak law of large numbers, a very standard result in probability. I like the proof because of its brevity. The statement of the theorem is as follows.

Let X1,X2,X_1,X_2,\ldots be a sequence of iid random variables. Define

pn(ϵ):=P(XnX<ϵ).p_n(\epsilon) := \mathrm{P} \big(|X_n - X| < \epsilon\big).

XnX<ϵ|X_n - X| < \epsilon is the event that XnX_n deviates from the random variable XX in magnitude by not more than ϵ\epsilon.

pn(ϵ)p_n(\epsilon) is the probability of such an event.

Let δ(0,1)\delta \in (0,1) and let ϵ>0\epsilon > 0 be given.

Convergence in probability means that there exists an NN such that

n>Npn(ϵ)1δ.n > N \implies p_n(\epsilon) \geq 1 -\delta .

XnX_n is then said to converge to XX _in probability*. This is denoted as

XnpX.X_n \overset{p}{\to} X .

In words, if one wants to permit XnX_n to deviate from XX by less than an ϵ\epsilon-margin with at least [(1δ)100]%[(1-\delta)\cdot 100]\% certainty, there will always exist an N which achieves this for all n>Nn >N (assuming the XnX_n’s are iid).

Let XX be a random variable and let X1,X2,X_1,X_2,\ldots be an infinite sequence of i.i.d. copies of XX. Define

Xn:=i=1nXin.\overline{X_n} := \frac{\sum_{i=1}^n X_i}{n} .

Then,

Xnpμ:=E[X].\overline{X_n} \overset{p}{\to} \mu := \mathrm{E}[X].

The proof

The proof hinges on the well-known tail-bound,

P(h(X)a)Eh(X)a.\mathrm{P} (h(X)\geq a) \leq \frac{\mathrm{E} h(X)}{a} .

Where h0h\geq 0.

Let X=XnX = \overline{X_n} and h(Xn)=(Xnμ)2h(\overline{X_n}) = (\overline{X_n} - \mu)^2 .

Then,

P(Xnμ<ϵ)=P((Xnμ)2<ϵ2)=1P((Xnμ)2ϵ2)1E(Xnμ)2ϵ2=11nσ2ϵ2\begin{aligned} \mathrm{P}\big(|\overline{X_n} - \mu| < \epsilon\big) &= \mathrm{P}\big((\overline{X_n} -\mu)^2 < \epsilon^2\big) \\ &= 1 - \mathrm{P}\big((\overline{X_n} -\mu)^2 \geq \epsilon^2\big)\\ &\geq 1 - \frac{\mathrm{E}(\overline{X_n} - \mu)^2}{\epsilon^2} \\ &= 1 - \frac{1}{n}\cdot \frac{\sigma^2}{\epsilon^2}\end{aligned}

Note the use of the i.i.d. assumption in the penultimate step where VarXn=σ2n\text{Var} \overline{X_n} =\frac{\sigma^2}{n} .

The term

1nσ2ϵ2- \frac{1}{n}\cdot \frac{\sigma^2}{\epsilon^2}

must be bounded below by δ-\delta in order to obtain the desired inequality

11nσ2ϵ21δ.1 - \frac{1}{n}\cdot \frac{\sigma^2}{\epsilon^2} \geq 1- \delta .

The only factor free to be altered is nn and

1nσ2ϵ2δn>σ2ϵ2δ.-\frac{1}{n}\cdot \frac{\sigma^2}{\epsilon^2} \geq - \delta \iff n > \frac{\sigma^2}{\epsilon^2 \delta} .

Application

Operationally then, given ϵ\epsilon, δ\delta, and σ2\sigma^2, the weak law of large numbers tells you how large nn needs to be in order to fall within ϵ\epsilon of XX with probability 1δ1-\delta.

Published 31 May 2018