# Probability to get the HHT sequence for the first time after n coin flip

Consider a coin that has the probability $p$ to give head and $1-p$ to give tail. I denote $H$ the event Head and $T$ the event Tail.

Let $A_n$ = "At the $n$-th flip, we get for the first time the sequence $HHT$" and $B_n$ = "At then $n$-th flip, we get the sequence $HHT$" be two events.

Finding a recurrence relation, determine the $\Bbb P(A_n)$.

I cannot find this recurrence relation.

What I tried : $$A_{n+3} = B_{n+3}\cap \bigcap_{i=3}^{n+2} \overline {B_i}$$ but it doesn't give anything interesting... I don't understand why is it suggested to use $B_n$ too.

Well maybe you've not seen this formalism yet but here's how I would solve your problem.

Let us introduce the following Markov Chain $(X_n)_{n>0}$ : at each step we follow where we are in the word "$HHT$", that is at $n=0$ set $X_0 = 0$. If the firt coin toss is Tail, then the word $HHT$ has not begun, and $X$ stays to 0. If the first coin toss is $H$ then the word $HHT$ we just have red the first letter of the word $HHT$ and hence go to state 1.

Once in state 1, if we read $T$ then we return to state 0, because we cannot form $HHT$ by starting our word by $HT..$. If we read $H$ we go to state 2. Here is the tricky part now : once in state 2, if we read $H$ we stay in state 2, because it is possible to form $HHT$ starting from $HH$. If we read $T$ of course we go to state 3 and then we kill our particule, because we are only interested in the first time it hits 3. Formally, we are considering the following Markov Chain.

Markov Chain

Now all we have to do is to remark $A_n = \{X_n = 3\}$, and to compute $\mathbb{P}_0(X_n = 3)$, which can be done by classical Markov chain arguments. More precisely, the transition matrix for the Markov chain is : $$P = \begin{pmatrix} p & 1-p & 0 & 0 & 0 \\ p & 0 & 1 - p & 0 & 0 \\ 0 & 0 & p & 1-p & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}$$ and all we want to do is to compute $P^n(0, 3)$. We could use algebraic arguments to compute $P^n$ but here we will use the Markov property.

$$\mathbb{P}_0(X_n = 3) = \mathbb{P}_0(X_n = 3 | X_1 = 0) \mathbb{P}_0(X_1= 0) + \mathbb{P}_0(X_n = 3 | X_1 = 1) \mathbb{P}_0(X_1 = 1)$$

We denote $p_n(x, y) = \mathbb{P}_x(X_n =y)$. Then after using the Markov property at time $n=1$ this equation becomes : $$p_n(0, 3) = p_{n-1}(0,3)(1-p) + p_{n-1}(1,3)p$$ By similar arguments we obtain :

$$p_{n-1}(1,3) = p_{n-2}(0,3)(1-p) + p_{n-2}(2,3)p \\$$ $$p_{n-2}(2,3) = p_{n-3}(2,3)p + p_{n-3}(3,3)(1-p) \\$$

Using $p_{n-3}(3,3) = 0$ for $n \geq 4$ (see our Markov chain description) and putting all things together we get :

$$p_n(0,3) = p_{n-1}(0,3)(1-p) + p(p_{n-2}(0,3)(1-p) + p^{n-2}(1-p)),$$

which we solve by induction.

• Thanks for this answer. I just don't understand what the "$x$ index" in $\Bbb P_x$ stands for? Jun 4, 2018 at 9:02
• It means that we start our Markov chain from the point $x$. Actually this whole Markov chain thing is not very important as long as you understand the ideas behind the decomposition of $P_0(X_n = 3)$ : you want to know, knowing that you started from 0, what is the probability to hit 3 at time $n$. First you look at the first step : which one could have it been ? To 0 or to 1 ? Etc... Another expression for $P_x(X_n = y)$ would be $P(X_n = y | X_0 = x)$. Is it more clear ? Jun 4, 2018 at 9:32
• Yeah it is! Thank you very much Jun 4, 2018 at 14:41