Markov Chain State Classification: Recurrence and Transience

Markov Chain State Classification: Recurrence and Transience

Definition of First-Passage Probability (ρxy\rho_{xy})

  • ρxy\rho_{xy} (read as "rho x y") represents the probability that, starting in state xx in a Markov chain, you will hit state yy for the first time in a finite amount of time.

  • This is a crucial distinction from a simple one-step transition probability (PxyP_{xy}).

    • PxyP_{xy} is the probability of going from state xx to state yy in one step.

    • ρxy\rho_{xy} considers the probability of reaching yy eventually for the first time, over any number of steps (t≥1)(t \ge 1), such that t<∞t < \infty.

  • The concept of ρxy\rho_{xy} addresses the question: "What is the probability that the time it takes to first hit state yy (starting from state xx) 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 ρxx\rho_{xx}.

Recurrent States
  • Definition: A state xx is said to be recurrent if and only if the probability of returning to state xx (starting from xx) in a finite amount of time is 11.

    • Mathematically: ρxx=1\rho_{xx} = 1.

  • 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 xx is said to be transient if and only if the probability of returning to state xx (starting from xx) in a finite amount of time is less than 11.

    • Mathematically: ρxx<1\rho_{xx} < 1.

  • Intuition: If a state is transient, there is a positive probability (1−ρxx>01 - \rho_{xx} > 0) 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: P<em>00=0.5P<em>{00} = 0.5, P</em>01=0.5P</em>{01} = 0.5

  • From State 1: P<em>11=1.0P<em>{11} = 1.0, P</em>10=0.0P</em>{10} = 0.0

In this example, state 1 is an absorbing state because once you enter it, you can never leave.

Classifying State 1 (ρ11\rho_{11})
  • ρ11\rho_{11} 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 t=1,t=2,t=3,…t=1, t=2, t=3, \ldots.

    • Time t=1t=1: To return to 1 in one step, you must transition from 1 to 1. The probability is P11=1P_{11} = 1.

    • Time t=2t=2: 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 P11=1P_{11} = 1, you must return to 1 in one step. Thus, the probability of returning for the first time at t=2t=2 is 00.

    • Time t>2t > 2: Similarly, the probabilities for returning for the first time at any t>1t > 1 are all 00.

  • Calculation: ρ<em>11=P(T</em>1=1)+P(T<em>1=2)+P(T</em>1=3)+…=1+0+0+…=1\rho<em>{11} = P(T</em>1 = 1) + P(T<em>1 = 2) + P(T</em>1 = 3) + \ldots = 1 + 0 + 0 + \ldots = 1.

  • Conclusion: Since ρ11=1\rho_{11} = 1, state 1 is recurrent.

Classifying State 0 (ρ00\rho_{00})
  • ρ00\rho_{00} 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 t=1,t=2,t=3,…t=1, t=2, t=3, \ldots.

    • Time t=1t=1: To return to 0 in one step, you must transition from 0 to 0. The probability is P00=0.5P_{00} = 0.5.

    • Time t=2t=2: 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 P<em>01=0.5P<em>{01} = 0.5). However, once you are in state 1, you can never return to state 0 (since P</em>10=0P</em>{10} = 0). Therefore, the probability of first returning to 0 at t=2t=2 is 00.

    • Time t>2t > 2: For the same reason, the probabilities for returning for the first time at any t>1t > 1 are all 00.

  • Calculation: ρ<em>00=P(T</em>0=1)+P(T<em>0=2)+P(T</em>0=3)+…=0.5+0+0+…=0.5\rho<em>{00} = P(T</em>0 = 1) + P(T<em>0 = 2) + P(T</em>0 = 3) + \ldots = 0.5 + 0 + 0 + \ldots = 0.5.

  • Conclusion: Since ρ00=0.5<1\rho_{00} = 0.5 < 1, 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: P<em>00=2/3P<em>{00} = 2/3, P</em>01=1/3P</em>{01} = 1/3

  • From State 1: P<em>11=1/4P<em>{11} = 1/4, P</em>10=3/4P</em>{10} = 3/4

Classifying State 1 (ρ11\rho_{11})
  • ρ11\rho_{11} 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 k≥1k \ge 1, i.e., ρ<em>11=∑</em>k=1∞P(T<em>1=k)\rho<em>{11} = \sum</em>{k=1}^{\infty} P(T<em>1 = k), where T</em>1T</em>1 is the first return time to state 1.

    • P(T<em>1=1)P(T<em>1 = 1): Direct loop from 1 to 1. Probability is P</em>11=1/4P</em>{11} = 1/4.

    • P(T1=k)P(T_1 = k) for k≥2k \ge 2: To return to 1 for the first time at step kk, you must:

      1. Leave state 1 for state 0 (probability P10=3/4P_{10} = 3/4).

      2. Stay in state 0 for k−2k-2 steps (probability P00k−2=(2/3)k−2P_{00}^{k-2} = (2/3)^{k-2}).

      3. Return to state 1 from state 0 (probability P01=1/3P_{01} = 1/3).

      • So, for k≥2k \ge 2: P(T<em>1=k)=P</em>10×P<em>00k−2×P</em>01=(3/4)×(2/3)k−2×(1/3)P(T<em>1 = k) = P</em>{10} \times P<em>{00}^{k-2} \times P</em>{01} = (3/4) \times (2/3)^{k-2} \times (1/3).

  • Calculation: We can write ρ<em>11\rho<em>{11} as a sum: ρ</em>11=P(T<em>1=1)+∑</em>k=2∞P(T<em>1=k)\rho</em>{11} = P(T<em>1 = 1) + \sum</em>{k=2}^{\infty} P(T<em>1 = k) ρ</em>11=1/4+∑<em>k=2∞(3/4)(2/3)k−2(1/3)\rho</em>{11} = 1/4 + \sum<em>{k=2}^{\infty} (3/4)(2/3)^{k-2}(1/3) Let j=k−2j = k-2. Then the sum starts at j=0j=0. ρ</em>11=1/4+(3/4)(1/3)∑<em>j=0∞(2/3)j\rho</em>{11} = 1/4 + (3/4)(1/3) \sum<em>{j=0}^{\infty} (2/3)^j ρ</em>11=1/4+(1/4)∑<em>j=0∞(2/3)j\rho</em>{11} = 1/4 + (1/4) \sum<em>{j=0}^{\infty} (2/3)^j The summation is a geometric series ∑</em>j=0∞rj=11−r\sum</em>{j=0}^{\infty} r^j = \frac{1}{1-r} for ∣r∣<1|r|<1. Here, r=2/3r = 2/3.
    ∑<em>j=0∞(2/3)j=11−2/3=11/3=3\sum<em>{j=0}^{\infty} (2/3)^j = \frac{1}{1 - 2/3} = \frac{1}{1/3} = 3 Substitute this back: ρ</em>11=1/4+(1/4)×3=1/4+3/4=1\rho</em>{11} = 1/4 + (1/4) \times 3 = 1/4 + 3/4 = 1

  • Conclusion: Since ρ11=1\rho_{11} = 1, state 1 is recurrent.

