🔀Stochastic Processes Unit 5 – Markov chains

Key Concepts and Definitions

• Markov chains model systems transitioning between discrete states over time
• Markov property assumes future states depend only on the current state, not past states
• State space $S$ represents the set of all possible states in the system
• Time index $t$ can be discrete (e.g., $t=0,1,2,\ldots$) or continuous (e.g., $t \geq 0$)
  • Discrete-time Markov chains (DTMCs) have discrete time steps
  • Continuous-time Markov chains (CTMCs) have continuous time
• Initial distribution $\pi_0$ specifies the probability of starting in each state
• Transition probabilities $p_{ij}$ define the likelihood of moving from state $i$ to state $j$
• Markov chains can be homogeneous (transition probabilities remain constant over time) or inhomogeneous (transition probabilities change with time)

Types of Markov Chains

• Finite-state Markov chains have a finite number of states in the state space
• Infinite-state Markov chains have an infinite number of states (e.g., birth-death processes)
• Absorbing Markov chains contain at least one absorbing state that, once entered, cannot be left
• Ergodic Markov chains are irreducible and aperiodic, ensuring a unique stationary distribution exists
  • Irreducible Markov chains allow reaching any state from any other state in a finite number of steps
  • Aperiodic Markov chains do not have periodic behavior in state transitions
• Time-homogeneous Markov chains have transition probabilities that remain constant over time
• Time-inhomogeneous Markov chains have transition probabilities that vary with time
• Higher-order Markov chains consider multiple previous states to determine the next state

Transition Probabilities and Matrices

• Transition probabilities $p_{ij}$ represent the probability of moving from state $i$ to state $j$ in one step
  • $p_{ij} = P(X_{t+1} = j | X_t = i)$, where $X_t$ is the state at time $t$
  • Transition probabilities satisfy $\sum_{j} p_{ij} = 1$ for each state $i$
• Transition probability matrix $P$ contains all transition probabilities $p_{ij}$
  • Rows of $P$ sum to 1, as they represent probability distributions
• $n$-step transition probabilities $p_{ij}^{(n)}$ give the probability of moving from state $i$ to state $j$ in exactly $n$ steps
  • Can be computed using matrix multiplication: $P^{(n)} = P^n$
• Limiting probabilities $\pi_j = \lim_{n \to \infty} p_{ij}^{(n)}$ describe the long-term behavior of the chain
• Transition rate matrix $Q$ is used for continuous-time Markov chains
  • Off-diagonal entries $q_{ij}$ represent the rate of transitioning from state $i$ to state $j$
  • Diagonal entries $q_{ii}$ are set such that each row sums to 0

State Classification and Properties

• Communicating states can be reached from each other in a finite number of steps
• Recurrent states are visited infinitely often with probability 1
  • Positive recurrent states have a finite expected return time
  • Null recurrent states have an infinite expected return time
• Transient states are visited only finitely many times with probability 1
• Absorbing states are recurrent states that, once entered, cannot be left
• Periodicity of a state is the greatest common divisor of the return times to that state
  • Aperiodic states have a period of 1
• Ergodic Markov chains are irreducible and aperiodic
  • All states communicate with each other and are aperiodic
• Detailed balance equations relate stationary probabilities and transition rates in reversible Markov chains

Stationary Distributions

• Stationary distribution $\pi$ is a probability vector that remains unchanged under the transition matrix
  • Satisfies $\pi P = \pi$ for discrete-time Markov chains
  • Satisfies $\pi Q = 0$ for continuous-time Markov chains
• Stationary distributions represent the long-term behavior of the Markov chain
• Ergodic Markov chains have a unique stationary distribution
  • Can be found by solving the linear system $\pi P = \pi$ or $\pi Q = 0$
• Time-reversible Markov chains have the same stationary distribution when time is reversed
  • Satisfy the detailed balance equations $\pi_i p_{ij} = \pi_j p_{ji}$ or $\pi_i q_{ij} = \pi_j q_{ji}$
• Mixing time measures how quickly the chain converges to its stationary distribution
• Convergence rate depends on the spectral gap of the transition matrix or generator

Applications and Examples

• PageRank algorithm uses a Markov chain to rank web pages in search engine results
  • States represent web pages, and transitions represent hyperlinks between pages
• Queueing systems can be modeled using Markov chains (e.g., M/M/1 queue)
  • States represent the number of customers in the system
  • Transitions occur when customers arrive or depart
• Hidden Markov models (HMMs) are used in speech recognition and bioinformatics
  • Observable states emit symbols according to an emission probability distribution
  • Hidden states form a Markov chain governing the transitions between observable states
• Markov decision processes (MDPs) combine Markov chains with decision-making for reinforcement learning
  • Actions taken in each state influence the transition probabilities and rewards
• Markov chain Monte Carlo (MCMC) methods sample from complex probability distributions
  • Construct a Markov chain whose stationary distribution is the target distribution
  • Examples include Metropolis-Hastings algorithm and Gibbs sampling

Computational Methods

• Matrix multiplication can be used to compute $n$-step transition probabilities: $P^{(n)} = P^n$
• Solving linear systems $\pi P = \pi$ or $\pi Q = 0$ yields stationary distributions
  • Gaussian elimination, iterative methods (e.g., Jacobi, Gauss-Seidel), or specialized algorithms can be used
• Eigenvalue decomposition of the transition matrix provides insights into long-term behavior
  • Largest eigenvalue is always 1, corresponding to the stationary distribution
  • Spectral gap between the largest and second-largest eigenvalues determines the convergence rate
• Simulation techniques generate sample paths of the Markov chain
  • Useful for estimating probabilities, expected values, and other quantities of interest
• Numerical methods for continuous-time Markov chains include uniformization and Runge-Kutta methods
• Specialized software packages (e.g., PRISM, PyMC, R packages) facilitate Markov chain analysis

Advanced Topics and Extensions

• Markov renewal processes generalize Markov chains by allowing non-exponential sojourn times in each state
• Semi-Markov processes have state transitions that depend on the sojourn time in the current state
• Markov-modulated processes use a Markov chain to govern the parameters of another stochastic process
  • Examples include Markov-modulated Poisson processes and Markov-modulated fluid flows
• Markov random fields extend Markov chains to higher dimensions (e.g., image processing, spatial statistics)
  • States are associated with nodes in a graph, and transitions occur between neighboring nodes
• Partially observable Markov decision processes (POMDPs) introduce uncertainty in the state observations
  • Decision-making must account for the belief state, a probability distribution over the possible states
• Reinforcement learning algorithms (e.g., Q-learning, SARSA) use Markov decision processes to learn optimal policies
• Convergence analysis and mixing times are essential for understanding the long-term behavior of Markov chains
  • Spectral methods, coupling arguments, and Lyapunov functions are used to establish convergence rates