1

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!

Your Dad
  • 41
  • Well, can you describe what the four states are? – lulu Nov 12 '17 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 '17 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 '17 at 13:11
  • oh... so how can I link that to finding the expected time till I see 2 consecutive heads? – Your Dad Nov 12 '17 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 '17 at 13:13
  • As you said, it's a Markov chain. Standard techniques apply. Write out the transition probabilities and solve. Three by three is easier than four by four so I'd go with my description. – lulu Nov 12 '17 at 13:14
  • sorry I don't quite understand because there is no condition here. like for example- if I toss heads, I'll toss tails the next time – Your Dad Nov 12 '17 at 13:15
  • Not following. That would be a transition probability of $1$. Here, state $0$ could stay at state $0$ or go to state $1$ (probability $\frac 12$ either way) and so on. – lulu Nov 12 '17 at 13:16
  • Oh, sorry...you said it comes up Heads with probability $p$. So, then state $0$ goes to state $1$ with probability $p$ and stays at state $0$ with probability $1-p$. – lulu Nov 12 '17 at 13:17
  • hmm... meaning the expected time can range from 1 to infinity? – Your Dad Nov 12 '17 at 13:17
  • How could it be $1$? – lulu Nov 12 '17 at 13:17
  • Have you ever seen a Markov chain calculation before? There's nothing at all unusual about this example. – lulu Nov 12 '17 at 13:18
  • sorry I meant 2! – Your Dad Nov 12 '17 at 13:18
  • yes I've been doing it but this question stumbles me... – Your Dad Nov 12 '17 at 13:19
  • it'll be great if you can help me out with the solution so I can understand better! – Your Dad Nov 12 '17 at 13:19
  • So, try again. Letting $E_i$ denote the expected time it will take from state $i\in {0,1,2}$ we see that you want $E_0$. But considering the first toss we see that $E_0=p\times (E_1+1)+(1-p)\times (E_0+1)$. Write out a similar equation for $E_1$ and solve for $E_0$. Note, of course, that $E_2=0$. – lulu Nov 12 '17 at 13:20
  • I have given you very heavy hints here. Try to work it out from those. – lulu Nov 12 '17 at 13:21
  • ahh okay I'll try! thank you so much! – Your Dad Nov 12 '17 at 13:22
  • is it possible if you provide with me step by step? I still am confused as of how I should start... – Your Dad Nov 12 '17 at 13:36
  • I'll post something below. – lulu Nov 12 '17 at 13:38

2 Answers2

3

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}$$

Did
  • 279,727
1

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.

lulu
  • 70,402