# Probability of $7$ tails in a row twice in $100$ coin flips

The starting point for my problem was the chance of having a $7$ tails in a row if you flip a coin $100$ times. I found this excellent explanation of calculating it: http://www.leancrew.com/all-this/2009/06/stochasticity/

My question: What is the chance of having (at least) $7$ tails occurring (at least) two times in a $100$ coin flip sequence? In general: $s$ is a sequence of length $n$ and $r$ is the number of repetitions, what are the odds that I found at least $r$ repetition of sequence $s$ in a sequence $S$ that has a length of $N$.

• Can the subsequences overlap? – rubik Sep 21 '15 at 12:56
• No, so if s = {H,H,H} and S = {H,H,H,H,H} then s is not repeated twice in S – Agoston T Sep 21 '15 at 12:59
• It looks to me that you already have the solution. The answer depends on a generalized Fibonacci sequence and by the dominant root of the associated characteristic polynomial. – Jack D'Aurizio Sep 21 '15 at 13:02
• @JackD'Aurizio: I'm not looking for only consecutive 14 tails but 7 tails occuring two times anywhere in the S sequence, so if s = {H,H} and S = {H,H,T,H,H} then r is 2. So for N = {1,2,3,4,5,6,7,8} possible S sequences that not contain s = {H,H} r = 2 times is {2,4,8,15,28,51,92,164} and that is not a generalized Fibonacci sequence. Or am I missing something? – Agoston T Sep 21 '15 at 13:19
• @Agoston: sorry, I misread the problem. In such a case, assuming we have a sequence of $2L$ outcomes, a good approximation is given by considering the concatenation of two sequences with length $L$, each of them having at least a run of seven tails. – Jack D'Aurizio Sep 21 '15 at 13:25

## 1 Answer

Here is a method that uses matrices. You would need Matlab or Mathematica or something similar to run it.

You can be in any one of fifteen situations:
1. Start; or previous toss was a H; no septet yet.
2. Previous toss was an T; no septet yet.
3. Previous two tosses were TT; no septet yet.
all the way down to
14. Previous six tosses were TTTTTT; already one septet
15. Win!
Any toss sends you either to the next situation; or back to either 1. or 8.
You can summarize this in a $15\times15$ matrix A. The first column is $[1/2,1/2,0,0,...,0]^T$ because state 1 sends you to state 1 half the time and state 2 half the time.
You start entirely in state 1, so with a vector $v=[1,0,0,...,0]^T$.
Now calculate $A^{100}v$ . The final entry in the result is your chance of two septets.

• Great solution, checked it in R and worked well, I modified only so that matrix A dimensions are rows = (n x r +1) cols = (N) and the probability was the sum of the last row (this is just convenience since base R does not support matrix power function) – Agoston T Sep 21 '15 at 21:10