Finding the transition matrix of a Markov chain and classifying it's states. A man tosses a fair coin until $3$ heads occur in a row.
Let $X_n=k$ if at the $n$-th trial, the last tail occurred at the $(n-k)$-th trial;
i.e., $X_n$  denotes the longest string of heads ending at the nth trial.
Find the transition matrix and classify the states.
 A: Note that $X_n=0\iff n-\text{th toss comes up with tails}$, hence $$P_{k,0}=\mathbb{P}(X_{n+1}=0\vert X_n=k)=\frac{1}{2}$$
Note that $X_n$ increases by one when $n$-th toss comes up with heads, hence $$P_{k,k+1}=\mathbb{P}(X_{n+1}=k+1\vert X_n=k)=\frac{1}{2}$$
When $X_n=3$ the game ends, thus $k=3$ is an absorbing state $$P_{3,k}=\mathbb{P}(X_{n+1}=k\vert X_n=3)=\delta_{3,k}$$
Let's fill in the transition matrix $P=(P_{h,k})$ for $h,k\in\{0,1,2,3\}$
$$\begin{pmatrix} 1/2 &1/2 &0 &0\\
1/2 &0 &1/2 &0 \\
1/2 &0 &0 &1/2  \\
0 &0 &0 &1\\
\end{pmatrix}
$$
Note that the variables $X_1, X_2$ can not be included in the chain because it is not true that $\mathbb{P}(X_2=3\vert X_1=2)=P_{2,3}=1/2$. But, formally, we can say that the process $\{X_n\}_{n\geq3}$ is a Markov chain with starting
distribution $\lambda$ and trnsition matrix $P$, where $\lambda$ is the law of $X_3$.
Let's find $\lambda$: if $ABC$ are the first three tosses, we have
$X_3=0\iff ABC\in\{CCC,CTC,TCC,TTC\}$
$X_3=1\iff ABC\in\{CCT,TCT\}$
$X_3=2\iff ABC\in\{CTT\}$
$X_3=3\iff ABC\in\{TTT\}$
Hence $\lambda=(4/8, 2/8, 1/8, 1/8)$
Let's classify the states: $k=3$ is an absorbing state, thus $C_1=\{3\}$ is a closed communicating class. Note that $$0\to1\to2\to0$$ thus $C_2=\{0,1,2\}$ is a communicating class, but it is not closed since $2\to3$ and $3\not\to 2$.
