Derivation of law of averages in Grimmett and Stirzaker

Question

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?

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