Classifying State 0 (ρ00\rho_{00})
  • ρ00\rho_{00} 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 k≥1k \ge 1, i.e., ρ<em>00=∑</em>k=1∞P(T<em>0=k)\rho<em>{00} = \sum</em>{k=1}^{\infty} P(T<em>0 = k), where T</em>0T</em>0 is the first return time to state 0.

    • P(T<em>0=1)P(T<em>0 = 1): Direct loop from 0 to 0. Probability is P</em>00=2/3P</em>{00} = 2/3.

    • P(T0=k)P(T_0 = k) for k≥2k \ge 2: To return to 0 for the first time at step kk, you must:

      1. Leave state 0 for state 1 (probability P01=1/3P_{01} = 1/3).

      2. Stay in state 1 for k−2k-2 steps (probability P11k−2=(1/4)k−2P_{11}^{k-2} = (1/4)^{k-2}).

      3. Return to state 0 from state 1 (probability P10=3/4P_{10} = 3/4).

      • So, for k≥2k \ge 2: P(T<em>0=k)=P</em>01×P<em>11k−2×P</em>10=(1/3)×(1/4)k−2×(3/4)P(T<em>0 = k) = P</em>{01} \times P<em>{11}^{k-2} \times P</em>{10} = (1/3) \times (1/4)^{k-2} \times (3/4).

  • Calculation: We can write ρ<em>00\rho<em>{00} as a sum: ρ</em>00=P(T<em>0=1)+∑</em>k=2∞P(T<em>0=k)\rho</em>{00} = P(T<em>0 = 1) + \sum</em>{k=2}^{\infty} P(T<em>0 = k) ρ</em>00=2/3+∑<em>k=2∞(1/3)(1/4)k−2(3/4)\rho</em>{00} = 2/3 + \sum<em>{k=2}^{\infty} (1/3)(1/4)^{k-2}(3/4) Let j=k−2j = k-2. Then the sum starts at j=0j=0. ρ</em>00=2/3+(1/3)(3/4)∑<em>j=0∞(1/4)j\rho</em>{00} = 2/3 + (1/3)(3/4) \sum<em>{j=0}^{\infty} (1/4)^j ρ</em>00=2/3+(1/4)∑<em>j=0∞(1/4)j\rho</em>{00} = 2/3 + (1/4) \sum<em>{j=0}^{\infty} (1/4)^j The summation is a geometric series with r=1/4r = 1/4. ∑</em>j=0∞(1/4)j=11−1/4=13/4=4/3\sum</em>{j=0}^{\infty} (1/4)^j = \frac{1}{1 - 1/4} = \frac{1}{3/4} = 4/3
    Substitute this back:
    ρ00=2/3+(1/4)×(4/3)=2/3+1/3=1\rho_{00} = 2/3 + (1/4) \times (4/3) = 2/3 + 1/3 = 1

  • Conclusion: Since ρ00=1\rho_{00} = 1, 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 XX is recurrent, and state XX leads to state YY (meaning there is a positive probability of eventually getting from XX to YY in some finite number of steps), then state YY is also recurrent.

    • Notation: "X→YX \to Y " means that ρxy>0\rho_{xy} > 0.

  • Implication: This theorem connects the recurrence property between states. If two states are mutually accessible (i.e., X↔YX \leftrightarrow Y meaning X→YX \to Y and Y→XY \to X), 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 XX is recurrent. This means you return to XX infinitely often.

    • Suppose X→YX \to Y, meaning there's a positive probability of eventually reaching YY from XX. (Given that you're in XX, you also return to XX with probability 1, and eventually you'll exit XX and have another chance to get to YY).

    • Since you return to XX infinitely often, and from each visit to XX there's a chance to go to YY, you will necessarily visit YY infinitely often.

    • For YY to be recurrent, you also need to show that if you are in YY, you can return to YY. Since XX leads to YY and XX is recurrent, it implies that once you reach YY, you eventually transition from YY back to XX (which is part of the path to making XX recurrent) and then from XX back to YY. This continuous cycle ensures that YY 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:

    1. By Theorem 1, at least one state (either 0 or 1) must be recurrent.

    2. From state 0, you can reach state 1 (via P01=1/3P_{01} = 1/3).

    3. From state 1, you can reach state 0 (via P10=3/4P_{10} = 3/4).

    4. 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.