How do you see a Markov chain is irreducible?

Question

I have some trouble understanding the Markov chain property irreducible.

Irreducible is said to mean that the stochastic process can "go from any state to any state".

But what defines whether it can go from state $i$ to state $j$, or cannot go?

---

The wikipedia page gives the formalisation:

State $j$ is accessible (written $i\rightarrow j$) from state $i$, if exists integer $n_{ij}>0$ s.t. $$P(X_{n_{ij}}=j\space |\space X_0=i)=p_{ij}^{(n_{ij})} >0$$

then communicating is if $i\rightarrow j$ and $j \rightarrow i$.

From these irreducibility follows somehow.

Answer 1

Here are three examples (taken from Greenberg, Introduction to Bayesian Econometrics, if I remember correctly) for transition matrices, the first two for the reducible case, the last for the irreducible one.

\begin{eqnarray*} P_1 &=& \left( \begin{array}{cccc} 0.5 & 0.5 & 0 & 0 \\ 0.9 & 0.1 & 0 & 0 \\ 0 & 0 & 0.2 & 0.8 \\ 0 & 0 & 0.7 & 0.3 \end{array} \right) \\\\ P_2 &=& \left( \begin{array}{cccc} 0.1 & 0.1 & 0.4 & 0.4 \\ 0.5 & 0.1 & 0.1 & 0.3 \\ 0.2 & 0.4 & 0.2 & 0.2 \\ 0 & 0 & 0 & 1% \end{array} \right) \end{eqnarray*} For $P_1$, when you are in state 3 or 4, you will stay there, and the same for states 1 and 2. There is no way to get from state 1 to state 3 or 4, for example.

For $P_2$, you can get to any state from states 1 to 3, but once you are in state 4, you will stay there. $$P_3=\left( \begin{array}{cccccc} 0.5 & 0.5 & 0 & 0 & 0 & 0 \\ 0.9 & 0 & 0 & 0 & 0 & 0.1 \\ 0 & 0 & 0 & 0.8 & 0 & 0.2 \\ 0.7 & 0 & 0.1 & 0 & 0.2 & 0 \\ 0 & 0 & 0 & 0.1 & 0.9 & 0 \\ 0.9 & 0 & 0 & 0 & 0.1 & 0% \end{array} \right)$$ For this example, you may start in any state and can still reach any other state, although not necessarily in one step.

Answer 2

The state $j$ is said to be accessible from a state $i$ (usually denoted by $i \to j$) if there exists some $n\geq 0$ such that: $$p^n_{ij}=\mathbb P(X_n=j\mid X_0=i) > 0$$ That is, one can get from the state $i$ to the state $j$ in $n$ steps with probability $p^n_{ij}$.

If both $i\to j$ and $j\to i$ hold true then the states $i$ and $j$ communicate (usually denoted by $i\leftrightarrow j$). Therefore, the Markov chain is irreducible if each two states communicate.

Answer 3

Some of the existing answers seem to be incorrect to me.

As cited in Stochastic Processes by J. Medhi (page 79, edition 4), a Markov chain is irreducible if it does not contain any proper 'closed' subset other than the state space.

So if in your transition probability matrix, there is a subset of states such that you cannot 'reach' (or access) any other states apart from those states, then the Markov chain is reducible. Otherwise the Markov chain is irreducible.

Answer 4

Let $i$ and $j$ be two distinct states of a Markov Chain. If there is some positive probability for the process to go from state $i$ to state $j$, whatever be the number of steps(say 1, 2, 3$\cdots$), then we say that state $j$ is accessible from state $i$.

Notationally, we express this as $i\rightarrow j$. In terms of probability, it is expressed as follows: a state $j$ is accessible from state $i$, if there exists an integer $m>0$ such that $p_{ij}^{(m)}>0$.

Similarly, we say that, $j\rightarrow i$, if there exists an integer $n>0$ such that $p_{ji}^{(n)}>0$.

Now, if both $i\rightarrow j$ and $j\rightarrow i$ are true, then we say that the states $i$ and $j$ communicate with each other, and is notationally expressed as $i \leftrightarrow j$. In terms of probability, this means that, there exists two integers $m>0,\;\; n>0$ such that $p_{ij}^{(m)}>0$ and $p_{ji}^{(n)}>0$.

If all the states in the Markov Chain belong to one closed communicating class, then the chain is called an irreducible Markov chain. Irreducibility is a property of the chain.

In an irreducible Markov Chain, the process can go from any state to any state, whatever be the number of steps it requires.

Answer 5

First a word of warning : never look at a matrix unless you have a serious reason to do so : the only one I can think of is checking for mistakenly typed digits, or reading in a textbook.

If $P$ is your transition matrix, compute $\exp(P)$. If all entries are nonzero, then the matrix is irreducible. Otherwise, it's reducible. If $P$ is too large, compute $P^n$ with $n$ as large as you can. Same test, slightly less accurate.

Irreducibility means : you can go from any state to any other state in a finite number of steps.

In Christoph Hanck's example $P_3$, you can't go directly from state 1 to state 6, but you can go 1 -> 2 -> 6