# The longest run of heads

Let be $X_1, X_2,\; \ldots$ independent and identically distributed (i.i.d.) random variables with common distribution: $\mathbb{P}(X_k=1)=p,\; \mathbb{P}(X_k=0)=1-p$. We fix a $\lambda > 1$ parameter and let $A_k^{(\lambda)}$ denote the following events: $k=1, 2, 3, \dots$ $$A_k^{(\lambda)}: = \{ \exists r \in [[\lambda^k], [\lambda^{k+1}]-1]\cap\mathbb{N}: X_r=X_{r+1}= \dots =X_{r+k-1}=1\}$$ where $[\lambda^k]$ denotes the floor. I.e.: $A_k^{(\lambda)}$ event means that between $[\lambda^k]$a and $[\lambda^{k+1}]-1$ exists a $k$ long run of ones. Let's prove:

a) If $\lambda < p^{-1}$ then $A_k^{(\lambda)}$ events occurs only for finitely many k with probability of 1.

b) If $\lambda > p^{-1}$ then $A_k^{(\lambda)}$ events occurs infinitely many times with probability of 1.

c) What happens when $\lambda=p^{-1}$?

Any help would be appreciated.

-
I think third question should be: "What happens if $\lambda=1/p$?" – Norbert Apr 14 '12 at 17:51
(+1) Is this homework? If so, kindly add the homework tag. :) – cardinal Apr 14 '12 at 18:23
Does $[\lambda^k]$ denote the nearest integer, or floor, or ceiling, or what? – Quinn Culver Apr 14 '12 at 19:19
Does "...among $A_{k}^{(\lambda)}$ events occurs only finitely many..." mean that $A_{k}^{(\lambda)}$ occurs for only finitely many $k$? – Quinn Culver Apr 14 '12 at 19:35
Thank you. I added the tag as you suggested and completed the text that $[\lambda^k]$ denotes the floor, plus I corrected the sentence that was not clear. – Dawson Apr 14 '12 at 20:16

The three parts are consequences of Borel-Cantelli lemmas hence we begin by controlling the probability of $A^{(\lambda)}_k$.
On the one hand, this event involves at most $\lambda^{k+1}-\lambda^k$ (non independent) events of probability $p^k$ hence, introducing $\mu=\lambda-1\gt0$, $$\mathrm P(A^{(\lambda)}_k)\leqslant \mu\cdot(p\lambda)^k.$$ On the other hand, decomposing the interval $(\lambda^k,\lambda^{k+1})$ into disjoint intervals of length $k$, one gets at least $\mu\lambda^k/k$ (independent) events of probability $p^k$ hence $$\mathrm P(A^{(\lambda)}_k)\geqslant 1-(1-p^k)^{\mu\lambda^k/k}.$$ These two estimates imply the following:
• In case (a), $p\lambda\lt1$ hence $\sum\limits_k\mathrm P(A^{(\lambda)}_k)$ converges and the first Borel-Cantelli lemma yields the conclusion in your post.
• In case (b), $p\lambda\gt1$ hence $(1-p^k)^{\mu\lambda^k/k}\to0$, $\mathrm P(A^{(\lambda)}_k)\to1$ and $\sum\limits_k\mathrm P(A^{(\lambda)}_k)$ diverges. Since the events $(A^{(\lambda)}_k)_k$ are independent, the second Borel-Cantelli lemma yields the conclusion in your post.
• In case (c), $(1-p^k)^{\mu\lambda^k}=(1-p^k)^{\mu/p^k}\to\mathrm e^{-\mu}\gt0$ hence $\mathrm P(A^{(\lambda)}_k)\geqslant (\mu+o(1))/k$ and the second Borel-Cantelli lemma shows that, almost surely, infinitely many events $A^{(\lambda)}_k$ occur.