Proving Positive Recurrence of States in Finite Markov Chains with Doubly Stochastic Transition Matrices

Understanding the properties of finite Markov chains with doubly stochastic transition matrices is crucial in various applications, from computer science to statistical physics. In this article, we will delve into the proof of positive recurrence of all states in such chains. This topic is not only theoretically interesting but also has practical implications in modeling various systems.

Definitions

A doubly stochastic matrix is a matrix ( P ) where all entries are non-negative and the sum of each row and each column equals 1. A state ( i ) in a Markov chain is positive recurrent if the expected return time to state ( i ) is finite.

Steps to Prove Positive Recurrence

1. Finite State Space: Consider a finite Markov chain with state space ( S {1, 2, ldots, n} ), where ( n ) is finite.

2. Uniform Stationary Distribution: Since the transition matrix ( P ) is doubly stochastic, it has a stationary distribution given by ( pi_i frac{1}{n} ) for all ( i in S ). This implies a uniform probability distribution across all states.

3. Existence of a Stationary Distribution: The existence of a stationary distribution guarantees that the system will eventually reach a steady state, where the probabilities remain consistent over time.

4. Recurrence: A Markov chain is recurrent if starting from any state there is a probability of 1 that the chain will eventually return to that state. For a doubly stochastic matrix, every state communicates with every other state, implying that the chain is irreducible.

5. Finite State Space and Recurrence: In a finite state space, if the Markov chain is irreducible, it is also recurrent. Therefore, all states are recurrent.

Positive Recurrence

Positive recurrence can be established by demonstrating that the expected return time to any state ( i ) is finite. Specifically, for a finite state space and a uniform stationary distribution, the expected return time to any state ( i ) is given by:

[ E[T_i] frac{1}{pi_i} n ]

Since ( n ) is finite, ( E[T_i]

Conclusion

Thus, we conclude that all states of a finite Markov chain with a doubly stochastic transition matrix are positive recurrent because:

The chain is irreducible due to the doubly stochastic nature. The finite state space ensures recurrence. The expected return time to any state is finite, confirming positive recurrence.

Summary

All states of a finite Markov chain with a doubly stochastic transition matrix are positive recurrent because they are irreducible, recurrent, and have finite expected return times.

Keywords

Doubly Stochastic Matrix, Finite Markov Chains, Positive Recurrence