# Positive probability of event in coin tosses

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.

• Do you mean exactly $n$ heads or at least $n$ heads? – lulu Feb 9 '18 at 18:01
• @lulu I have edited the question. – z00x Feb 9 '18 at 18:03
• 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? – lulu Feb 9 '18 at 18:08
• @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$? – Brian Tung Feb 9 '18 at 18:10
• @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. – 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.