8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What's the intuition about "accessibility"? I don't understand why having a conditional probability makes something "accessible"? $\endgroup$ – mavavilj Dec 10 '15 at 8:20
  • $\begingroup$ 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). $\endgroup$ – nmerci Dec 10 '15 at 8:28
8
$\begingroup$

Here are three examples 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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is the $n$ in $p_{ij}^n$ a power or an index? $\endgroup$ – mavavilj Dec 10 '15 at 10:29
  • $\begingroup$ 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). $\endgroup$ – nmerci Dec 10 '15 at 12:32
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How do you define "can go from state $i$ to state $j$"? $\endgroup$ – mavavilj Dec 10 '15 at 10:26
  • 1
    $\begingroup$ You really need to ask your teacher. He's not going to eat you, you know. $\endgroup$ – titus Dec 14 '15 at 10:17
  • $\begingroup$ 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? $\endgroup$ – Hunle Nov 8 '18 at 7:35
  • $\begingroup$ I am referring to the matrix exponential $\endgroup$ – titus Mar 12 at 21:02
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.