Markov chain long run probabilities

Question

So I want to find the long run probability of getting two heads in a row when flipping a fair coin many times. I know this answer should be 1/6 (expected number of flips to get 2H in a row is 6) but I'm trying to figure out how to use a Markov chain to solve this.

I think my transition matrix should be (3x3):

    0H 1H 2H
0H  .5 .5  0
1H  .5  0  .5
2H  0   0  1

Then I come up with a system of equations to find the limiting distribution.

.5x1 + .5x2 = x1
.5x1 = x2
.5x2 + .5x3 = x3
x1 + x2 + x3 = 1

But I can't seem to solve this equation correctly. Is my transition matrix/ approach correct?

Answer 1

The response above by Xi'an addresses a different question than the one you are asking, I believe. He answers the question of the probability of 'HH' in a given pair of flips. This is slightly different than flipping until you get two heads in a row since the sequence 'THHT' would not register as two heads in a row in his MC.

You were very close to having the correct Markov chain, but your problem is with your last row. You have '0 0 1' which would correspond to going from a state where you have 2 heads in a row back to the same state. What you really want to do is immediately start a new sequence of flips to find another instance of 'HH' in a row. The new transition matrix would be

$$ A=\left( \begin{matrix} 0.5 &0.5 &0\\ 0.5 &0 &0.5 \\ 0.5 &0.5 &0\end{matrix}\right)\,. $$

as the first flip after reaching the state for two heads in a row will either be a tail meaning you are back to no heads or a head meaning that you have one head in a row in your new string of flips. As you were hoping for, the stationary distribution (easily checkable) is (1/2 1/3 1/6), giving 1/6 as the probability of being in the '2 heads' state.

---

In response to Xi'an's comment:

The goal is to perform experiments where we flip a fair coin repeatedly until two heads are flipped in a row. When that experiment ends you repeat it. We want to calculate the expected number of flips required to witness two heads in a row. One way to do this is to construct a Markov chain where one state (in this case, the third state, or '2H' as the original poster put it) which the MC enters only when the second coin is flipped and is in another state when the rest are flipped. That way, the long-run (stationary) probability of being in the state should correspond to one over the expected value of the number of flips required to get two heads in a row (1/6).

For the 'HTTHTTTHTHHTH' sequence you mentioned, the state sequence would be '1001000101201'. Where the number represents the number of consecutive heads. A trickier example would be 'THHHTHHT' which would have state sequence '01210120'. The first coin is tails so we are in the 0H state, then after the second is heads, we enter 1H and then 2H. This is the end of the first 'experiment' since we've observed two heads in a row. Subsequently, a new experiment begins. The first flip is heads, so we go right from the 2H state to the 1H state.

Answer 2

Your analysis is almost correct, but you made a mistake in the Markov construction: first, you need four states, not three, because $(H,T)$ is not the same as $(T,H)$: the former cannot be followed by $(H,H$). (And you confuse the probability of seeing $(H,H)$ in the sequence of flips with the number of flips required to reach $(H,H)$ for the first time, for which the Markov approach does not help...). So if we rank the states as $(T,T)$, $(H,T)$, $(T,H)$, and $(H,H)$, the transition matrix is $$ A=\left( \begin{matrix} 0.5 &0 &0.5 &0\\ 0.5 &0 &0.5 &0\\ 0 &0.5 &0 &0.5\\ 0 &0.5 &0 &0.5\end{matrix}\right)\,. $$ The stationary vector is then (unsurprisingly) $(1/4,1/4,1/4,1/4)$.