Waiting for Heads – Markov Chains

Some time ago, we analytically estimated the expected waiting times of sequences HT and HH from coin-flipping games. Today, we calculate them using Markov chains.

Waiting time for HT

First, the notations, followed by the transition matrix:

\begin{bmatrix} 0.0 & 0.0 & 0.0 & 0.0\\ 0.5 & 0.5 & 0.5 & 0.0\\ 0.5 & 0.0 & 0.5 & 0.0\\ 0.0 & 0.5 & 0.0 & 1.0 \end{bmatrix}

Get Q, I – Q and its inverse 

AA <- matrix(c(0.0, 0.5, 0.5,
               0.0, 0.5, 0.0,
               0.0, 0.5, 0.5), nrow = 3)

II <- matrix(c(1, 0, 0,
               0, 1, 0,
               0, 0, 1), nrow = 3)
BB <- II - AA

CC <- solve(BB)

NN <- c(1, 1, 1)
NN%*%CC
 4    2    4

The average waiting time from 0 to HT is the first element in the vector, i.e., 4.

Waiting time for HH

\begin{bmatrix} 0.0 & 0.0 & 0.0 & 0.0\\ 0.5 & 0.0 & 0.5 & 0.0\\ 0.5 & 0.5 & 0.5 & 0.0\\ 0.0 & 0.5 & 0.0 & 1.0 \end{bmatrix}

AA <- matrix(c(0.0, 0.5, 0.5,
               0.0, 0.0, 0.5,
               0.0, 0.5, 0.5), nrow = 3)

II <- matrix(c(1, 0, 0,
               0, 1, 0,
               0, 0, 1), nrow = 3)
BB <- II - AA

CC <- solve(BB)

NN <- c(1, 1, 1)
NN%*%CC
 6    4    6

The waiting time is 6.

Related Posts