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!
Best Answer
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}$$