Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

closed as off-topic by LeGrandDODOM, Ivo Terek, ᴡᴏʀᴅs, PhoemueX, saz Oct 11 '14 at 19:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – LeGrandDODOM, Ivo Terek, ᴡᴏʀᴅs, PhoemueX, saz
If this question can be reworded to fit the rules in the help center, please edit the question.

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|cite|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

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|cite|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

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|cite|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

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