1
$\begingroup$

I have come across two different definitions for a 'irreducible set of states' of a Markov chain.

Definition 1: A subset of states $A$ of a Markov chain is irreducible if it is possible to access (in possibly more than one step) each state from the other.

Definition 2: A nonempty set of states $A$ is closed if $x \in A$ and $x \rightarrow y ~ \implies y \in A$. A closed set $A$ is irreducible if $A$ has no proper closed subset.

My question is the following:

(Q): If $A$ is a set of transient states that are accessible from each other, does it also mean $A$ is an irreducible set of states?

Why do i care?

The following is perturbation bounds paper for finite Markov chains. http://www.jstor.org/stable/3212261

The paper claims the perturbation bounds apply to two Markov chains if both of them have a 'single irreducible set of states which don't necessarily overlap'. Referring to (Q), if a Markov chain has a transient set of states that communicate with each other and another closed set of states that communicate with each other, does the Markov chain have a 'single' irreducible set of states or 'two' irreducible set of states?

Example:

$P = \begin{bmatrix} 0 & 1/2 & 0 & 1/6 & 1/6 & 1/6 \\ 0 & 0 & 1/2 & 1/6 & 1/6 &1/6 \\ 1/2 & 0 & 0 & 1/6 & 1/6 & 1/6 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \end{bmatrix}$

Does this Markov chain have a single irreducible set of states $\{4,5,6\}$ or two irreducible sets $\{1,2,3\}$ and $\{4,5,6\}$ ?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Terminologies sometimes differ, but I would go with Definition 1: at least, it is equivalent to the one used by Grimmett and Stirzaker. Definition 2 is not incorrect, but incomplete: this author, it seems, only talks about irreducible sets when they happen to be closed, and therefore chooses not to say what a non-closed irreducible set is.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Robert. So you think the perturbation bounds in the paper mentioned do not apply to Markov chains of the type that i have given as an example? $\endgroup$
    – Vedarun
    Commented Sep 17, 2014 at 8:47
0
$\begingroup$

The confusion arises because Definition 1 is not entirely correct. The correct version would be:

A closed subset of states A of a Markov chain is irreducible if it is possible to access (in possibly more than one step) each state from the other.

Essentially, the subset of states A forms a closed communicating class if it is irreducible and vice-versa.

For an extremely clear definition with lots of examples, ref to Section 9.5 (Irreducibility) of the book "Probability, Markov chains, Queues and Simulation" by William Stewart.

In your question if A is a set of transient states, then it is possible to escape to a state outside A (unless the Markov chain has infinite states) and thus for a finite Markov chain such a set of states would not be called irreducible. The paper by Schweitzer you have cited deals exclusively with finite Markov chains. The chain in your example has exactly one irreducible set of states {4,5,6}. The results in the paper do indeed apply to such a chain.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .