A problem about the Borel-Cantelli lemma in Feller's Introduction to Probability

Question

The problem is from Chapter 8 of the book, and it states the following.

"In a sequence of Bernoulli trials let $A_n$ be the event that a run of $n$ consecuitive successes ocurrs between the $2^n$th trial and the $2^{n+1}$st trial. If $p \ge \frac{1}{2}$, there is probability one that infinitely many $A_n$ occur; if $p<\frac{1}{2}$, then with probability one, only finitely many $A_n$ ocurr"

I've had several issues when trying to solve this problem, but the most important one is how the book solves this problem:

"Note that $Pr(A_n) < (2p)^n$, but $Pr(A_n) > 1 - (1-p^n)^{\frac{2^n}{2n}} > 1-e^{\frac{(-2p)^n}{2n}}$.

If $p=\frac{1}{2}$ the last quantity is approximately $\frac{n}{2}$; if $p>1$ then $Pr(A_n)$ does not even tend to zero".

Can someone explain the proof that is given? Because it kinda confused me.

Answer 1

We might as well just think about the first $2^n$ successive trials since there's no significance to where they occur in the sequence.

The first inequality is because $A_n$ occurs if trials $t_1, \ldots, t_n$ are all successes, or $t_1, \ldots, t_{n+1}$ are all successes, ..., or $t_{2^n-n+1}, \ldots t_{2^n}$ are all successes. Each of these events has probability $p^n$ and there are slightly under $2^n$ of them, so the probability of $A_n$ is less than $2^n p^n$.

The second inequality is equivalent to saying that the probability of there being no $n$ consecutive successes is $\leq (1-p^n)^{2^n/(2n)}$. If there are no $n$ consecutive successes in the whole of the $2^n$ trials then certainly there are no $n$ consecutive successes in $t_1, \ldots, t_n$ (probability $1-p^n$), or in $t_{n+1}, \ldots, t_{2n}$, or ... Those events are independent, so you can multiply their probabilities to get the result (actually, something stronger: $n$ in the denominator, not $2n$).

Finally $1-x \leq e^{-x}$ so $(1-p^n) \leq e^{-p^n}$ and $(1-p^n)^{2^n/n} \leq e^{-(2p)^n/n}$.

It doesn't make sense to have $p>1$, maybe $p > 1/2$ is meant at the end. The "last quantity" is a lower bound for a probability so it can't be roughly $n/2$ - something is wrong there.

Answer 2

I'm not sure which quantity you mean is approximately $\frac n2$. If $p = \frac 12$, then $1-e^{\frac{(-2p)^n}{2n}} \approx 1$. As pointed out in the comments, there is a sign error and that should really be $1-e^{-\frac{(2p)^n}{2n}}$.

The first inequality comes from the fact that the probability of succeeding $n$ times in a row starting from trial $k$ is $p^n$, and you have fewer than $2^n$ trials to start the streak from (since you need to have completed it by time $2^{n+1}$), so $P(A_n) < 2^n p^n = (2p)^n$.

For the second inequality, let $B_{k,n}$ be the event that there are $n$ successes in a row starting from trial $k$. Then $A_n = \bigcup_{k=2^n}^{2^{n+1}-n} B_{k,n}$, so \begin{align*} P(A_n) = 1-P(A_n^c) = 1-P\left( \bigcap_{k=2^n}^{2^{n+1}-n} B_{k,n}^c\right). \end{align*} The events $B_{k,n}$ and $B_{j,n}$ are independent if $k+n < j$, so instead of looking at the whole intersection we can get an inequality by just looking at the ones that are independent. There are at least $\frac{2^n}{2n}$ independent $B_{k,n}$ events for $2^n \le k \le 2^{n+1}-n$, so $$ P\left( \bigcap_{k=2^n}^{2^{n+1}-n} B_{k,n}^c\right) \le P(B_{k,n}^c)^{\frac{2^n}{2n}} = (1-p^n)^{\frac{2^n}{2n}}$$ and hence \begin{align*} P(A_n) = 1-P(A_n^c) = 1-P\left( \bigcap_{k=2^n}^{2^{n+1}-n} B_{k,n}^c\right) \ge 1- (1-p^n)^{\frac{2^n}{2n}}. \end{align*} The last inequality is just using the fact that $e^{-x} \ge 1-x$ for all $x \in \mathbb{R}$.

And yes, if $p > \frac 12$ then $P(A_n)$ tends to $1$. That makes sense, though: if you are more likely to succeed than not, the chance of you going on an $n$ trial winning streak over the course of $2^n$ events should be almost certain when $n$ is large.