1
$\begingroup$

What is the probability of getting two consecutive heads in 20 coin tosses?

I found that the expected number of throws to get two consecutive heads is 6, implying the probability of two heads in a row is 1/6. I realize I need to use the idea from this answer, which means having a $3 *3$ Transition Matrix, where:

$A$: We have not had 2 Heads in a row yet

$B$: We have not had 2 Heads in a row yet, but had one Head in the last trial

$C$: We have have 2 Heads in a row

Would this be the required transition matrix: $$\begin{bmatrix}5/6 & 5/6 &0\\1/6 & 0 & 0\\0 & 1/6 & 1\end{bmatrix}$$? And then calculate $M^{20}$ and the value associated with this matrix for the entry (3,1)?

Thank You

$\endgroup$
1
  • $\begingroup$ Do you mean for A: "We have not had 2 Heads in a row yet, and the last trial was a Tail"? The way you wrote it, A includes B. $\endgroup$ – Rory Daulton Sep 12 '15 at 22:48
1
$\begingroup$

Three mutually exclusive states are:

  1. Haven't thrown yet, or last throw was a tail. Have not had two heads yet.
  2. Last throw was head. Have not had two heads yet.
  3. Have had two heads in a row. This is an absorbing state.

Then the transition matrix is:

$$M=\begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & 1 \\ \end{bmatrix}$$

Then compute $M^{20}$ as you suggested, and then

$$\mathbf{x}=M^{20}\begin{bmatrix}1\\0\\0\end{bmatrix}=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}$$

where $x_3$ is the probability that the final state is absorbing, i.e. two consecutive heads were recorded.


However, there is another method that reveals an exact answer that is related to the Fibonacci sequence.

Let:

  • $H_n =$ prob. of getting two consecutive heads where last throw was a head, with $n$ throws left
  • $T_n =$ prob. of getting two consecutive heads where last throw was a tail, with $n$ throws left

Then we have the initial (final?) conditions:

  • $H_0 = 0$
  • $T_0=T_1=0$

and the recursions

$$\begin{align} H_{n+1}=\frac{1}{2}+\frac{1}{2}T_n,\quad 0\le n\le19 \tag{1}\\[1em] T_{n+1}=\frac{1}{2}H_n+\frac{1}{2}T_n,\quad 0\le n\le19 \tag{2} \end{align}$$

From (1) and (2):

$$T_{n+2}=\frac{1}{4}+\frac{1}{2}T_{n+1}+\frac{1}{4}T_{n},\quad 0\le n\le18 \tag{3}$$

From (3) it can be seen that sequence $\{T\}$ converges to $1$, so tabulate $T_n$ and $\color{blue}{1-T_n}$ against $n$:

$$\begin{array}{c|c|c} n & T_n & 1-T_n \\ 0 & 0 & 1-\frac{1}{1}\\ 1 & 0 & 1-\frac{2}{2}\\ 2 & \frac{1}{4} & 1-\frac{3}{4} \\ 3 & \frac{3}{8} & 1-\frac{5}{8} \\ 4 & \frac{1}{2} & 1-\frac{8}{16} \\ 5 & \frac{19}{32} & 1-\frac{13}{32} \end{array}$$

The numerators in the last column are Fibonacci numbers and the denominators are powers of $2$. We can conjecture that:

$$T_n = 1-\frac{F_{n+2}}{2^n} \tag{4}$$

and prove by induction. Note that $F_1=F_2=1,F_3=2$ for this Fibonacci sequence.

Clearly, by (4) we have $T_0=T_1=0$. So assuming (4) as the induction hypothesis, for $n\ge2$, we have by (3):

$$\begin{align} T_{n+2}&=\frac{1}{4}+\frac{1}{2}T_{n+1}+\frac{1}{4}T_{n} \\[1em] &=\frac{1}{4}+\frac{1}{2}\left(1-\frac{F_{n+3}}{2^{n+1}}\right)+\frac{1}{4}\left(1-\frac{F_{n+2}}{2^{n}}\right) &(\text{by IH for }n,n+1)\\[1em] &=1-\frac{F_{n+3}}{2^{n+2}}-\frac{F_{n+2}}{2^{n+2}} &(\text{rearranging}) \\[1em] &=1-\frac{F_{n+4}}{2^{n+2}} &(\text{property of F.S.}) \end{align}$$

So this proves the IH for $n+2$ given IH for $n$ and $n+1$, hence proves the inductive step.

So we can compute the original probability as:

$$T_{20}=1-\frac{F_{22}}{2^{20}}$$

where

$$F_n = \frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n-\frac{1}{\sqrt5}\left(\frac{1-\sqrt5}{2}\right)^n$$

Then $F_{22}=17711$, so

$$\boxed{T_{20}=1-\frac{17711}{2^{20}}=1-\frac{17711}{1048576}}$$

$\endgroup$

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.