Positive probability of event in coin tosses

Question

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.

Answer 1

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.