Markov Chain Properties - nakaly’s notes

In the previous post, I gave the definition of Markov chain and as you can see in the page that I introduced in the previous post, a Markov chain can be represented by a directed graph. Each node represents a state and each edge of the graph represents a probability from one state to another state.

f:id:nakaly:20170218030945p:plain:w200

Imagine that there are various directed graphs. It means that there are various Markov chains. To understand Markov chain more deeply, you want to categorise Markov chain by statistic characteristics.

One of the most important properties that represents Markov chain statistic characteristics is ergodicity. Before understanding ergodicity, there are some other properties that you need to understand.

Reducibility

A Markov chain is said to be irreducible if it is possible to get to any state from any state.

f:id:nakaly:20170218032246p:plain:w700

Transience and recurrence

When you are given a state of a Markov chain, if there is a non-zero probability that you will never return to the state, the state is said to be transient.

If a state is not transient, it’s said to be recurrent.

f:id:nakaly:20170218040341p:plain:w200

The state A is transient even though it has a self loop. There is a probability that you will return to A when you start from A. But you will never return to A once you go to the state B. B, C, D are recurrent.

If the expected return time of a state is finite, the state is said to be positive recurrent.

To understand an expected return time, we need to define the first return time of a state i.

$\displaystyle T_i = \inf \left\{ n\ge1: X_n = i \mid X_0 = i \right\}$

And we define the probability of the first return time after $n$ steps as follows:

$\displaystyle f_{ii}^{(n)} = P(T_i = n)$

Then we can define the expected return time $M_i$ as follows:

$\displaystyle M_i = \sum_{n=1}^{\infty} n\cdot f_{ii}^{(n)}$

Periodicity

When you are given a state of a Markov chain, if you return to the same state after a multiples of k steps, k is said to be the period of the state.

f:id:nakaly:20170218042209p:plain:w500

If a state has 1 period, the state is said to be aperiodic.

Ergodicity

If a state is aperiodic and positive recurrent, the state is said to be ergodic. If all states in an irreducible Markov chain are ergodic, the Markov chain is said to be ergodic.

Stationarity

One of the remarkable characteristics of a ergodic Markov chain is that a ergodic Markov chain has a stationary distribution.

It means that regardless of the initial state, the proportion of time the chain spends in a state is going to be converge to a finite value.

Let’s give a formal definition of a stationary distribution of Markov chain.

Let $p_{ij}$ is a probability of a transition from a state $i$ to another state $j$ .

A Markov chain can be represented by a transition matrix.

$P = (p_{ij}) =$

\begin{equation} \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1n} \\ p_{21} & p_{22} & \cdots & p_{2n} \\ \vdots & \vdots & p_{ij} & \vdots \\ p_{m1} & p_{m2} & \cdots & p_{mn} \end{bmatrix} \end{equation}

If a Markov chain is ergodic, there is a vector $\pi$ such as: