6.4 Stationary distributions
6 min read•august 20, 2024
Stationary distributions are key to understanding Markov chains' long-term behavior. They represent the equilibrium state where probabilities remain constant over time. By analyzing stationary distributions, we can predict a system's steady-state performance and make informed decisions.
Computation methods like solving or using eigenvectors help find stationary distributions. These distributions have important properties, such as invariance under the and representing long-run proportions of time in each state. Examples in birth-death processes, random walks, and queueing models illustrate their practical applications.
Definition of stationary distributions
- A is a probability distribution that remains unchanged over time in a Markov chain or stochastic process
- Represents the long-run behavior of the system, where the probabilities of being in each state remain constant
- Formally, a distribution is stationary if it satisfies the equation , where is the transition matrix of the Markov chain
- This means that if the system starts in the stationary distribution, it will remain in that distribution at all future time steps
Existence and uniqueness
- The existence of a stationary distribution depends on the properties of the Markov chain
- Irreducible: It is possible to reach any state from any other state in a finite number of steps
- Aperiodic: The chain does not have a periodic structure, meaning it does not return to certain states at fixed intervals
- If a Markov chain is both irreducible and aperiodic, it is guaranteed to have a unique stationary distribution
- In some cases, a Markov chain may have multiple stationary distributions or no stationary distribution at all
Relationship to limiting distributions
- The of a Markov chain describes the long-run behavior of the system when starting from any initial distribution
- If a unique stationary distribution exists, the limiting distribution will converge to the stationary distribution regardless of the initial state
- The stationary distribution can be thought of as the equilibrium state of the system, while the limiting distribution represents the convergence to that equilibrium over time
Computation methods
Solving balance equations
Top images from around the web for Solving balance equations
Markov chain - Wikipedia View original
Is this image relevant?
markov chains - Balance Equations for M/M/1/m Queue - Mathematics Stack Exchange View original
Is this image relevant?
matlab - Ergodic Markov chain stationary distribution: solving eqns - Stack Overflow View original
Is this image relevant?
Markov chain - Wikipedia View original
Is this image relevant?
markov chains - Balance Equations for M/M/1/m Queue - Mathematics Stack Exchange View original
Is this image relevant?
1 of 3
Top images from around the web for Solving balance equations
Markov chain - Wikipedia View original
Is this image relevant?
markov chains - Balance Equations for M/M/1/m Queue - Mathematics Stack Exchange View original
Is this image relevant?
matlab - Ergodic Markov chain stationary distribution: solving eqns - Stack Overflow View original
Is this image relevant?
Markov chain - Wikipedia View original
Is this image relevant?
markov chains - Balance Equations for M/M/1/m Queue - Mathematics Stack Exchange View original
Is this image relevant?
1 of 3
- Balance equations, also known as steady-state equations, can be used to find the stationary distribution of a Markov chain
- The balance equations state that the total probability flow into each state must equal the total probability flow out of that state
- To solve for the stationary distribution, set up a system of linear equations based on the balance equations and the normalization condition (i.e., the probabilities must sum to 1)
- Solving this system of equations yields the stationary distribution
Using eigenvectors of transition matrix
- The stationary distribution can also be computed using the eigenvectors of the transition matrix
- The stationary distribution corresponds to the left eigenvector of the transition matrix associated with the eigenvalue 1
- To find the stationary distribution:
- Compute the eigenvalues and left eigenvectors of the transition matrix
- Identify the eigenvector corresponding to the eigenvalue 1
- Normalize the eigenvector so that its entries sum to 1, yielding the stationary distribution
Properties
Invariance under Markov chain
- The stationary distribution is invariant under the action of the Markov chain
- If the system starts in the stationary distribution, the distribution of states will remain the same at each subsequent time step
- This property is a consequence of the definition of the stationary distribution, which satisfies
Long-run proportion of time in each state
- The stationary distribution has an important interpretation in terms of the long-run behavior of the Markov chain
- The entries of the stationary distribution vector represent the proportion of time the system spends in each state over the long run
- Specifically, is the long-run proportion of time the system spends in state , regardless of the initial state
Examples
Birth-death processes
- Birth-death processes are a class of Markov chains used to model population dynamics, queueing systems, and other applications
- In a , the system can only transition between adjacent states, representing births and deaths (or arrivals and departures)
- The stationary distribution of a birth-death process can be found using the balance equations, which take into account the birth and death rates at each state
Random walks
- Random walks are stochastic processes where the system moves randomly between states according to certain transition probabilities
- Examples include the simple on a line or a graph, where the system moves to neighboring states with equal probability
- The stationary distribution of a random walk depends on the structure of the state space and the transition probabilities
- For a simple random walk on a finite line with reflecting boundaries, the stationary distribution is uniform
Queueing models
- Queueing models describe systems where customers arrive, wait in a queue, and are served by one or more servers
- Common queueing models include M/M/1 (single server with Poisson arrivals and exponential service times) and M/M/c (multiple servers)
- The stationary distribution of a queueing model represents the long-run distribution of the number of customers in the system
- For an M/M/1 queue, the stationary distribution is geometric, with the probability of having customers in the system decreasing exponentially with
Applications
Steady-state behavior of systems
- Stationary distributions are crucial for understanding the steady-state behavior of systems modeled by Markov chains
- In many applications, such as queueing systems, inventory management, and population dynamics, the long-run behavior is of primary interest
- By analyzing the stationary distribution, one can determine key performance measures, such as the average number of customers in a queue or the long-run proportion of time a machine is idle
Ergodicity and convergence
- Ergodicity is a property of Markov chains that ensures the long-run behavior of the system is independent of the initial state
- If a Markov chain is ergodic (i.e., irreducible and aperiodic), it will converge to its unique stationary distribution over time
- This convergence property is essential for the practical application of Markov chains, as it allows for the estimation of long-run averages and the design of efficient simulation algorithms
Simulation and sampling techniques
- Stationary distributions play a key role in the design and analysis of simulation and sampling techniques for Markov chains
- Markov chain Monte Carlo (MCMC) methods, such as the Metropolis-Hastings algorithm and Gibbs sampling, rely on constructing a Markov chain with a desired stationary distribution
- By running the Markov chain for a sufficient number of steps, samples from the stationary distribution can be obtained, enabling the estimation of various quantities of interest
Stationary distributions vs limiting distributions
- While stationary and limiting distributions are closely related, they are distinct concepts
- A stationary distribution is a probability distribution that remains invariant under the action of the Markov chain
- If the system starts in the stationary distribution, it will remain in that distribution at all future time steps
- A limiting distribution, on the other hand, describes the long-run behavior of the Markov chain when starting from any initial distribution
- If a unique stationary distribution exists, the limiting distribution will converge to the stationary distribution over time
- In some cases, a Markov chain may have a limiting distribution but no stationary distribution, or vice versa
Extensions and generalizations
Quasi-stationary distributions
- Quasi-stationary distributions are a generalization of stationary distributions for Markov chains with absorbing states
- In a Markov chain with absorbing states, the system will eventually reach an absorbing state and remain there forever
- A describes the long-run behavior of the system conditional on not being absorbed
- It represents the distribution of states the system visits before absorption, given that it has not yet been absorbed
Stationary distributions in continuous time
- The concept of stationary distributions can be extended to (CTMCs)
- In a CTMC, the system evolves continuously over time, with transitions occurring according to exponentially distributed holding times
- The stationary distribution of a CTMC satisfies the global balance equations, which are analogous to the balance equations in discrete-time Markov chains
- The global balance equations state that the total rate of flow into each state must equal the total rate of flow out of that state
- Computing the stationary distribution of a CTMC involves solving a system of linear equations based on the global balance equations and the normalization condition
Key Terms to Review (19)
Aperiodicity: Aperiodicity refers to the property of a stochastic process where the system does not exhibit regular cycles or patterns in its state transitions. This means that the return times to a particular state can vary, allowing for greater flexibility in the long-term behavior of the process. Aperiodicity is crucial when analyzing stationary distributions, absorption probabilities, and ergodic behavior, as it ensures that the system can eventually explore all states over time without being trapped in a cycle.
Balance equations: Balance equations are mathematical expressions used to ensure that the flow into and out of a system is equal, maintaining a steady state. They are crucial in determining the stationary distributions of a stochastic process, particularly in systems like queueing models and birth-death processes. By setting up these equations, you can analyze the stability and long-term behavior of different stochastic systems.
Birth-death process: A birth-death process is a specific type of continuous-time Markov chain that models the transitions of a system where entities can be added (births) or removed (deaths) over time. This process is characterized by the state space being non-negative integers, representing the number of entities in the system, and it is extensively used in various applications like queueing theory and population dynamics. The transition rates are typically dependent on the current state, which ties into properties of Poisson processes and stationary distributions.
Continuous-Time Markov Chains: Continuous-time Markov chains are stochastic processes where changes can occur at any point in time, characterized by the memoryless property, meaning the future state depends only on the current state and not on the sequence of events that preceded it. These processes are defined by a set of states, transition rates between those states, and a system of governing equations that describe how probabilities evolve over time. The behavior of these chains is analyzed through their stationary distributions, which reveal the long-term behavior of the system.
Convergence to equilibrium: Convergence to equilibrium refers to the process by which a stochastic system approaches a stable state, known as the equilibrium or stationary distribution, over time. This concept is crucial for understanding how systems stabilize and what their long-term behaviors will be, especially in the context of Markov chains and their steady-state distributions.
Detailed balance condition: The detailed balance condition is a principle in the study of Markov chains that requires the probability flow between states to be equal in both directions at equilibrium. This means that for any two states, the rate of transition from state A to state B should equal the rate of transition from state B to state A when the system is in a stationary distribution. This concept is crucial for understanding how stationary distributions behave and ensures that the distribution remains unchanged over time.
Eigenvector method: The eigenvector method is a mathematical technique used to find the stationary distributions of a Markov chain by identifying eigenvectors associated with the transition matrix. This method provides insight into the long-term behavior of the chain, highlighting stable states that the system will converge to over time. The significance of this method lies in its ability to simplify complex problems by transforming them into more manageable linear algebra problems.
Ergodic Distribution: An ergodic distribution is a type of probability distribution that represents the long-term behavior of a stochastic process, ensuring that the time averages converge to the same value as the ensemble averages. This concept is key for understanding stationary distributions, as an ergodic distribution indicates that the system will eventually reach a stable state where statistical properties remain unchanged over time. In simpler terms, if a process is ergodic, you can learn everything about its long-term behavior by observing it over a sufficient period.
Gibbs Distribution: The Gibbs distribution, also known as the Boltzmann distribution, is a probability distribution that describes the likelihood of a system being in a particular state, based on its energy level and temperature. It plays a crucial role in statistical mechanics and stochastic processes, providing a way to understand how systems evolve over time and reach equilibrium. This distribution is often associated with stationary distributions in Markov chains, where it describes the steady-state probabilities of being in various states of the system.
Irreducibility: Irreducibility in the context of stochastic processes refers to a property of a Markov chain where it is possible to reach any state from any other state in a finite number of steps. This characteristic indicates that all states communicate with each other, forming a single communicating class. It is an important feature because it implies that long-term behavior and stationary distributions are defined across the entire state space, impacting concepts like absorption and ergodicity.
Limiting Distribution: A limiting distribution is the probability distribution that a stochastic process converges to as time approaches infinity. This concept helps in understanding the long-term behavior of a system, revealing how probabilities stabilize over time and provide insights into the steady-state behavior of processes. It's crucial for analyzing both stationary distributions and alternating renewal processes, as they describe the system's characteristics when it reaches equilibrium.
Markov Chain: A Markov Chain is a mathematical system that undergoes transitions from one state to another within a finite or countable number of possible states, where the probability of each transition depends only on the current state and not on the sequence of events that preceded it. This property is known as the Markov property and allows for the modeling of random processes in various fields, including those involving stationary distributions and genetics. By understanding Markov Chains, one can analyze how systems evolve over time and predict future states based on current conditions.
Mean return time: Mean return time is the expected time it takes for a stochastic process to return to a particular state after leaving it. This concept is essential when analyzing stationary distributions, as it helps quantify how frequently a system revisits its states, offering insights into the long-term behavior of the process.
Quasi-stationary distribution: A quasi-stationary distribution refers to a probability distribution that describes the state of a stochastic process conditioned on survival beyond a certain time, usually in the context of absorbing states. Unlike stationary distributions, which remain constant over time, quasi-stationary distributions apply to non-absorbing processes and focus on the behavior of the system while it is still active, highlighting how probabilities evolve before absorption occurs.
Queueing Theory: Queueing theory is the mathematical study of waiting lines, which helps analyze and model the behavior of queues in various systems. It explores how entities arrive, wait, and are served, allowing us to understand complex processes such as customer service, network traffic, and manufacturing operations.
Random walk: A random walk is a mathematical model that describes a path consisting of a succession of random steps. It is often used to model seemingly unpredictable processes in various fields, illustrating how random variables can accumulate over time. This concept connects to important ideas such as equilibrium behavior, the properties of continuous processes, the dynamics of gambling and financial markets, and even the mechanisms behind genetic variation and population changes.
Reversible Markov Chains: Reversible Markov Chains are a special type of Markov chain where the transition probabilities allow for the process to move in both directions between states, maintaining equilibrium. This reversibility means that the flow of probability into a state is equal to the flow out when the chain is in a stationary distribution, creating a balance that is essential for understanding long-term behavior and equilibrium properties.
Stationary distribution: A stationary distribution is a probability distribution that remains unchanged as the process evolves over time in a Markov chain. It describes the long-term behavior of the chain, where the probabilities of being in each state stabilize and do not vary as time progresses, connecting to key concepts like state space, transition probabilities, and ergodicity.
Steady-state probabilities: Steady-state probabilities represent the long-term behavior of a stochastic process, where the probabilities of being in each state stabilize and do not change over time. These probabilities are crucial for understanding systems at equilibrium, particularly in analyzing performance measures in queueing models and stationary distributions.