I was reading the material and I am confused at the following example.
Q: In a sequence of independent flips of a fair coin, let N denote the
number of flips until there is a run of three consecutive heads. Find $P(N = 8)$.
ANS: Another way to determine P(N = 8) is to consider a Markov chain with states
0, 1, 2, 3, 4 where, as before, for i < 3 state i means that we currently are on a run
of i consecutive heads, state 3 means that the first run of size 3 has just occurred,
and state 4 that a run of size 3 occurred in the past. That is, this Markov chain has
transition probability matrix
$Q=\begin{matrix} 1/2&1/2&0&0&0\\1/2&0&1/2&0&0\\1/2&0&0&1/2&0\\0&0&0&0&1\\0&0&0&0&1 \end{matrix}$
P(N=8)=$Q^8_{0,3}$
*Confusion: I am wondering what is the state 4? Can I say state 4 is the probability of getting three consecutive heads when we flip the coin 8 times? (State 3 is the until we flip the coin 8 times?)
Best Answer
Here, state 4 is needed to sort out the difference between "the third heads just happened" and "the third head happened before now". The probability that it takes 8 flips to get 3 heads in a row is the probability the process is in state 3 just after the 8th flip (that is, the third heads happened on the 8th flip). Notice, if the state is 4 just after the 8th flip, the 3rd heads happened sometime before the 8th flip. We don't want to count this in the probability it takes exactly 8 flips.
Notice that the process enters state 4 after it is in state 3 no matter what the outcome of the flip is. State 4 is what's known as an "absorbing state". Once the process reaches state 4, it stays there forever.
I was curious about the answer. I get $\frac{13}{256}\approx 0.05$