# How do you see a Markov chain is irreducible?

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?

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.

• What's the intuition about "accessibility"? I don't understand why having a conditional probability makes something "accessible"? Dec 10, 2015 at 8:20
• You may look from the inaccessibility point. The state $j$ is said to be inaccessible from $i$ if there is no chance to get there from $i$, that is for any number of steps $n$ the probability of this event remains $0$. To make definition of accessibility one should switch the quantors, i.e. $\forall$ to $\exists$ and $=0$ to $\neq 0$ (which is the same as $>0$, since probability is positive). Dec 10, 2015 at 8:28

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.

• A Markov state that does not transition to other states is also known as an absorbing state (I have also heard the term sink state): en.wikipedia.org/wiki/Absorbing_Markov_chain Nov 5 at 11:10

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.

• Is the $n$ in $p_{ij}^n$ a power or an index? Dec 10, 2015 at 10:29
• It's an index. However, it has an interpretation: if $\mathbf P=(p_{ij})$ be a transition probability matrix, then $p_{ij}^n$ is the $ij$-th element of $\mathbf P^n$ (here $n$ is a power). Dec 10, 2015 at 12:32
• what is irreducible and aperiodic Markov chain? Why we need both to ensure ergodicity? Could you give an example of a non-ergodic but irreducible but aperiodic Markov chain? Feb 12, 2021 at 15:58

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.

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.

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

• How do you define "can go from state $i$ to state $j$"? Dec 10, 2015 at 10:26
• You really need to ask your teacher. He's not going to eat you, you know. Dec 14, 2015 at 10:17
• when you use exp(P) you are referring ot the matrix exponential? or $e^{P_{ij}}$, where i, j is the ij term of the matrix P? Nov 8, 2018 at 7:35
• I am referring to the matrix exponential Mar 12, 2019 at 21:02