Tossing a coin with at least $k$ consecutive heads

Toss a coin with $\Pr(\text{Heads})=p$ repeatedly. Let $A_k$ be the event that $k$ or more consecutive heads occurs amongst the tosses numbered $2^k,2^k+1,...,2^{k+1}-1$. Show that, $\Pr(A_k\ i.o.)=1$ if $p\ge\frac12$ and $\Pr(A_k\ i.o.)=0$ if $p<\frac12$

($i.o.$ means infinitely often)

Borel-Cantelli lemma states that, if $A_k$'s are mutually independent then

$\displaystyle\sum\limits_{k=1}^{\infty}\Pr(A_k)=\infty\Longleftrightarrow\Pr(A_k\ i.o.)=1$

So can I assume in this case that $A_k$'s are independent ?

If I show that the sequence, $\Pr(A_k)$ doesn't converge to $0$, the series would be also divergent, but is this a good approach ? (maybe too difficult)

How can I write the events $A_k$, with the Inclusion-Exclusion formula ?

Solution 1:

The $A_k$ are independent because for any $i \neq j$, the sets of tosses $2^i, \ldots, 2^{i+1}-1$ and $2^j, \ldots, 2^{j+1}-1$ are disjoint. Hence, $A_i$ tells you no information about $A_j$.

Let's find upper and lower bounds for $P(A_k)$.

Amongst the tosses numbered $2^k, \ldots, 2^{k+1}-1$, there are $2^k$ tosses, and so, there are $2^k-k+1$ blocks of $k$ consecutive tosses. For each block of $k$ consecutive tosses, the probability of all $k$ tosses being all heads is $p^k$. Hence, the expected number of blocks of $k$ consecutive tosses is $(2^k-k+1)p^k$. Therefore, $P(A_k) \le (2^k-k+1)p^k$.

Amongst the tosses numbered $2^k, \ldots, 2^{k+1}-1$, there are $2^k$ tosses, and so, there are $\left\lfloor\tfrac{2^k}{k}\right\rfloor$ disjoint blocks of $k$ consecutive tosses. For each disjoint block of $k$ consecutive tosses, the probability of all $k$ tosses being all heads is $p^k$. Hence, the probability of any one of these blocks of $k$ tosses being all heads is $1-(1-p^k)^{\left\lfloor\tfrac{2^k}{k}\right\rfloor}$. Therefore, $P(A_k) \ge 1-(1-p^k)^{\left\lfloor\tfrac{2^k}{k}\right\rfloor}$.

• If $p < \dfrac{1}{2}$, then $P(A_k) \le (2^k-k+1)p^k < (2p)^k$, and so, $\displaystyle\sum_{k = 1}^{\infty}P(A_k) \le \sum_{k = 1}^{\infty}(2p)^k = \dfrac{2p}{1-2p} < \infty$.

  Therefore, $P(A_k \ i.o.) = 0$.

• If $p > \dfrac{1}{2}$, then $\ln(1-P(A_k)) \le \left\lfloor\tfrac{2^k}{k}\right\rfloor\ln(1-p^k) \le -\dfrac{2^k}{k}p^k = -\dfrac{(2p)^k}{k} \to -\infty$ as $k \to \infty$.

  So, $1-P(A_k) \to 0$ i.e., $P(A_k) \to 1$ as $k \to \infty$. Hence, $\displaystyle\sum_{k = 1}^{\infty}P(A_k) = \infty$.

  Therefore, $P(A_k \ i.o.) = 1$.

• If $p = \dfrac{1}{2}$, then $\ln(1-P(A_k)) \le -\dfrac{1}{k}$, and so, $P(A_k) \ge 1-e^{-\tfrac{1}{k}} \sim \dfrac{1}{k}$.

  Hence, $\displaystyle\sum_{k = 1}^{\infty}P(A_k) = \infty$ by limit comparison with $\displaystyle\sum_{k = 1}^{\infty}\dfrac{1}{k}$.

  Therefore, $P(A_k \ i.o.) = 1$.

Solution 2:

The $A_k$'s are clearly independent, because they involve disjoint sets of coin flips. ($A_0$ depends on flip $1$; $A_1$ depends on flips $2$ and $3$; $A_2$ depends on flips $4$ through $7$; and so on.) So the Borel-Cantelli lemma applies. Also, "$A_k$ infinitely often" is a tail event, so Kolmogorov's zero-one law says that it must have probability $0$ or $1$. Combining the two facts, you need to show that $\sum_{k=0}^{\infty}P[A_k]$ converges for $p<1/2$ (hence the probability that $A_k$ i.o. is not $1$, hence it must be $0$) and diverges for $p\ge 1/2$ (hence the probability that $A_k$ i.o. is $1$). To show divergence of the sum, it would suffice to show that $P[A_k]$ does not converge to zero; but that result is stronger than necessary and may not even be true.

Hint: find effective upper and lower bounds for $P[A_k]$, such that the sum of the lower bounds diverges for $p\ge 1/2$ and the sum of the upper bounds converges for $p<1/2$.