5.4 Stationary distributions

Stationary distributions are crucial in understanding the long-term behavior of stochastic processes. They represent the equilibrium state of a system, where the probability of being in each state remains constant over time. This concept is fundamental in analyzing Markov chains and their applications.

In Markov chains, stationary distributions satisfy the equation πP = π, where P is the transition matrix. They provide insights into the system's stability and help predict its long-run behavior. Understanding stationary distributions is essential for various applications, from queueing theory to web page ranking algorithms.

Definition of stationary distributions

• A stationary distribution is a probability distribution over the states of a stochastic process that remains unchanged over time
• It represents the long-run behavior of the process, indicating the proportion of time the process spends in each state
• In the context of Markov chains, a stationary distribution is a row vector $\pi$ that satisfies the equation $\pi P = \pi$, where $P$ is the transition probability matrix

Properties of stationary distributions

Invariance under state transitions

Top images from around the web for Invariance under state transitions

• 

  How to draw state diagram for first order Markov chain for 10000bases from 2 chromosomes ... View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

• 

  Hidden Markov Model View original

  Is this image relevant?

• 

  How to draw state diagram for first order Markov chain for 10000bases from 2 chromosomes ... View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

1 of 3

Top images from around the web for Invariance under state transitions

• 

  How to draw state diagram for first order Markov chain for 10000bases from 2 chromosomes ... View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

• 

  Hidden Markov Model View original

  Is this image relevant?

• 

  How to draw state diagram for first order Markov chain for 10000bases from 2 chromosomes ... View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

1 of 3

• A key property of stationary distributions is their invariance under state transitions
• If a Markov chain starts in a stationary distribution, it will remain in that distribution after any number of transitions
• Mathematically, if $\pi$ is a stationary distribution and $P$ is the transition probability matrix, then $\pi P^n = \pi$ for all $n \geq 0$

Uniqueness of stationary distributions

• Under certain conditions, a Markov chain has a unique stationary distribution
• If a Markov chain is irreducible and aperiodic, then it has a unique stationary distribution
• Uniqueness implies that the long-run behavior of the chain is independent of the initial state distribution

Existence of stationary distributions

Irreducible Markov chains

• An irreducible Markov chain is one in which all states communicate with each other
• In other words, it is possible to reach any state from any other state in a finite number of steps
• Irreducibility is a necessary condition for the existence of a stationary distribution

Aperiodic Markov chains

• A state in a Markov chain is aperiodic if the greatest common divisor of the return times to that state is 1
• A Markov chain is aperiodic if all its states are aperiodic
• Aperiodicity, along with irreducibility, guarantees the existence of a unique stationary distribution

Positive recurrent states

• A state in a Markov chain is positive recurrent if the expected return time to that state is finite
• In an irreducible Markov chain, all states are either positive recurrent or null recurrent
• Positive recurrence is a sufficient condition for the existence of a stationary distribution

Computation of stationary distributions

Solving balance equations

• One method to compute the stationary distribution is by solving the balance equations
• The balance equations state that the total probability flow into a state must equal the total probability flow out of that state
• For a Markov chain with $n$ states, the balance equations form a system of $n$ linear equations, which can be solved to obtain the stationary distribution

Power method for approximation

• The power method is an iterative algorithm for approximating the stationary distribution
• It involves repeatedly multiplying an initial probability distribution by the transition probability matrix until convergence
• The power method is particularly useful when the state space is large, and solving the balance equations becomes computationally expensive

Limiting distributions vs stationary distributions

Convergence to stationary distributions

• A limiting distribution is the probability distribution that a Markov chain approaches as the number of transitions tends to infinity
• If a Markov chain has a unique stationary distribution, then the limiting distribution exists and is equal to the stationary distribution
• Convergence to the stationary distribution occurs regardless of the initial state distribution

Conditions for convergence

• For a Markov chain to converge to its stationary distribution, it must be irreducible and aperiodic
• Irreducibility ensures that the chain can reach any state from any other state, preventing the existence of absorbing states or closed communicating classes
• Aperiodicity prevents the chain from getting stuck in cycles, allowing it to settle into a stable long-run distribution

Applications of stationary distributions

Queueing theory

• Stationary distributions play a crucial role in queueing theory, which studies the behavior of waiting lines or queues
• In a stable queueing system, the stationary distribution represents the long-run probabilities of the system being in various states (e.g., number of customers in the queue)
• Queueing models, such as the M/M/1 queue, rely on stationary distributions to derive performance measures like average queue length and waiting time

PageRank algorithm

• The PageRank algorithm, used by search engines like Google, employs stationary distributions to rank web pages
• It models web surfing as a Markov chain, where states represent web pages, and transitions represent clicking on links
• The stationary distribution of this Markov chain assigns a PageRank score to each web page, indicating its importance or relevance

Thermodynamic equilibrium

• In statistical mechanics, stationary distributions are used to describe the equilibrium state of a system
• The Boltzmann distribution, which gives the probability of a system being in a particular microstate, is a stationary distribution
• At thermodynamic equilibrium, the system's macroscopic properties (e.g., temperature, pressure) remain constant over time, corresponding to the invariance property of stationary distributions