Let $Q_n$ be the probability that no $3$ consecutive heads appear on $n$ throws of a fair coin. Show that the following recurrence formula is true:

$$Q_n = \frac12 Q_{n-1} + \frac14 Q_{n-2} + \frac18 Q_{n-3} $$

I'm having problems trying to figure out $Q_n$ (not asked by the question) and this recurrence formula.

Thank you

obs.: $Q_0 = Q_1 = Q_2 = 1$


2 Answers 2


Hint: You can partition the event "no three consecutive heads appear in $n$ coin tosses" based on the first three coins; specifically, what about these disjoint events:

  1. The first coin is tails.
  2. The first coin is heads but the second coin is tails.
  3. The first two coins are heads but the third is tails.
  4. The first three coins are all heads.
  • $\begingroup$ Sorry, but I don't understand: why the first three? $\endgroup$ Jun 17, 2015 at 21:23
  • $\begingroup$ @kaslusimoes Well, the first three are to get you started mostly with the equation, not the entire answer. $\endgroup$
    – Kbot
    Jun 17, 2015 at 21:34
  • $\begingroup$ Well, you could just as easily use the last three. The big idea here is that you want to find a recurrence relation -- and in order to do that, you have to find some way to reduce the bigger problem in to a set of smaller, similar problems. If you know what happens with the first coin, you just have to figure out what happens with the remaining $n-1$. If you know the first two, you have to figure out what happens with the remaining $n-2$. Etc. The real question is: why did I only look at cases where the last coin is tails? What does that tell you about the rest of the coin flips? $\endgroup$ Jun 17, 2015 at 21:44
  • $\begingroup$ Got it! Thank you guys $\endgroup$ Jun 19, 2015 at 17:01

Let $X_n$ = 1 if flip n was heads, and 0 if tails.

$$Qn = P(X_n = 0)*Q_{n-1} + P(X_n=1,X_{n-1}=0)*Q_{n-2}+P(X_n=1,X_{n-1}=1,X_{n-2}=0)Q_{n-3}$$

$$= \frac{1}{2}Q_{n-1}+\frac{1}{4}Q_{n-2}+\frac{1}{8}Q_{n-3}$$

The solution is

$$Q_n = \frac{F_{n+2}^{(3)}}{2^n}$$

where $F_n^{(3)}$ is a Fibonacci 3-step number.

$$F_0^{(3)} = 0$$ $$F_1^{(3)} = 1$$ $$F_2^{(3)} = 1$$ $$F_n^{(3)} = F_{n-1}^{(3)} + F_{n-2}^{(3)} + F_{n-3}^{(3)},\:\: n>2$$

See http://mathworld.wolfram.com/Run.html

Here is another recurrence for 3 consecutive successes:

$$P_n = P_{n-1} + \frac{1}{16}(1-P_{n-4})$$

where $P_n = 1-Q_n$, $P_0=P_1=P_2=0$, $P_3=1/8.$ To get HHH by $n$, you either get it by $n-1$, or you got it first on $n$ which means you got THHH with probabilty $1/16$ after failing to get it by $n-4$.

There is a closed form solution to problems like this in general for arbitrary run lengths and probabilities, but it tends to be numerically ill-conditioned.

  • $\begingroup$ why would $F_1$ and $F_2$ be 1 and not 2 and 4 respectively? $\endgroup$ Oct 13, 2021 at 13:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .