Skip to main content
added 46 characters in body
Source Link

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$A$ is closed if x∈A$x \in A$ and x→y implies y∈A$x \rightarrow y ~ \implies y \in A$. A closed set A$A$ is irreducible if A$A$ has no proper closed subset.

My question is the following:

(Q): If A$A$ is a set of transient states that are accessible from each other, does it also mean A$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}$\{4,5,6\}$ or two irreducible sets {1,2,3}$\{1,2,3\}$ and {4,5,6}$\{4,5,6\}$ ?

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∈A and x→y implies y∈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} ?

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\}$ ?

Source Link

Does a irreducible set of states necessarily need to be closed in a Markov chain?

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∈A and x→y implies y∈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} ?