Probability Theory – Tossing a Coin with at Least $k$ Consecutive Heads

probability theoryrandom variables

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 ?

Best Answer

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

Related Question