I have set up the following model:
Let $X_n$ be the number of heads in the $n$-th toss and $P(X_0=0)=1$. I can calculate the transition matrix $P$. Define $$ T=\min\{n\geq 0\mid X_n=5\}. $$ Then $P(X=1)=P(X_{T-1}=4)$. Noting that $X_n$ is a Markov chain and defining $$ u_i=P(X_{T-1}=4\mid X_0=i) $$ we have $$ u_i=\sum_{j=0}^5P(X_{T-1}=4\mid X_1=j)\cdot P_{ij}. $$ I ended up with $u_0=0$ which seems nonsense.
[Edited:]What is wrong with my model?Would anybody come up with a better one?
[Added:] Here is possibly where I get the calculation wrong:
$$ P(X_{T-1}=4\mid X_1=i)=u_i $$ and $u_5=0$.
[Last Update:] What is wrong is $$ P(X_{T-1}=4\mid X_1=4)=u_4. $$ One should get $P(X_{T-1}=4\mid X_1=4)=1$ instead.
$\endgroup$ 12 Answers
$\begingroup$It might simplify slightly to say we just require the chain to reach state $4$ at any point, starting at $0$, and we can forget about the variable $T$. So re-define $u_i$ as
$$u_i = P(X_n = 4 \text{ for some $n$}\mid X_0=i).$$
Our transition probability matrix:
$$ \begin{matrix} \qquad 0 \qquad & 1 \qquad & 2 \qquad & 3 \quad & 4 \qquad & 5 \\ \end{matrix} \\ P = \begin{bmatrix} 1/32 & 5/32 & 10/32 & 10/32 & 5/32 & 1/32 \\ 0 & 1/16 & 4/16 & 6/16 & 4/16 & 1/16 \\ 0 & 0 & 1/8 & 3/8 & 3/8 & 1/8 \\ 0 & 0 & 0 & 1/4 & 1/2 & 1/4 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} $$
The values for $u_i$ can be calculated in turn, using first-step analysis, until we get the required value, $u_0$:
\begin{align} u_3 &= \frac{1}{4}u_3 + \frac{1}{2} \\ \therefore\quad u_3 &= \frac{2}{3} \\ & \\ u_2 &= \frac{1}{8}u_2 + \frac{3}{8}u_3 + \frac{3}{8} \\ \therefore\quad u_2 &= \frac{5}{7} \\ & \\ u_1 &= \frac{1}{16}u_1 + \frac{1}{4}u_2 + \frac{3}{8}u_3 + \frac{1}{4} \\ \therefore\quad u_1 &= \frac{76}{105} \\ & \\ u_0 &= \frac{1}{32}u_0 + \frac{5}{32}u_1 + \frac{5}{16}u_2 + \frac{5}{16}u_3 + \frac{5}{32} \\ \therefore\quad u_0 &= \frac{157}{217}. \end{align}
$\endgroup$ 2 $\begingroup$Personally I would use a graph rather than a transition matrix.
The first graph here corresponds to your transition matrix, with the blue numbers representing the number of coins to toss in the next round and the green numbers of probability of moving to the next state.
But you are not interested in tosses which are all tails, i.e. do not change the state. So in the second graph, the green numbers are the probabilities of what happens if you change state, which are similar to those before but with slightly different denominators.
The brown numbers in the second graph are the probability of visiting a particular state, so the answer to $\mathbb{P}(X=1)$ is $\dfrac{157}{217}\times 1 = \dfrac{157}{217}\approx 0.7235$.
For what it is worth,
- $\mathbb{P}(X=2)=\dfrac{118}{217}\times \dfrac{1}{3} = \dfrac{118}{651}\approx 0.1813$,
- $\mathbb{P}(X=3)=\dfrac{34}{93}\times \dfrac{1}{7} = \dfrac{34}{651}\approx 0.0522$,
- $\mathbb{P}(X=4)=\dfrac{5}{31}\times \dfrac{1}{15} = \dfrac{1}{93}\approx 0.0108$,
- $\mathbb{P}(X=5)=1\times \dfrac{1}{31} = \dfrac{1}{31}\approx 0.0323$,
- $E[X]=\dfrac{314}{217}\approx 1.4470$.
