Communicating classes
A state i leads to state j, denoted i → j, if
P(xn = j for some n|x0 = i) > 0
This means that pijn > 0 for some n. Clearly
i → i
i → j and j → k implies i → k
A state i communicates with state j, denoted i ↔ j, provided i → j and j → i
i ↔ j is an equivalence relationship, i.e.
i ↔ i
if i ↔ j then j ↔ i
if i ↔ j and j ↔ k then i ↔ k
Thus, this relationship partitions the set of states S into communicating classes.
A communications class C is closed if it is not possible to leave that class, i.e.
if i ∈ C and i → j, then j ∈ C
A state i is absorbing provided {i} is a closed class, i.e. pii = 1.
A Markov chain is irreducible provided there is only one communications class, i.e. every state can communicate with every other state.
For any communications classes C and D, define C → D if there are states i in C and j in D such that i → j. Clearly,
if C → D and D → E, then C → E
if C → D and D → C, then C = D
Recurrent and transient states
In Hitting Probabilities, we define
ti = P(xn = i, n > 0|x0 = i)
A state i is recurrent if ti = 1 and transient if ti < 1.
As we will see in Property 4, if i ↔ j, then either both states are recurrent, or both are transient. Thus, we can extend the definition of recurrent and transient to communications classes. A communications class is recurrent if all (or any of) the states in that class are recurrent. The class is transient if all (or any of) the states in the class are transient.
Recurrent/transient properties
Property 1: Let Vi = {n: xn = i|x0 = i} and vi = the number of elements in Vi.
If i is a recurrent state, then
P(vi = ∞) = 1
If i is a transient state, then
vi ∼ Geom(1 – ti)
The geometric distribution is described in Negative Binomial and Geometric Distributions.
Proof: Suppose i is recurrent and x0 = i. Since i is recurrent, ti = 1, and so xn1 = i for some n1 > 0. But by the homogeneity property, this means there is an n2 > n1 such that xn2 = i. Similarly, we can find n3 > n2 such that xn3 = i. Etc.
Now suppose i is transient. Thus, vi is finite. Thus
P(vi = k ) = probability that i is returned to k times and then not hit again = tik(1 – ti)
If we view returning to i as failure and not returning as success, we have the situation modeled by the gamma distribution with p = 1 – ti. The expected value for vi is (1–p)/p = ti/(1–ti). If we include the initial hit of i, then the expected number of hits is 1/p = 1/(1–ti).
Property 2:
where vi is as defined in Property 1.
Proof: This follows by Property 2 of Markov Chain Basic Concepts, where n is replaced by ∞.
Property 3:
If i is recurrent, then
If i is transient, then
Proof: By Property 1, i is recurrent if and only if E[vi] = ∞. The result now follows from Property 2.
Property 4: If i ↔ j and i is recurrent, then j is recurrent
Proof: Since i → j and j → i, there are k and m such that
and so
By Property 3
Clearly, for any r > 0
Finally, we note that for any n, by the Chapman-Kolmogorov theorem (see Markov Chains Basic Concepts)
Putting all these pieces together, we get
Hence, by Property 3, j is recurrent.
Property 5: Every finite Markov chain has at least one recurrent state (and therefore at least one recurrent class).
Suppose the states of the Markov chain are S = {1, …, k} and assume there is no recurrent state. Thus, for each state i, there is a value mi such that xn ≠ i for any n > mi. Now set m = 1 + the largest of these mi. But xm = i for some state i, which is a contradiction since m > mi.
Closed class properties
Property 6: If C is a communications class that is not closed, then it is transient.
Proof: Since C is not closed, there are states i and j such that i in C, j not in C, and i → j. Thus, pij > 0. Suppose there is a k in C such that j → k. Thus, j → k ↔ i → j. Hence, j → k and k → j, and so k ↔ j, which would imply that j is in C, a contradiction.
This means that for any k in C, there is positive probability that k → j, but the Markov chain never returns to C. This means that the state is transient, and so the class C is transient.
Property 7: If C is a closed communications class in a Markov chain with a finite number of states, then it is recurrent.
Since C is closed, then once xn enters C it stays in C forever. Since there are only a finite number of states in C, some state i must be repeated an infinite number of times. Thus ti = 1, and so i is recurrent. Therefore, C is recurrent.
Property 8: Every finite Markov chain has at least one closed class
Proof: Follows from Properties 5 and 7.
Examples
Example 1: Identify the communications classes for the Markov chain with the transition matrix shown in Figure 1.
Figure 1 – Transition matrix
There are two communications classes {1, 2} and {3, 4}. The second of these is closed, while the first is not, since 2 → 3. 3 and 4 are recurrent, and 1 and 2 are transient.
Example 2: Identify the communication classes for a random walk Markov chain. Since i ↔ i+1 for any i, we see that any state communicates with any other state. Thus, there is only one communications class, and this chain is irreducible.
As we see in Random Walks, if p = .5, t0 = 1, and so 0 is recurrent. If, however, p ≠ .5, then t0 < 1, and so 0 is transient. By Property 4, if p = .5, then all states are recurrent; otherwise, they are all transient.
Examples Workbook
Click here to download the Excel workbook with the examples described on this webpage.
Links
References
Pishro-Nik, H. (2014) Classification of states. Introduction to probability, statistics, and random processes. Kappa Research.
https://www.probabilitycourse.com/chapter11/11_2_4_classification_of_states.php
Huang, Y. (2021) Classification of states. Introduction to Markov Chains
https://www.stat.uchicago.edu/~yibi/teaching/stat317/2021/Lectures/Lecture3.pdf
Aldridge, M. (2021) Class structure. Introduction to Markov Processes
https://mpaldridge.github.io/math2750/S07-classes.html
Norris, J. (2004) Discrete-time Markov chains. Cambridge University Press
https://www.statslab.cam.ac.uk/~jrn10//Markov/