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?)

  • $\begingroup$ Hi Chris, what's $\mathbb P\left(A_k\hspace{1mm} \text i.\text o.\right)=1$? $\endgroup$ – Vincent Tjeng Mar 14 '13 at 2:42
  • 1
    $\begingroup$ $A_k \text{i.o.}$ denotes the event that in the sequence of outcomes $k \geqslant 1$, events $A_k$ occur infinitely often. $\endgroup$ – Sasha Mar 14 '13 at 2:45
  • $\begingroup$ I understand i.o to mean infinitely often, as sasha said. $\endgroup$ – Chris Mar 14 '13 at 2:47
  • 2
    $\begingroup$ @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. $\endgroup$ – 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$.

Nice question! Being a homework, I am sure there must be a simpler solution, and I am very keen to see it now.

  • $\begingroup$ Wow, this is amazing. I'm going to speak with my professor about the problem and when I get something simpler, I'll post it here. Thank you! $\endgroup$ – Chris Mar 14 '13 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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