Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I toss a fair coin $n$ times, calculate the probability that no pattern HHTHTHH occurs.

share|improve this question
Is this homework? If yes, please post what you have tried. –  picakhu Jan 19 '11 at 6:00
@picakhu: It is my understanding that we should not unilaterally tag a question as homework unless there is some explicit reason to know that it is homework (the OP says it is homework in the body, or some such), and specifically not to do it on the basis of our guess that it is a homework problem. –  Arturo Magidin Jan 19 '11 at 6:07
Ill remove the tag, it certainly looks like homework to me, (based on other questions asked by OP) –  picakhu Jan 19 '11 at 6:08
@picakhu: Yes, it looks like it; as I said, this is my understanding. Certainly, ask and request that if it is, they add the tag. –  Arturo Magidin Jan 19 '11 at 6:13
Guys, this is definitely not homework! –  Qiang Li Jan 19 '11 at 6:37
add comment

3 Answers

up vote 3 down vote accepted

I ended doing something very similar to Moron.

Define a Markov chain with states i=0..7 as follows. Given a full sequence of n coins, if the pattern has not yet appeared, find the maximum length of the last tosses (sequence suffix) that coincide with the begginning of the expected pattern, so that

   i =  length of matching suffix , if pattern has not appeared
   i = 7 otherwise

For example: HTTHTTTTHT : i=0 , HTTTTHHT i=3

It's easy to write down the transition probabilities. (i=7 would be a absorbent state), and the probability of being in state 7 in step n.

So your anwser would be $ P(n) = 1- p_7[n]$ where $p[n] = M^n p[0]$ where $M$ is the 8x8 transition matrix and $p[0] = (1,0,0,0,0,0,0,0)$ is the initial state. I doubt you'll get a simpler closed form answer.

One could get a very coarse approximate solution by assumming that the patterns starting at each position are independent (obviously a false assumpion), and get $ P(n) \approx (1-2^{-7})^{n-6}$ ($n \ge 7$)

UPDATE: some Octave/Matlab code to test the approximation (it seems to work better than I'd expected)

% approximation
pa = (1-1/128).^((1:N)-6);
% transition matrix:
M = [ 1,1,0,0,0,0,0,0 ;
      1,0,1,0,0,0,0,0 ;
      0,0,1,1,0,0,0,0 ;
      1,0,0,0,1,0,0,0 ;
      0,0,1,0,0,1,0,0 ;
      1,0,0,0,0,0,1,0 ;
      1,0,0,0,0,0,0,1 ;
      0,0,0,0,0,0,0,2 ]/2;
for n = 1:N
 p = p * M;
 p7(n) = 1 - p(8);

>>> pa(5:9)
ans =

   1.00000   1.00000   0.99219   0.98444   0.97675

>>> p7(5:9)
ans =

   1.00000   1.00000   0.99219   0.98438   0.97656

>>> pa(N-5:N)
ans =

   0.22710   0.22533   0.22357   0.22182   0.22009   0.21837

>>> p7(N-5:N)
ans =
   0.22717   0.22540   0.22364   0.22189   0.22016   0.21844
share|improve this answer
@leonbloy: Is it possible for you to use this method to get a recurrence formula for the probability in question? No need to explicitly solve for a closed-form solution; a recurrence relation is enough. –  Qiang Li Jan 19 '11 at 17:14
The recurrence you get is for the full probability vector: $p[n] = M p[n-1]$ . I doesn't give (I don't think it's possible) a recurrence in terms on the single probability in question ($p[7] or 1-p[7]$). –  leonbloy Jan 19 '11 at 17:29
@leonbloy: the $P(n) \approx (1-2^7)^{n-7} (n>6)$ does not look correct. Can you explain what should it look like and why? Many thanks! –  Qiang Li Jan 19 '11 at 22:51
I made some small corrections. Does it look good to you know ? At least it's exact for n=7 :-) –  leonbloy Jan 19 '11 at 23:13
actually I have just tested the approximation and it seems to approximate very well the exact result –  leonbloy Jan 19 '11 at 23:53
show 7 more comments

Construct a deterministic finite automaton which detects the regular expression $.*(HHTHTHH).*$ such that the sole accepting state $A$ always transitions to a state $B$, which always transitions to itself. The starting state is $S$.

This is basically a directed graph and we can find the transition matrix $P$, each row of which gives the probabilities of getting from one state (i.e. vertex) corresponding to that row, to the next states (one vertex corresponding to each column).

You basically need the entries corresponding to starting state $S$ and ending state $A$, from each of $P, P^2, P^3, \dots , P^n$ and add them up to get the probability that the pattern $HHTHTHH$ occurs (or more simply the $(S,B)$ entry of $P^{n+1}$ will do). Subtract that from $1$ and you are done.

The $(S,A)$ entry of $P^k$ gives the probability that we find the pattern exactly at the end of $k$ tosses, and no tosses before that.

share|improve this answer
not completely get your solution. Is it possible for you to use this method to get a recurrence formula for the probability in question? –  Qiang Li Jan 19 '11 at 17:13
@Qiang: It gives you multiple recurrences (one for each state). You can diagonalize the matrix (if that possible) to compute the powers easily. –  Aryabhata Jan 19 '11 at 18:43
add comment

I don't know about exact solution, but numeric approximation is $P(n)=1-e^{-\frac{n}{125}}$. alt text

Matlab\Octave Code

function test_script_1()
function result=tsh(a,b,n)
% HHTHTHH (H -> 1 , T -> 0)
if isempty(a)
    a=logical([1 1 0 1 0 1 1]);
if isempty(b)
if isempty(n)
if any(size(n)>1)
    for pa=1:length(n)
for i=1:b
    for j=1:n
        if all(a==v(j:j+la-1))
function resu=raspr(a1,b1,s)

Somebody know why is that?

share|improve this answer
Because you can treat the problem as a rare event problem, i.e. the probability of encountering the sequence HHTHTHH is small. Therefore the probability distribution for the waiting time to encountering the sequence will be approximately exponential. So you only need to compute find the expectation value of the waiting time to have a nice exponential approximation. I guess that can be found by a simple recursion relation. –  Raskolnikov Jan 20 '11 at 13:11
this is wrong, as $n \to \infty$, $P(n)\to 0$. Yours goes to 1. –  Qiang Li Jan 20 '11 at 20:34
Yes, the law is expected to be exponential. In fact, if you see my approximation, it's practically the same (127.5 instead of 125, and a -6 shift that is unimportant for large n. –  leonbloy Jan 20 '11 at 21:45
@Qiang Li - you right, i have read the question wrong. But it still correct for inverse problem –  Alexander Jan 20 '11 at 22:17
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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