6
$\begingroup$

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 ?

$\endgroup$
8
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This looks so great, I cannot believe. $\endgroup$ – OBDA Jun 28 '14 at 22:34
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This may be a little nit picky but when you say "it's clearly independent because invoke disjoint sets..." Disjoint sets are never independent. I know this isn't what you meant but just wanted to point that out $\endgroup$ – Kamster Jun 28 '14 at 22:24
  • $\begingroup$ @Kamster never ? $\endgroup$ – BCLC Jun 16 '16 at 22:07
  • 1
    $\begingroup$ ok if at least one has probability zero they are independent. but if non zero disjoint is never independent $\endgroup$ – Kamster Aug 29 '16 at 3:39
  • $\begingroup$ @Kamster: The coin flips are mutually independent. Each $A_k$ is a random variable that depends on the coin flips with indices in some $J_k \subseteq \{1,2,3,\ldots\}$. The index sets $J_k$ are described in the problem. For $k\neq k'$, $J_k$ and $J_{k'}$ are disjoint sets of indices. Therefore, $A_k$ and $A_{k'}$ are independent random variables. (I assume you're referring to disjoint events in the probability space.... but "coin 1 comes up heads" and "coin 2 or coin 3 comes up heads" aren't disjoint events, even though $\{1\}$ and $\{2,3\}$ are disjoint sets.) $\endgroup$ – mjqxxxx Aug 29 '16 at 18:34
  • $\begingroup$ yea you are most likely correct, been away from subject for a bit so that is a misunderstanding on my part $\endgroup$ – Kamster Sep 9 '16 at 4:18

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.