Markov Chain State Classification: Recurrence and Transience
Markov Chain State Classification: Recurrence and Transience
Definition of First-Passage Probability ()
(read as "rho x y") represents the probability that, starting in state in a Markov chain, you will hit state for the first time in a finite amount of time.
This is a crucial distinction from a simple one-step transition probability ().
is the probability of going from state to state in one step.
considers the probability of reaching eventually for the first time, over any number of steps , such that .
The concept of addresses the question: "What is the probability that the time it takes to first hit state (starting from state ) is finite?"
Classifying States: Recurrent vs. Transient
States in a Markov chain can be classified into two fundamental types based on their return probabilities, specifically .
Recurrent States
Definition: A state is said to be recurrent if and only if the probability of returning to state (starting from ) in a finite amount of time is .
Mathematically: .
Intuition: If a state is recurrent, it means that once you visit that state, you are guaranteed to return to it again (with probability 1). Consequently, a recurrent state will be visited infinitely often over the long run.
Transient States
Definition: A state is said to be transient if and only if the probability of returning to state (starting from ) in a finite amount of time is less than .
Mathematically: .
Intuition: If a state is transient, there is a positive probability () that you will never return to that state after leaving it. This implies that a transient state will be visited only a finite number of times, after which the chain will eventually leave the state permanently.
Analogy: The term "transient" evokes the image of someone passing through a place and not settling down, similar to a homeless person moving from one location to another and not necessarily returning. In a Markov chain, a transient state is one you might visit, but there's a chance you'll eventually leave it for good.
Example 1: Two-State Markov Chain with an Absorbing State
Consider a simple two-state Markov chain with states 0 and 1, and the following transition probabilities:
From State 0: ,
From State 1: ,
In this example, state 1 is an absorbing state because once you enter it, you can never leave.
Classifying State 1 ()
is the probability of starting at state 1 and returning to state 1 for the first time in finite time.
We sum the probabilities of returning at time .
Time : To return to 1 in one step, you must transition from 1 to 1. The probability is .
Time : To return to 1 for the first time in two steps, you would have to leave 1 at step 1 and then return at step 2. However, since , you must return to 1 in one step. Thus, the probability of returning for the first time at is .
Time : Similarly, the probabilities for returning for the first time at any are all .
Calculation: .
Conclusion: Since , state 1 is recurrent.
Classifying State 0 ()
is the probability of starting at state 0 and returning to state 0 for the first time in finite time.
We sum the probabilities of returning at time .
Time : To return to 0 in one step, you must transition from 0 to 0. The probability is .
Time : To return to 0 for the first time in two steps, you must leave 0 at step 1 and then return to 0 at step 2. The only way to leave 0 is to go to 1 (with probability ). However, once you are in state 1, you can never return to state 0 (since ). Therefore, the probability of first returning to 0 at is .
Time : For the same reason, the probabilities for returning for the first time at any are all .
Calculation: .
Conclusion: Since , state 0 is transient.
This example illustrates that a single Markov chain can have both recurrent and transient states.
Example 2: Two-State Markov Chain with Mutual Accessibility
Consider another two-state Markov chain (states 0 and 1) with the following transition probabilities:
From State 0: ,
From State 1: ,
Classifying State 1 ()
is the probability of starting at state 1 and returning to state 1 for the first time in finite time.
We sum the probabilities of first return at each time step , i.e., , where is the first return time to state 1.
: Direct loop from 1 to 1. Probability is .
for : To return to 1 for the first time at step , you must:
Leave state 1 for state 0 (probability ).
Stay in state 0 for steps (probability ).
Return to state 1 from state 0 (probability ).
So, for : .
Calculation: We can write as a sum: Let . Then the sum starts at . The summation is a geometric series for . Here, .
Substitute this back:Conclusion: Since , state 1 is recurrent.
Classifying State 0 ()
is the probability of starting at state 0 and returning to state 0 for the first time in finite time.
We sum the probabilities of first return at each time step , i.e., , where is the first return time to state 0.
: Direct loop from 0 to 0. Probability is .
for : To return to 0 for the first time at step , you must:
Leave state 0 for state 1 (probability ).
Stay in state 1 for steps (probability ).
Return to state 0 from state 1 (probability ).
So, for : .
Calculation: We can write as a sum: Let . Then the sum starts at . The summation is a geometric series with .
Substitute this back:Conclusion: Since , state 0 is recurrent.
In this example, both states in the Markov chain are recurrent.
Important Theorems for Recurrence and Transience
These theorems provide powerful tools for classifying states without always needing to perform the extensive geometric series calculations.
Theorem 1: Existence of at least one Recurrent State in Finite Markov Chains
Statement: Every finite-state Markov chain has at least one recurrent state.
Implication: If you have a Markov chain with a finite number of states, it's impossible for all its states to be transient.
Intuition (Proof by Contradiction):
Assume, for the sake of contradiction, that all states in a finite-state Markov chain are transient.
If a state is transient, there's a positive probability that you will eventually leave it and never return. This means each state is visited only a finite number of times.
If you start at any state and eventually leave it, and this applies to all states, then after a sufficiently long time, you would have left all states permanently.
However, in a finite-state Markov chain, you must exist in some state at all times. You cannot simply disappear from the state space.
This leads to a contradiction: you must be in a state, but if all states are transient, you can't be in any state permanently. Therefore, at least one state must eventually lead back to itself infinitely often, meaning it must be recurrent.
Theorem 2: Recurrence as a Class Property
Statement: If state is recurrent, and state leads to state (meaning there is a positive probability of eventually getting from to in some finite number of steps), then state is also recurrent.
Notation: " " means that .
Implication: This theorem connects the recurrence property between states. If two states are mutually accessible (i.e., meaning and ), and one of them is recurrent, then the other must also be recurrent. This extends to entire communication classes: all states in a single communication class are either all recurrent or all transient.
Intuition (Pseudo-Proof):
Suppose is recurrent. This means you return to infinitely often.
Suppose , meaning there's a positive probability of eventually reaching from . (Given that you're in , you also return to with probability 1, and eventually you'll exit and have another chance to get to ).
Since you return to infinitely often, and from each visit to there's a chance to go to , you will necessarily visit infinitely often.
For to be recurrent, you also need to show that if you are in , you can return to . Since leads to and is recurrent, it implies that once you reach , you eventually transition from back to (which is part of the path to making recurrent) and then from back to . This continuous cycle ensures that is also visited infinitely often and will eventually return to itself.
Application: In Example 2 above, we saw that both states 0 and 1 were recurrent. This could have been deduced more quickly:
By Theorem 1, at least one state (either 0 or 1) must be recurrent.
From state 0, you can reach state 1 (via ).
From state 1, you can reach state 0 (via ).
Since 0 and 1 are mutually accessible, if just one of them is recurrent (guaranteed by Theorem 1), then the other must also be recurrent by Theorem 2. Therefore, both states 0 and 1 are recurrent.
These theorems often simplify the classification of states in finite Markov chains, especially when states form connected components.