# 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`

— Function`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.

`DiscreteMarkovChains.periodicities`

— Function`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.

`DiscreteMarkovChains.decompose`

— Function`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])
```

`DiscreteMarkovChains.canonical_form`

— Function`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.