A sequence of random variables $X_0,X_1,X_2,…$ taking values in the state space ${1,2,…,M}$ is called Markov Chain, the event $X_i+1$ only influenced by $X_i$
$$P(X_{n+1}=j|X_n = i,X_{n-1}=i_{n-1},…,X_0=i_0) = P(X_{n+1}=j|X_n=i)$$

Let $X_0,X_1,X_2,…$ be a Markov Chain with state space ${1,2,…,M}$, and let
$q_{ij} = P(X_{n+1}=j|X_N=i)$ be the transition probability from state $i$ to state $j$. The $M times M$ matrix $Q=(q_{ij})$ is called transition matrix of the chain.

The n-step transition probability from $i$ to $j$ is the probability of being at $j$ exactly $n$ steps after being at $i$. Denote this by $q^{(n)}_{ij}$
$$q^{(n)}_{ij} = P(X_n=j|X_0=i)=sum_{kin S} q^{(1)}_{kj} q^{(n-1)}_{ik}$$
which implies
$$Q^n = Q^{n-1}cdot Q$$

$$q_{ij}^{(n+m)} = sum_{kin S} q^{(n)}_{ik} q^{(m)}_{kj}$$

This problem can be formulated as a 3-state markov chain

The Transition graph is equivalent to

Let $e_s = E[text{waiting time for HH|initial state = s}]$, then we have
$$begin{align}
e_{Null} &= frac{1}{2} (1+e_{Null})+frac{1}{2} (1+e_H) \
e_H &= frac{1}{2} (1+e_{HH}) + frac{1}{2} (1+e_{Null})\
e_{HH} &= 0
end{align}$$

Let see a more complicate case , this can be done by establish a linear equation

• Recurrent State $i$ of Markov chain have the probability of $1$ eventually return to $i$
• Transient Other-wise, the state is Transient

• Irreducible any state $i$ and $j$, possible to go from $i$ to $j$ in a finite number of steps.
• Reducible not irreducible

In an irreducible Markov Chain with a finite state space, all states are recurrent

We want to collect all $C$ types coupons, Let $X_n$ be the number of distinct coupon types in our collection after $n$ attempts. Then $X_0,X_1,…$ is a Markov Chain on the state space ${ 0,1,…,C }$

The period of state $i$ in a markov chain is the gcd of the possible numbers of steps can return to $i$ when starting at $i$. A state is called aperiodic if its period equals 1, and periodic otherwise.

.