# Markov Chain and Expectation

A coin with probability of heads p is being tossed repeatedly. Consider the 4 state Markov chain given by the results of the previous toss and the toss before that. Using Markov chain hitting time arguments, find the expected time we need to wait until we see two consecutive heads.

Can someone please help me with this question? I get confused when there are more than 2 states!

Thank you!

• Well, can you describe what the four states are?
– lulu
Nov 12, 2017 at 12:53
• To be clear, I personally do not see four states here. Perhaps they are considering "Start" and $T$ as distinct states (consider that a hint for setting up the states).
– lulu
Nov 12, 2017 at 13:08
• No...except for the End state you are only interested in the last toss. So I'd say the states were $\{\emptyset,H,End\}$. Here we note that $H$ precludes $HH=End.$ I can see where someone would prefer $\{Start, T, H,End\}$ but I think my way is simpler.
– lulu
Nov 12, 2017 at 13:11
• oh... so how can I link that to finding the expected time till I see 2 consecutive heads? Nov 12, 2017 at 13:13
• To think of it in a (very slightly) different way, I'd say that the states should count how many consecutive $H's$ you have in the running string. Thus another way to write my three states would be $\{0,1,2\}$.
– lulu
Nov 12, 2017 at 13:13

First note that the question should be closed for lack of context, but... since several users, in comments and even in an answer, misled the OP about the model or about the solution asked, here is the solution the statement of the problem is clearly pointing at.

So... we have a Markov chain, with state space $$S=\{HH,HT,TH,TT\}$$ and we are given that the four transitions $HH\to HH$, $HT\to TH$, $TH\to HH$ and $TT\to TH$ have probability $p$ each, that the four transitions $HH\to HT$, $HT\to TT$, $TH\to HT$ and $TT\to TT$ have probability $q=1-p$ each, and, consequently, that the other eight transitions are impossible.

This is a finite Markov chain, irreducible, and one is looking for $$t=t_{TT}$$ where $t_s$ denotes the mean hitting time of $s$, for every state $s$. (One could also compute $t_{HT}$, the result would be the same, the important thing is that no $H$ was just produced before starting.)

Now, the classical Markov one step recursion starting from $TT$ reads $$t=t_{TT}=1+pt_{TH}+qt_{TT}$$ thus one needs $t_{TH}$, but the classical Markov one step recursion starting from $TH$ reads $$t_{TH}=1+qt_{HT}$$ thus one needs $t_{HT}$, but the classical Markov one step recursion starting from $HT$ reads $$t_{HT}=1+pt_{TH}+qt_{TT}$$ Thus, as already mentioned, $$t_{HT}=t$$ and one is left with the $(t,t_{TH})$-system $$t=1+pt_{TH}+qt\qquad t_{TH}=1+qt$$ Solving it yields $$t=1+p(1+qt)+qt$$ that is, $$t=\frac{1+p}{1-pq-q}=\frac{1+p}{p^2}$$

Define three states $S_i$ for $i\in \{0,1,2\}$. Here the subscript $i$ denotes the number of consecutive $H's$ you have in the current run. Of course you are starting in $S_0$ and $S_2$ is the End state.

Let $E_i$ denote the expected number of tosses it will take from $S_i$. The answer to your question is $E_0$. Of course $E_2=0$.

Start in $S_0$. We consider the first toss. Either you get to $S_1$ by throwing $H$ (prob. $p$) or you stay in $S_0$ by throwing a $T$ (prob $1-p$). Thus $$E_0=p\times (E_1+1)+(1-p)\times (E_0+1)$$

Similarly $$E_1=p\times 1+ (1-p)\times (E_0+1)=1+(1-p)\times E_0$$

We want to solve for $E_0$ so we substitute to get $$E_0=p(2+(1-p)E_0)+(1-p)(E_0+1)$$ Which can be resolved to $$\boxed {E_0=\frac {1+p}{p^2}}$$

As a crude sanity check note that taking $p=1$ would give $E_0=2$ as it clearly should.

• wow thank you so much! this is so much clearer! much appreciated! thank you!! Nov 12, 2017 at 15:45
• As lum mentioned, do you think it is possible to do the question in 4 states? And not 3? Nov 13, 2017 at 8:41