Probability of at least 1 sequence of 6 heads followed by 6 tails among $n$ tosses?

Question

You flip a coin $n > 11$ times. What is the probability that you have at least 1 sequence with 6 heads followed by 6 tails.

I am completely lost on how to solve this in an elegant way. The approach that I am thinking of would involve the inclusion-exclusion principle. We'd examine the feasibility of each location in the sequence NOT being the start of the said sequence.

We can define $a_i$ to be the event that the said sequence does not begin at the $i$-th location. Then the probability we're looking for is

$$ 1 - P\left(\bigcup_{i=1}^{N - 11}a_i \right) $$.

To find $P\left(\bigcup_{i=1}^{N - 11}a_i \right)$, I believe I would need to invoke the inclusion-exclusion principle, and this will get pretty messy. Is there a simpler approach?

Answer 1

Suppose the $n$ coin flips end up with $k$ such runs of 12 coin flips. Collapse each run into one slot so that you are thinking in terms of $n-11k$ slots, where $k$ of the slots will expand to be that kind of run of 12. (Note that the runs-of-12 cannot overlap. This problem would need a different solution if, say, we were looking at runs of THT that can overlap.)

If $12\leq n<24$, then it's only possible for $k$ to be $1$. You choose which slot to expand, and let the rest be coin flips that fall where they may: $$\frac{\binom{n-11}{1}2^{n-12}}{2^n}$$

Now if $24\leq n<35$, use the same formula, but with inclusion-exclusion to account for when there are two runs of 12 like this: $$\frac{\binom{n-11}{1}2^{n-12}}{2^n}-\frac{\binom{n-22}{2}2^{n-24}}{2^n}$$

Notice that second term is zero for $12\leq n<24$, so its actually a valid formula for $12\leq n<24$ as well.

EDIT

The above line is false, I was wrong. For example, something like $\binom{-2}{3}$ is nonzero. It equals $\frac{(-2)(-3)(-4)}{3!}=-4$. So what follows is edited from earlier versions.

Continue in this way with inclusion-exclusion to find $$\sum_{k=1}^{\lfloor n/12\rfloor}(-1)^{k-1}\frac{\binom{n-11k}{k}2^{n-12k}}{2^n}=\sum_{k=1}^{\lfloor n/12\rfloor}(-1)^{k-1}{\binom{n-11k}{k}}2^{-12k}$$

You can even extend this to work for $0\leq n<12$, and simplify to:

$$1-\sum_{k=0}^{\lfloor n/12\rfloor}\left(-2^{-12}\right)^k{\binom{n-11k}{k}}$$

Answer 2

The independence approximation should work quite well here. Calling $E_i$ the event that the sequence $(c_i,c_{i+1}\cdots c_{i+11})$ does not follow the desired pattern, we have

$$\begin{align} p_n &= 1 - P(E_1 \cap E_2 \cap \cdots E_{n-11})\\ &\approx 1 - \prod_{i=1}^{n-11} P(E_i)\\ &= 1-\left(1-\frac{1}{4096}\right)^{n-11} \end{align}$$

An exact numerical solution can be obtained with Markov chains. The state $s\in \{0,1, 2 \cdots 12\}$ denotes, when $s<12$ the number of matching coins in the tail of the sequence (the desired sequence has not yet appeared); while $s=12$ (absorbing state) means that the desired sequence has already appeared. The transition matrix is given by $P = A/2 $ where $A$ is the following $13 \times 13$ matrix:

   1   1   0   0   0   0   0   0   0   0   0   0   0
   1   0   1   0   0   0   0   0   0   0   0   0   0
   1   0   0   1   0   0   0   0   0   0   0   0   0
   1   0   0   0   1   0   0   0   0   0   0   0   0
   1   0   0   0   0   1   0   0   0   0   0   0   0
   1   0   0   0   0   0   1   0   0   0   0   0   0
   0   0   0   0   0   0   1   1   0   0   0   0   0
   0   1   0   0   0   0   0   0   1   0   0   0   0
   0   1   0   0   0   0   0   0   0   1   0   0   0
   0   1   0   0   0   0   0   0   0   0   1   0   0
   0   1   0   0   0   0   0   0   0   0   0   1   0
   0   1   0   0   0   0   0   0   0   0   0   0   1
   0   0   0   0   0   0   0   0   0   0   0   0   2

In Matlab/Octave:

A = [zeros(12,1),eye(12);zeros(1,13)];
A(1:6,1)=1;
A(8:12,2)=1;
A(7,7)=1;
A(13,13)=2;
P = A/2
p0 = [1,zeros(1,12)]

% prob after 11 tries:
(p0 * P^11) (1,13)
ans = 0
% prob after 12 tries:
(p0 * P^12) (1,13)
ans =  0.00024414
% prob after 13 tries:
(p0 * P^13) (1,13)
ans =  0.00048828
% prob after 24 tries:
(p0 * P^24) (1,13)
ans =  0.0031738
% prob after 50 tries:
(p0 * P^50) (1,13)
ans =  0.0094990
% prob after 200 tries:
(p0 * P^200) (1,13)
ans =  0.045215
% approximation
1-(1-1/4096)^(200-11)
ans =  0.045100