Communication Functions

communication_classes(x)

Definitions

A state $j$ is accessible from state $i$ if it is possible to eventually reach state $j$ given that the process started in state $i$. That is, $∃ \, t ∈ \mathbb{N}$ such that $p^{(t)}_{i,j} > 0$.

States $i$ and $j$ communicate if $i$ is accessible from $j$ and $j$ is accessible from $i$.

A communication class is the set of states in a Markov chain that are all accessible from one another. Communication classes form a class in the mathematical sense. They also form a partition of the state space.

A state $i$ is recurrent if the process is guarenteed to eventually return to state $i$ given that the process started in state $i$. If a state $i$ is not recurrent, then it is said to be transient.

Arguments

• x: some kind of Markov chain.

Returns

A tuple containing 2 arrays.

• This first array contains C arrays which store the states that communicate.
• The second array is an array of Bool where the ith value is true if the ith communication class is recurrent.

Examples

using DiscreteMarkovChains
T = [
    1 0;
    0 1;
]
X = DiscreteMarkovChain(T)

communication_classes(X)

# output

([[1], [2]], Any[true, true])

So the Markov chain has two communication classes and both are recurrent.

T = [
    .5 .5 .0;
    .2 .8 .0;
    .1 .2 .7;
]
X = DiscreteMarkovChain(["Sunny", "Cloudy", "Rainy"], T)

communication_classes(X)

# output

([["Sunny", "Cloudy"], ["Rainy"]], Any[true, false])

So the Sunny and Cloudy states communicate and are recurrent. The Rainy state is transient. Note that this is not a very good weather model since once it stops raining, it will never rain again.

periodicities(x::AbstractDiscreteMarkovChain)

A more advanced version of communication_classes designed for discrete Markov chains. It is the same as communication_classes but it returns periodicities as well.

Definitions

The period, $d_i$ of a state $i$ is the greatest common denominator of all integers $n ∈ \mathbb{N}$ for which $p^{(n)}_{i,i} > 0$. Written more succinctly,

\[d_i = \text{gcd}\{ n ∈ \mathbb{N} | p^{(n)}_{i,i} > 0 \}\]

If $d_i=1$ then state $i$ is said to be aperiodic.

Arguments

• x: some kind of discrete Markov chain.

Returns

A tuple containing 3 arrays.

• This first array contains C arrays which store the states that communicate.
• The second array is an array of Bool where the ith value is true if the ith communication class is recurrent.
• The third array is the periodicity of each communication class.

Examples

using DiscreteMarkovChains
T = [
    1 0;
    0 1;
]
X = DiscreteMarkovChain(T)

periodicities(X)

# output

([[1], [2]], Any[true, true], Any[1, 1])

So the Markov chain has two communication classes and both are recurrent and aperiodic.

T = [
    0.0 1.0 0.0;
    1.0 0.0 0.0;
    0.1 0.2 0.7;
]
X = DiscreteMarkovChain(["Sunny", "Cloudy", "Rainy"], T)

periodicities(X)

# output

([["Sunny", "Cloudy"], ["Rainy"]], Any[true, false], Any[2, 1])

So the Sunny and Cloudy states communicate and are recurrent with period 2. The Rainy state is transient and aperiodic. Note that this is not a very good weather model since once it stops raining, it will never rain again. Also, each day after that, the process will oscillate between Sunny and Cloudy.

decompose(x)

All transition matrices can be reordered so that we have

\[T = \begin{pmatrix} A & 0\\ B & C \end{pmatrix}\]

Where $A$, $B$ and $C$ are as described below. $0$ is a matrix of zeros.

Arguments

• x: some kind of Markov chain.

Returns

A tuple of four values

• states: the first value is an array of the new states.
• A: the second value is a matrix of recurrent states to recurrent states.
• B: the third value is a matrix of transient states to recurrent states.
• C: the fourth value is a matrix of transient to transient states.

Examples

using DiscreteMarkovChains
T = [
    0.0 1.0 0.0;
    1.0 0.0 0.0;
    0.1 0.2 0.7;
]
X = DiscreteMarkovChain(["Sunny", "Cloudy", "Rainy"], T)

decompose(X)

# output

(Any["Sunny", "Cloudy", "Rainy"], [0.0 1.0; 1.0 0.0], [0.1 0.2], [0.7])

canonical_form(x)

Reorders the states of the transition matrix of x so that recurrent states appear first and transient states appear last.

Arguments

• x: some kind of Markov chain.

Returns

A tuple with the new states and the new transition matrix.

Examples

We will use the same matrix as previous examples but change the order of it.

using DiscreteMarkovChains
T = [
    0.7 0.2 0.1;
    0.0 0.0 1.0;
    0.0 1.0 0.0;
]
X = DiscreteMarkovChain(["Rainy", "Cloudy", "Sunny"], T)

canonical_form(X)

# output

(Any["Cloudy", "Sunny", "Rainy"], [0.0 1.0 0.0; 1.0 0.0 0.0; 0.2 0.1 0.7])

Here, Cloudy and Sunny are recurrent states so they appear first. Rainy is a transient state so it appears last.