I am working through Probability and Random Processes by Geoffrey Grimmet 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?

up vote 2 down vote accepted

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

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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