# Derivation of law of averages in Grimmett and Stirzaker

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}$$

Using

$$\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?

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$.