I am working through Probability and Random Processes by Geoffrey Grimmett and David Stirzaker, and got stumped following their proof concerning the law of averages. I will start by posting the proof with the tagged equations, and my questions at the end.

We think of $A_i$ as being the event 'that A occurs on the $i$th experiment. We write $S_n = \sum_{i=1}^n I_{A_i}$, the sum of indicator functions of $A_1, A_2,\ldots, A_n$.

We want to proof the following theorem:

It is the case that $n^{-1}S_n$ converges to p as n $\rightarrow \infty$ in the sense that, for all $\epsilon > 0$,

$$\mathbb P(p - \epsilon \leq n^{-1}S_n \leq p + \epsilon) \rightarrow 1 \text{ as } n \rightarrow \infty \tag{1} $$

The proof begins by presuming an experiment where a coin is tossed repeatedly, and heads occurs on each toss with probability $p$. It is obvious then that the random variable $S_n$ has the same probability distribution as the number $H_n$ of heads which occur during the first n tosses i.e. $\mathbb{P}(S_n = k) = \mathbb{P}(H_n = k)$. It therefore follows that

$$\mathbb{P}(\frac{1}{n}S_n \geq p + \epsilon) = \sum_{k \geq n(p+\epsilon)}\mathbb{P}(H_n = k) \tag{2}$$


$$\mathbb{P}(H_n = k) = {n \choose k} p^k (1-p)^{n-k}, \; \text{for} \; 0 \leq k \leq n \tag{3} $$

we get

$$\mathbb{P}(\frac{1}{n}S_n \geq p + \epsilon) = \sum_{k=m}^n {n \choose k} p^k (1-p)^{n-k}, \; \text{where} \; m = \lceil n(p + \epsilon) \rceil \tag{4}$$

Letting $\lambda > 0$, noting that $e^{\lambda k} \geq e^{\lambda n(p + \epsilon)}$ if $k > m$ and writing $q = 1 - p$, we have

\begin{align*} \mathbb{P}(\frac{1}{n}S_n \geq p + \epsilon) &\leq \sum_{k=m}^n e^{\lambda[k-n(p+\epsilon]}{n \choose k} p^k q^{n-k} \tag{5} \\ &\leq e^{-\lambda n \epsilon} \sum_{k=0}^n {n \choose k} (pe^{\lambda q})^k (qe^{-\lambda p})^{n-k} \tag{6} \\ &= e^{-\lambda n \epsilon}(pe^{\lambda q} + qe^{-\lambda p})^n \tag{7} \end{align*}

where the last step is obtained using the binomial theorem.

Then, using the inequality $e^x \leq x + e^{x^2}$, we get

\begin{align*} \mathbb{P}(\frac{1}{n}S_n \geq p + \epsilon) &\leq e^{-\lambda n \epsilon}[pe^{\lambda^2 q^2} + qe^{\lambda^2 p^2}]^n \tag {8}\\ &\leq e^{\lambda^2 n - \lambda n \epsilon} \tag{9} \end{align*}

Picking $\lambda$ to minimize the right-hand side, we get

$$ \mathbb{P}(\frac{1}{n} S_n \geq p + \epsilon) \leq e^{-\frac{1}{4} n \epsilon^2} \; \text{for} \; \epsilon > 0 \tag{10} $$

It follows immediately that $\mathbb{P}(n^{-1} S_n \leq p + \epsilon) \rightarrow 0$ as $n \rightarrow \infty$, and using a similar argument as above, that $\mathbb{P}(n^{-1} S_n \leq p - \epsilon) \rightarrow 0$ as $n \rightarrow \infty$, and thus the theorem is proved.

My questions are as follows:

  1. In order to get from equation (5) to equation (6), it's just a matter of upper-bounding $\sum_{k=m}^n$ by $\sum_{k=0}^n$, am I right?

  2. I am clueless as to how we get equations (8) and (9). Could someone shed some light on that?


1 Answer 1


You are correct on question 1. After upper-bounding the sum from $m$ to $n$ with the sum from $0$ to $n$, write $$e^{\lambda(k-np)}=e^{\lambda(p+q)k}e^{-\lambda np}=(e^{\lambda q})^ke^{-\lambda p(n-k)}.$$ On question 2: for (8), apply the inequality with $x=\lambda q$ and a second time with $x=-\lambda p$. Then multiply the first result through by $p$ and the second result through by $q$, and add up.

For (9), simply bound $pe^{\lambda^2 q^2}$ by $pe^{\lambda^2}$, since $q^2\le 1$. Similarly bound $qe^{\lambda^2p^2}$ by $qe^{\lambda ^2}$. Then add up, using $p+q=1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.