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$.

  • $\begingroup$ Can the subsequences overlap? $\endgroup$ – rubik Sep 21 '15 at 12:56
  • $\begingroup$ No, so if s = {H,H,H} and S = {H,H,H,H,H} then s is not repeated twice in S $\endgroup$ – Agoston T Sep 21 '15 at 12:59
  • $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Sep 21 '15 at 13:02
  • $\begingroup$ @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? $\endgroup$ – Agoston T Sep 21 '15 at 13:19
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Sep 21 '15 at 13:25

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.

  • $\begingroup$ 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) $\endgroup$ – Agoston T Sep 21 '15 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.