Markov chain

Memoryless

The probability of which state a random process will be in the future is independent of any state experienced in the past, and if a random process satisfies this property, it is a Markov chain.

one step transition probability

Contingent probability

$$P\{X_{t+1}=j|X_t=i\}$$

This is called the probability of the Markov chain moving from $i$ to $j$ in one step at time $t$, that is, the probability of the chain moving to $j$ at time $t$.

When this probability is independent of $t$, the Markov chain is said to have a smooth transition probability, denoted as $p_{ij}$​. Markov chains with stationary transition probability are called time-Zimmarkov chains.

Since the Markov chain must transition to some definite state, the sum of the one-step transition probabilities of all states is 1:

$$\sum _{j=0}^{\mathrm{\infty }}{p}_{ij}=1$$

By arranging all the step transition probabilities into a square matrix, we get the transition probability matrix:

$$\left[\begin{array}{ccccc}{p}_{00}& p_{01}& \cdots & p_{0j}& \cdots \\ p_{10}& p_{11}& \cdots & p_{1j}& \cdots \\ ⋮& ⋮& & ⋮\\ p_{i0}& p_{i1}& \cdots & p_{ij}& \cdots \\ ⋮& ⋮& & ⋮\end{array}\right]$$

Multistep transition probability

Contingent probability

$$p_{ij}(t,t+n)=P\{X_{t+n}=j|X_t=i\}$$

It is called the transition probability of Markov chain $X_t$ reaching state $j$ after $n$ steps at time $t$ in state $i$.

If $X_t$ is time-homogeneous, then $p_{ij}(t,t+n)$ is independent of $t$, and $p_{ij}(t,t+n)$ is denoted as $p_{ij}(n)$ and the corresponding n-step transition probability matrix $p_{ij}(n)$ is denoted as $Pn$.

The multistep transition probability can also be approximated by experiment and Kolmogorov-Chapman equation:

$$p_{ij}(n+m)=\sum _{k=0}^{\mathrm{\infty }}{p}_{ik}(n)p_{kj}(m)i,j=0,1,2,...$$

Written in moment form:

$$P(n+m)=P(n)P(m)$$$$P(n)=PP(n-1)=P^n$$

In other words, the n-step transition probability matrix is one step transition probability matrix to the $n^{th}$ power.

Ergodicity

What happens to the transition probability as the number of steps goes to infinity?

For the general two-state Markov chain:

$$P=\left[\begin{array}{cc}1-a& a\\ b& a-b\end{array}\right](0<a,b<1)$$

The n-step transition probability can be calculated:

$$P(n)=P^n=\left[\begin{array}{cc}{p}_{00}(n)& p_{01}(n)\\ p_{10}(n)& p_{11}(n)\end{array}\right]$$$$=\frac{1}{a+b}\left[\begin{array}{cc}b& a\\ b& a\end{array}\right]+\frac{(1-a-b{)}^n}{a+b}\left[\begin{array}{cc}a& -a\\ -b& b\end{array}\right],n=1,2,...$$

Then the n-step transition probability has a limit:

$$li{m}_{n\to \mathrm{\infty }}{p}_{00}(n)=li{m}_{n\to \mathrm{\infty }}{p}_{10}(n)=\frac{b}{a+b}denotedas{\pi }_0,$$$$li{m}_{n\to \mathrm{\infty }}{p}_{01}(n)=li{m}_{n\to \mathrm{\infty }}{p}_{11}(n)=\frac{a}{a+b}denotedas{\pi }_1$$

That is to say, for a particular state $j$, no matter when the chain starts, the probability of reaching the state $j$ after a long transition is close to ${\pi }_j$​, which is ergodic.

Limiting distribution

Since ${\pi }_0+{\pi }_1=1$, they form a distribution law

$$({\pi }_0,{\pi }_1)=\pi$$

which is the limiting distribution of the chain.

If we can find a positive integer $m$ such that the m-step transition probability matrix $P_m$ has no zero element, we can say that the chain is traversal.