# $K$ consecutive heads with a biased coin?

You toss a coin repeatedly and independently. The probability to get a head is $p$, tail is $1-p$. Let $A_k$ be the following event: $k$ or more consecutive heads occur amongst the tosses numbered $2^k,...,2^{k+1}-1$. Prove that $\mathbb P\left(A_k\hspace{1mm} \text i.\text o.\right)=1$ if $\displaystyle p\geq \frac{1}{2}$, $0$ otherwise.

I'd appreciate any help with this one! edit: Assuming this has to do with Borel-Cantelli, specifically a "$0/1$ law".

We know that if $\{A_n:n\geq 1\}$ is a sequence of independent events in a probability space, then either $\mathbb P\left(A\left(\text i.\text o.\right)\right)=0$, which is the $\mathbb E\left(N\right)<\infty$ case, or $\mathbb P\left(A\left(\text i.\text o.\right)\right)=1$, which is the $\mathbb E\left(N\right)=\infty$ case, where $N$ denotes the total number of $A_n$ to occur;

$\displaystyle N=\sum_{n=1}^{\infty}I_n$, where $I_n=I\{A_n\}$ denote the indicator rv for the event $A_n$.

$\displaystyle \mathbb{E}(N) = \sum_{k=1}^\infty \mathbb{P}(A_k)$, so we have to show that this sum converges for $\displaystyle p< \frac{1}{2}$, and diverges otherwise. (how?)

• Hi Chris, what's $\mathbb P\left(A_k\hspace{1mm} \text i.\text o.\right)=1$? – Vincent Tjeng Mar 14 '13 at 2:42
• $A_k \text{i.o.}$ denotes the event that in the sequence of outcomes $k \geqslant 1$, events $A_k$ occur infinitely often. – Sasha Mar 14 '13 at 2:45
• I understand i.o to mean infinitely often, as sasha said. – Chris Mar 14 '13 at 2:47
• @Chris You are on the right track. Recall that $\mathbb{E}(N) = \sum_{k=1}^\infty \mathbb{P}(A_k)$. Evaluation of $\mathbb{P}(A_k)$ has been done here but most likely this problem does not require it. Only the convergence/divergence needs to be established. – Sasha Mar 14 '13 at 4:48

Per Borel-Cantelli theorem you need to determine convergence of $\sum_{k \geqslant 1}\mathbb{P}\left(A_k\right)$. Per section 14.1 of the "Problems and snapshots from the world of probability" by Blom, Holst and Sandell the probability than amongst $2^k$ throws considered in $A_k$ a run of heads of length $\geqslant k$ will occur can be extracted from the probability generating function: $$\mathbb{P}\left(A_k\right) = [s^{2^k}] \frac{p^k s^k (1-p s)}{\left(1-s + (1-p)p^k s^{k+1}\right)\left(1-s\right)} = [s^{2^k}] G_{k,p}(s)$$ Because $n=2^k$ grows much faster than $k$, we can use asymptotic techniques to find $c_n = [s^n]G_{k,p}(s)$. The large $n$ behavior of $c_n$ is determined by smallest positive roots of the denominator of $G_{k,p}(s)$. The smallest in absolute value root of equation $1-s + (1-p)p^k s^{k+1}$ is close to $s=1$, specifically: $$s_\ast = 1 + \frac{(1-p) p^k}{ 1-(k+1) (1-p) p^k } + \mathcal{o}\left(p^k\right) > 1$$ Thus in the vicinity of $s=1$ the $G_{k,p}(s)$ behaves as $$G_{k,p}(s) \approx \frac{p^k s^k (1-ps)}{(s_\ast - s) (1-s)} = \sum_{m=k}^\infty s^m p^k \frac{1 - s_\ast^{m-k+1} - p (1- s_\ast^{k-m})}{s_\ast - 1}$$ and thus since for large $k$ the root $s_\ast$ is very close to $1$ giving $$\left[s^{2^k}\right] G_{k,p}(s) \approx 1 - \left(1-\frac{p^k}{1-k (1-p) p^k }\right) s_\ast^{k - 2^k} \approx 1 - \exp\left(-\lambda_k \right)$$ where $$\lambda_k = (2^k -k ) (s_\ast - 1) = (2^k -k )\frac{(1-p) p^k}{ 1-(k+1) (1-p) p^k }$$ Clearly $\lim_{k \to \infty} \lambda_k = 0$ and thus $\lim_{k \to \infty} \mathbb{P}(A_k) = 0$ exponentially for $2p < 1$, and thus $\sum_{k \geqslant 1} \mathbb{P}(A_k)$ convergence, hence $\mathbb{P}\left(A_k \text{ i.o}\right) = 0$ by Borel-Cantelli theorem.
Furthermore $\lim_{k \to \infty} \lambda_k = \infty$ for $2p>1$ implying $\mathbb{P}\left(A_k \text{ i.o}\right) = 1$.
When $p=\frac{1}{2}$ we have $$\lambda_k = \left(2^k -k \right) \frac{2^{-k-1}}{1-(k+1) 2^{-k-1}} \rightarrow_{k \to \infty} \frac{1}{2}$$ therefore $\mathbb{P}(A_k) \to 1-\exp(-1/2)$ and the sum $\sum_{k \geqslant 1} \mathbb{P}(A_k)$ diverges, implying $\mathbb{P}\left(A_k \text{ i.o}\right) = 1$.