Communication Functions
These functions deal with the structure of the transition matrix. It identifies how classes communicate, whether they are recurrent or transient and what their periodicity is.
Contents
Index
DiscreteMarkovChains.canonical_form
DiscreteMarkovChains.communication_classes
DiscreteMarkovChains.decompose
DiscreteMarkovChains.periodicities
Documentation
DiscreteMarkovChains.communication_classes
— Functioncommunication_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.
DiscreteMarkovChains.periodicities
— Functionperiodicities(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.
DiscreteMarkovChains.decompose
— Functiondecompose(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])
DiscreteMarkovChains.canonical_form
— Functioncanonical_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.