Vtyjkyuk

The original question:

If I toss a coin 15000 times, what is the probability that I'll get at least 15 consecutive heads at least once.

The workup:

Consider a toy example, 2 consecutive heads in 5 flips, we have the following cases (where X is don't cares):

Toss | Result
------|-------
HHXXX | True
THHXX | True
?THHX | True
??THH | True
Other | False

The ?s are because in order to avoid double counting cases we require that the ?s not result in our goal. Let $C(f, h)$ represent the number of successful cases out of all the $2^f$ cases, and let $neg C(f, h) = 2^f - C(f, h)$ representing the number of unsuccessful cases. In this case our toy example is:

$$C(5, 2) = 2^3 text(from the Xs on line one) + neg C(0, 2) cdot 2^2 text(line two) + neg C(1, 2) cdot 2 text(line three) + neg C(2, 2) text(line four)$$

This gives 19.

Let's consider what happens when we go up by one:

Toss | Result
---------|-------
HHXXX(X) | True
THHXX(X) | True
?THHX(X) | True
??THH(X) | True
(???THH) | True
Other | False

So we have an extra X for each of the lines that were in C(5,2) and one more line.

$$C(6,2) = 2 C(5,2) + neg C(3,2)$$

From this we can deduce a method of increasing the number of flips by one:

$$C(f+1, h) = 2 C(f, h) + neg C(f-(h+1), h)$$

And then we can set some initial conditions:

$$beginsplit
C(f=h, h) &= 1 \
C(f<h, h) &= 0 \
endsplit$$

Finally the probability of any $f, h$ pair is simply:

$$P(f,h) = fracC(f,h)2^f$$

My question:

From here it's possible to simply let a computer crunch on this to get a solution. However, just for the sake of curiosity, I wanted to come up with an explicit formula. What I would normally do is come up with a matrix form of this formula then perform an eigendecomposition on it.

$$beginpmatrix
2 & 0 & 0 & dots & ? \
1 & 0 & 0 & dots & 0 \
0 & 1 & 0 & dots & 0 \
vdots & vdots & vdots & ddots & vdots \
0 & 0 & 0 & dots & 0 \
endpmatrix
beginpmatrix
C(f,h) \
C(f-1,h) \
C(f-2,h) \
vdots \
C(f-(h+1),h) \
endpmatrix
=
beginpmatrix
C(f+1,h) \
C(f,h) \
C(f-1,h) \
vdots \
C(f-h,h) \
endpmatrix $$

But I don't think it's possible to cleanly represent $neg C$ in this fashion, and that's what needs to go into the spot with the ?.

So next I tried to get rid of the $2^f$ in the formula.

$$beginsplit
C(f, h) &= 2C(f-1, h) + 2^f - C(f-(h+2), h) \
C(f-1, h) &= 2C(f-2, h) + 2^f - C(f-(h+3), h) \
C(f, h) &= 3C(f-1, h) - 2C(f-2, h) - C(f-(h+2), h) + C(f-(h+3),h) \
endsplit$$

And this works. However, when I put all of this together, and take the eigenvectors, one eigenvector is 0, 0, 0, ..., 0. So the matrix of eigenvectors is singular, so I can't use the $SLambda^nS^-1$ formula.

Is there an approach that will work in this case?

Let $p_n$ be the probability that you get $15$ consecutive heads when you flip a coin $n$ times. A recurrence relation is
$$
p_n = frac12p_n-1 + frac14 p_n-2+frac18p_n-3 + dots + frac12^14p_n-14+frac12^15p_n-15 + frac12^15tag$nge 15$
$$
The first term accounts for the cases where you flip $T$ first, and you now need to get $15$ heads in a row in the remaining $n-1$ flips. The next term is for when your first two flips are $HT$, the third when they are $HHT$, etc. The last term account for when the first 15 flips are all heads.

The trick you tried works to get rid of the $frac12^15:$

$$
p_n-p_n-1=frac12p_n-1-frac14p_n-2-frac18p_n-3-dots-frac12^15p_n-15-frac12^15p_n-16
$$
You can now put this in matrix form and find the eigenvalues, etc.

Letting $C_n$ be the number of sequences of flips with a run of 15 heads, which is $C(n,15)$ in your notation, then
$$
C_n = C_n-1+C_n-2 + dots + C_n-15 + 2^n-15. tag1
$$
To get rid of the $2^n-15$, you should instead subtract two times the previous eqaution:
$$
2C_n-1 = 2C_n-2+dots +2C_n-15+2cdot 2^n-16
$$
The result is
$$
C_n = 3C_n-1-C_n-2-ldots-C_n-15-2C_n-16
$$

If you apply the usual subtraction trick to $(1)$, you get
$$
C_n = 2C_n-1 - C_n-16 + 2^n-16
$$
which is exactly the recurrence you had before.

As I mentioned in my comment, I had made a simple error in simplifying the recurrence relationship.

$$C(f-1, h) = 2C(f-2, h) + 2^f - C(f-(h+3), h)$$

Should have been:

$$C(f-1, h) = 2C(f-2, h) + 2^f-(h+3) - C(f-(h+3), h)$$

and so on...

From this it's possible to simplify the relationship as follows (third line is obtained by subtracting $2 C(f-1, h)$ from both sides and simplifying):

$$beginsplit
C(f, h) &= 2C(f-1, h) + 2^f-(h+2) - C(f-(h+2), h) \
C(f-1, h) &= 2C(f-2, h) + 2^f-(h+3) - C(f-(h+3), h) \
C(f, h) &= 4C(f-1, h) - 4C(f-2, h) - C(f-(h+2), h) + 2 C(f-(h+3),h) \
endsplit$$

From here, the derivation is straightforward, I let a symbolic computation program crunch on it for a while and it gave the explicit formula for $C(n, 2)$ to be (n = f-h):

$$-fraci4 sqrt11left(textRootleft[text$#$1^6+42340 text$#$1^4-10128 text$#$1^2+704&,3right] textRootleft[text$#$1^3-text$#$1^2-text$#$1-1&,1right]^n+textRootleft[text$#$1^6+42340 text$#$1^4-10128 text$#$1^2+704&,2right] textRootleft[text$#$1^3-text$#$1^2-text$#$1-1&,2right]^n+textRootleft[text$#$1^6+42340 text$#$1^4-10128 text$#$1^2+704&,6right] textRootleft[text$#$1^3-text$#$1^2-text$#$1-1&,3right]^n+2 i sqrt11 left(2^n+5+1right)right)$$

I didn't bother to compute the explict formula for h=15.