Lets say I toss a coin infinite times such that all tosses are independent. Does the event "For all $n\in \mathbb N$, we had exactly $n$ heads in a row between the toss number $3^n$ and toss number $3^{n+1}$" have a positive probability?

Is it it true for $n^2$?

I am thinking about using Borel-Cantelli but don't know how to begin formalizing the problem.

  • $\begingroup$ Do you mean exactly $n$ heads or at least $n$ heads? $\endgroup$ – lulu Feb 9 '18 at 18:01
  • $\begingroup$ @lulu I have edited the question. $\endgroup$ – z00x Feb 9 '18 at 18:03
  • $\begingroup$ But you have not clarified it. What does "exactly $n$ heads in a row" mean? Just take $n=1$, say. So we are looking between $3$ and $9$. Which sequences are good and which are bad? $\endgroup$ – lulu Feb 9 '18 at 18:08
  • $\begingroup$ @lulu: I agree that it's unclear, but does it matter for this particular question? We require only a positive probability. So long as $3^{n+1}-3^n \geq n$ (or $n^2$), shouldn't the probability be greater than $0$? $\endgroup$ – Brian Tung Feb 9 '18 at 18:10
  • $\begingroup$ @BrianTung But you need this for all $n$. Depending on what the OP is asking, that sounds like an infinite product wherein the factors decrease to $0$. But perhaps (probably?) I have an entirely incorrect picture of what is being asked. $\endgroup$ – lulu Feb 9 '18 at 18:13

The question as stated currently (2018-02-09-1820 UT) is somewhat unclear, but we will view it in the following restrictive way:

  • For any $n \in \mathbb{N}_{\geq 1}$, we look only at the sequence of tosses $3^n+1$ through $3^{n+1}-1$; that is, we look at $2 \times 3^n - 1$ tosses.
  • We require that the run of $n$ consecutive heads be entirely isolated within that sequence.

We will show, broadly, that the probability is always non-zero, and that its limiting probability, as $n \to \infty$, is $1$.

First, we note that the number of tosses we look at, $2 \times 3^n - 1$, is always greater than $n+2$, for $n \geq 1$. It is true for $n = 1$, and whenever it is true for $n = k$, it is (almost) trivially true for $n = k+1$. Induction thus suffices to establish our claim.

The probability that the first $n+2$ tosses in our sequence have the form $THH \cdots HHT$ is $\frac{1}{2^{n+2}}$. This is non-zero for any $n \geq 1$; since this is a lower bound for the probability of any run of exactly $n$ heads, that probability must also be non-zero for any $n \geq 1$.

[Note: The 'align' environment doesn't seem to be working at the moment? Formatting may be askew.]

We now show, broadly, that the limiting probability is $1$. Not a rigorous proof, but you can proceed sort of along these lines:

It may not escape your notice that not only does $2 \times 3^n - 1 > n+2$, but the former grows rather faster than the latter. For any $n \geq 1$, in fact, we look at, altogether,

$$ \left\lfloor \frac{2 \times 3^n - 1}{n+2} \right\rfloor $$

segments of $n+2$ tosses. Note that for $n \geq 1$,

$$ \left\lfloor \frac{2 \times 3^n - 1}{n+2} \right\rfloor \geq \frac{3^n}{n+2} \\ \geq \frac{3^n}{3n} \\ \geq \frac{3^n}{3(6/5)^n} \\ \geq \frac{(5/2)^n}{3} $$

(There probably was an easier way to get to what I wanted, but that'll work.) Recall that a segment of length $n+2$ has the form $THH \cdots HHT$ with probability $\frac{1}{2^{n+2}}$, so the probability that none of $\frac{(5/2)^n}{3}$ segments have such a form is at most

$$ \left( 1 - \frac{1}{2^{n+2}} \right)^\frac{(5/2)^n}{3} = \left[ \left( 1 - \frac{1}{2^{n+2}} \right)^{2^{n+2}} \right] ^\frac{(5/2)^n}{3\times 2^{n+2}} \\ \to \exp \left( - \frac{(5/4)^n}{12} \right) \\ \to 0 $$

So the limiting probability is $1-0 = 1$ that there will be such a run, somewhere in those segments.


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.