Fact-checked by Grok 2 weeks ago

Discrete-time Markov chain

A discrete-time Markov chain (DTMC) is a stochastic process that models a system transitioning between a countable set of states at discrete time steps, where the probability of transitioning to the next state depends solely on the current state and satisfies the Markov property: the future state is conditionally independent of the past given the present.^[1] Formally, for a process \{X_n\}_{n \geq 0} with state space S (a countable set, such as the non-negative integers), the transition probabilities are defined by P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i) = p_{ij} for all n \geq 0 and states i, j \in S, where p_{ij} \geq 0 and \sum_{j \in S} p_{ij} = 1 for each i.^[1] These probabilities form the rows of a transition matrix P, which fully characterizes the chain's one-step dynamics.^[2] The concept of Markov chains was introduced by Russian mathematician Andrey Andreyevich Markov (1856–1922) in 1906, initially to analyze sequences of dependent events and challenge the assumption of independence in the law of large numbers, using examples from Alexander Pushkin's poetry to demonstrate correlated letter occurrences.^[3] Markov's work laid the foundation for modern probability theory, extending earlier ideas from Pafnuty Chebyshev and influencing stochastic processes broadly.^[4] Over the 20th century, the theory evolved through contributions like William Feller's classifications of states (transient, recurrent, and absorbing) and the development of n-step transition probabilities via the Chapman-Kolmogorov equations: p_{ij}^{(n+m)} = \sum_{k \in S} p_{ik}^{(n)} p_{kj}^{(m)}, enabling analysis of long-term behavior.^[4] Key properties include irreducibility (every state reachable from any other), periodicity (the greatest common divisor of return times), and ergodicity, under which limiting stationary distributions \pi exist, satisfying \pi = \pi P and \sum \pi_j = 1, representing long-run proportions of time in each state.^[2] Discrete-time Markov chains find wide applications across fields, modeling phenomena where memoryless transitions approximate real-world dependencies. In queueing theory, they describe customer arrivals and service times in systems like M/M/1 queues, yielding steady-state waiting times.^[2] In population genetics, they underpin the Hardy-Weinberg equilibrium by tracking allele frequencies over generations, with transition matrices reflecting mutation and selection probabilities.^[4] Other uses include finance for stock price modeling (e.g., regime-switching), computer science for algorithm analysis like PageRank in search engines, and operations research for inventory control, such as optimizing pallet repair policies to minimize costs based on steady-state probabilities.^[4] These models are computationally tractable via matrix exponentiation and eigenvalue analysis, making them foundational for simulation techniques like Markov chain Monte Carlo in Bayesian statistics.^[5]

Fundamentals

Definition

A discrete-time Markov chain is a stochastic process that models a system evolving through a sequence of states over discrete time steps, where the probability distribution of the next state depends solely on the current state. Formally, it is defined as a sequence of random variables \{X_n : n = 0, 1, 2, \dots \} taking values in a discrete state space S, which may be finite or countably infinite.^[6]^[7] The defining feature is the Markov property, which states that the future state is conditionally independent of the past given the present:

P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i)

for all n \geq 0, states i_0, \dots, i_n, j \in S, and where the right-hand side equals the transition probability p_{ij}.^[6]^[8]^[7] This property ensures a memoryless evolution, capturing systems where history beyond the current configuration is irrelevant. Under the standard assumption of time-homogeneity, the transition probabilities p_{ij} = P(X_{n+1} = j \mid X_n = i) are constant across time steps n. These form the entries of a transition matrix P = (p_{ij}), which is row-stochastic: each row sums to 1, i.e., \sum_{j \in S} p_{ij} = 1 for every i \in S, and p_{ij} \geq 0.^[6]^[8] The chain begins with an initial distribution \pi_0, a probability vector over S such that \pi_0(i) = P(X_0 = i) for i \in S, with \sum_{i \in S} \pi_0(i) = 1.^[6]^[7] The process induces a probability measure on the space of all possible paths, i.e., sequences (x_0, x_1, x_2, \dots) \in S^{\mathbb{N}_0}, determined jointly by \pi_0 and the transition kernel P. Specifically, the probability of a path is \pi_0(x_0) \prod_{n=0}^\infty p_{x_n x_{n+1}} (with the infinite product converging appropriately under the stochastic structure). This framework fully specifies the joint distribution of the chain.^[6]

Examples and Variations

A classic example of a discrete-time Markov chain is the two-state weather model, where the states represent sunny (S) and rainy (R) days. The process transitions from sunny to sunny with probability 0.8, sunny to rainy with 0.2, rainy to sunny with 0.4, and rainy to rainy with 0.6; the initial distribution might assign probability 0.7 to sunny and 0.3 to rainy on day 0.^[9] This setup models daily weather dependence solely on the previous day's condition, illustrating a finite-state homogeneous chain.^[10] Another finite-state example is the gambler's ruin problem, where a gambler starts with i dollars (states 0 to N, with 0 and N absorbing) and bets $1per round against a house, winning with probabilityp=0.5and losing withq=0.5. The transition probabilities are P_{k,k+1}=pandP_{k,k-1}=qfor0<k<N, P_{0,0}=P_{N,N}=1, and the initial distribution is a point mass at i$.^[11] This chain captures the eventual ruin or success of the gambler in a fair game.^[12] For an infinite-state case, consider the simple symmetric random walk on the integers \mathbb{Z}, where from state k \in \mathbb{Z}, the chain moves to k+1 or k-1 each with probability $1/2, and the initial distribution is a point mass at 0.^[13] This countable-state homogeneous chain models unbiased diffusion on the number line, such as a particle's position over discrete steps.^[14] Markov chains vary by state space: finite chains have a limited number of states, enabling complete transition matrix representation, while countable infinite spaces, like the random walk, require infinite matrices but allow analysis via generating functions.^[15] Most standard models assume homogeneity, where transition probabilities remain constant over time, though inhomogeneous variants permit time-dependent probabilities for non-stationary processes (detailed in later sections on multi-step transitions).^[16] Discrete-time chains evolve at fixed integer steps, contrasting with continuous-time versions that jump at random exponential times, but both share the memoryless property.^[16]

Transition Probabilities

One-Step Transitions

In a discrete-time Markov chain, the one-step transition probabilities form the fundamental mechanism governing the evolution from one state to the next. These probabilities are defined as p_{ij} = P(X_{n+1} = j \mid X_n = i), where X_n denotes the state at time n, and the chain is assumed to be time-homogeneous such that p_{ij} does not depend on n. This conditional probability captures the likelihood of moving from state i to state j in a single step, satisfying p_{ij} \geq 0 for all states i, j in the state space and \sum_j p_{ij} = 1 for each i, ensuring the transitions exhaust all possibilities.^[7]^[17] The collection of these probabilities is conveniently represented by the transition matrix P = (p_{ij}), a square matrix whose rows correspond to the current state and columns to the next state. For a finite state space with m states, P is an m \times m matrix with non-negative entries where each row sums to 1, making it a right-stochastic matrix. Such matrices preserve probability measures under multiplication, reflecting the Markov property's memoryless evolution. Properties like irreducibility—where every state is reachable from every other—and aperiodicity—where the greatest common divisor of return times to a state is 1—emerge as key characteristics of P, influencing long-term behavior but rooted in the one-step structure.^[7]^[18]^[19] The Chapman-Kolmogorov equations, which generalize transition probabilities over multiple steps, simplify trivially for one step: p_{ij}^{(1)} = p_{ij}, or in matrix form, P^{(1)} = P. This identity underscores that the one-step matrix directly encodes the immediate dynamics without further composition.^[17]^[7] The probability distribution over states evolves linearly via the transition matrix. If \pi_n = (\pi_n(i)) is the row vector of probabilities P(X_n = i) at time n, then the next distribution is given by

\pi_{n+1} = \pi_n P,

where matrix multiplication yields \pi_{n+1}(j) = \sum_i \pi_n(i) p_{ij}, the law of total probability applied conditionally. This recursive relation allows simulation of the chain by iteratively applying P to an initial distribution \pi_0.^[17]^[18] From an interpretive standpoint, the one-step transitions determine the expected number of visits to state j starting from i after one step, simply p_{ij}, providing the basis for simulating paths or computing short-term expectations in applications like queueing systems or genetic models.^[7]^[19]

n-Step Transitions

In a discrete-time Markov chain, the n-step transition probability from state i to state j, denoted p_{ij}^{(n)}, is defined as the probability that the chain is in state j after n steps given that it started in state i at time k, formally p_{ij}^{(n)} = P(X_{k+n} = j \mid X_k = i). This quantity captures the likelihood of reaching j from i over multiple transitions and is independent of k due to the time-homogeneity of the chain.^[1]^[20] The matrix of n-step transition probabilities, P^{(n)}, has entries p_{ij}^{(n)} and is obtained by raising the one-step transition matrix P to the nth power, so P^{(n)} = P^n. This matrix power formulation allows the n-step probabilities to be computed as the product of successive one-step transitions, where the (i,j)-th entry of P^n sums over all possible intermediate paths of length n from i to j, weighted by their probabilities. The Chapman-Kolmogorov equations provide a fundamental relation for these matrices: for any nonnegative integers m and n, P^{(m+n)} = P^{(m)} P^{(n)}, which follows from the law of total probability by conditioning on the state after m steps. These equations, originally derived in the context of stochastic processes, enable recursive computation of multi-step transitions without enumerating all paths explicitly.^[1]^[20]^[21] For chains with a finite state space, the n-step transition matrix can be computed directly via matrix multiplication, which is efficient for small state spaces using standard linear algebra algorithms. For example, iterative squaring of P (computing P^2, then (P^2)^2 = P^4, and so on) reduces the complexity from O(N^3 n) to O(N^3 \log n) for N states, making it practical for moderate n. While asymptotic behaviors emerge for large n, the focus here remains on exact finite-step calculations.^[10]^[22] The evolution of the state distribution after n steps is given by the row vector equation \pi_n = \pi_0 P^n, where \pi_0 is the initial distribution and \pi_n is the distribution at time n. This matrix form succinctly expresses how the probability mass redistributes over states through repeated application of the transition matrix, providing a vectorized view of the n-step dynamics.^[20]^[10]

State Classification

Communicating Classes

In a discrete-time Markov chain with state space S, a state j \in S is said to be accessible from a state i \in S, denoted i \to j, if there exists some integer n \geq 0 such that the probability of transitioning from i to j in exactly n steps is positive, i.e., P(X_n = j \mid X_0 = i) > 0.^[14] This relation captures the directional reachability between states based on the chain's transition structure. Accessibility is a fundamental concept that underlies the connectivity of the state space. States i and j communicate with each other, denoted i \leftrightarrow j, if i \to j and j \to i.^[14] Communication is an equivalence relation on S, as it is reflexive (every state communicates with itself), symmetric, and transitive.^[14] Consequently, the state space S can be partitioned into disjoint equivalence classes, known as communicating classes, where every pair of states within a class communicates, but states in different classes do not.^[14] A communicating class C \subseteq S is closed if, for every i \in C and every j \in S such that i \to j, it holds that j \in C; otherwise, the class is open.^[14] Closed classes trap the chain once entered, with no probability of escape to outside states, while open classes allow transitions to other classes.^[14] Singleton classes consisting of a single absorbing state (where the transition probability to itself is 1) are always closed.^[14] Communicating classes can be further classified as transient or recurrent, depending on whether the chain eventually leaves the class with positive probability or remains there indefinitely; however, detailed analysis of these properties follows from recurrence considerations.^[14] The transition matrix P of the chain can be rearranged by ordering states according to their communicating classes, resulting in a block structure where the submatrices along the diagonal correspond to the intra-class transitions within each class.^[23] For closed classes, the corresponding blocks have no outgoing transitions to other blocks, reflecting the absence of escape paths.^[23] Consider the simple symmetric random walk on the integers \mathbb{Z}, where from any state i, the chain moves to i+1 or i-1 with equal probability $1/2. In this chain, every pair of states communicates, forming a single irreducible communicating class that encompasses the entire state space.^[24] In contrast, the gambler's ruin problem models an absorbing chain on states \{0, [1](/page/1), \dots, N\}, where states 0 and N are absorbing (transition probability 1 to themselves), and from interior states i = [1](/page/1), \dots, N-1, the chain moves to i+1 or i-1 with probabilities p and $1-p, respectively. Here, the singleton classes \{0\} and \{N\} are closed communicating classes, while the remaining states \{[1](/page/1), \dots, N-1\} form an open communicating class from which the chain eventually absorbs into one of the closed classes.^[7]

Periodicity

In a discrete-time Markov chain, the period of a state i is defined as the greatest common divisor d of the set \{n \geq 1 : p_{ii}^{(n)} > 0\}, where p_{ii}^{(n)} denotes the probability of returning to state i after exactly n steps.^[25] This integer d \geq 1 captures the cyclic structure of possible return paths to the state, as returns can only occur at multiples of d. If d = 1, the state is aperiodic, meaning return times have no common divisor greater than 1 and can occur at arbitrary large steps without restriction.^[25] Within a communicating class C, all states share the same period d, which serves as the period of the class itself. This common period is equivalently the greatest common divisor of the set \{n \geq 1 : p_{ij}^{(n)} > 0 \text{ for some } i, j \in C\}.^[25] A class is periodic if d > 1 and aperiodic if d = 1. The uniformity of periodicity across the class arises from the bidirectional accessibility of states, ensuring that return patterns align for all members.^[25] The periodicity of a class has significant implications for the chain's dynamic behavior. In a periodic class with d > 1, the transition probabilities exhibit oscillatory patterns, cycling through d subclasses where the chain alternates deterministically between them every step.^[25] For instance, consider a simple symmetric random walk on the integers \mathbb{Z}, where from an even state, the chain moves to an odd state with probability 1, and vice versa; this bipartite structure yields d = 2, as returns to the starting parity occur only at even steps.^[26] In contrast, an aperiodic class with d = 1 lacks such enforced cycling, allowing more flexible return timings and smoother long-term evolution without periodic constraints.^[25]

Transience and Recurrence

In a discrete-time Markov chain, a state i is classified as recurrent if, starting from i, the chain returns to i with probability 1, that is, the probability of eventual return f_{ii} = \sum_{n=1}^\infty f_{ii}^{(n)} = 1, where f_{ii}^{(n)} denotes the probability of first return to i at exactly step n.^[24] Conversely, state i is transient if f_{ii} < 1, meaning there is a positive probability that the chain never returns to i after leaving it.^[24] This classification depends solely on the n-step transition probabilities p_{ii}^{(n)} from the chain's structure, as the generating function relation f_{ii}(s) = \frac{U_i(s) - 1}{U_i(s)} (where U_i(s) = \sum_{n=0}^\infty p_{ii}^{(n)} s^n) yields f_{ii} = 1 if and only if \sum_{n=0}^\infty p_{ii}^{(n)} = \infty.^[27] Within a communicating class, the recurrence or transience classification is uniform: if one state in the class is recurrent, all states in the class are recurrent, and similarly for transience.^[24] This follows from the mutual accessibility of states in the class, ensuring that return probabilities propagate across the class.^[28] Recurrent states can be further distinguished as null recurrent or positive recurrent based on the mean return time \mu_i = \mathbb{E}[T_i \mid X_0 = i], where T_i = \min\{n \geq 1 : X_n = i\} is the first return time to i. A recurrent state i is positive recurrent if \mu_i < \infty and null recurrent if \mu_i = \infty.^[27] Classic examples illustrate these concepts. The simple symmetric random walk on the one-dimensional integer lattice \mathbb{Z} (where from position k, the chain moves to k+1 or k-1 with probability $1/2 each) is recurrent, as the probability of returning to the origin is 1, though null recurrent since the expected return time is infinite.^[29] In contrast, the same walk on the three-dimensional lattice \mathbb{Z}^3 is transient, with return probability less than 1, as established by Pólya's theorem for dimensions d \geq 3.^[30] Another example is the gambler's ruin chain on states \{1, 2, \dots, N-1\} with transitions from i to i+1 or i-1 with equal probability (assuming absorbing barriers at 0 and N), where all interior states are transient, as the chain eventually reaches an absorbing state without returning.^[31]

Absorbing States

In a discrete-time Markov chain, an absorbing state is defined as a state i for which the one-step transition probability satisfies p_{ii} = 1, implying that once the process enters state i, it remains there with probability 1 for all subsequent steps.^[32] This property distinguishes absorbing states from other states, as the chain is "trapped" upon arrival, with no possibility of departure.^[33] An absorbing Markov chain is one that possesses at least one absorbing state, and from every transient (non-absorbing) state, there exists a path leading to some absorbing state with probability 1.^[32] In such chains, the state space can be partitioned into transient states and one or more absorbing states, where the transient states form communicating classes that eventually lead to absorption.^[33] A canonical form for the transition matrix P of an absorbing chain rearranges states so that absorbing states appear first, yielding

P = \begin{pmatrix} I & 0 \\ R & Q \end{pmatrix},

where I is the identity matrix for absorbing states, R captures transitions from transient to absorbing states, and Q governs transitions among transient states (with spectral radius less than 1, ensuring eventual absorption).^[32] The probability of eventual absorption in a particular absorbing state j, starting from a transient state i, is denoted b_{ij}. For absorbing states, b_{jj} = 1 and b_{kj} = 0 for k \neq j. For transient states i, these probabilities satisfy the system of linear equations

b_{ij} = p_{ij} + \sum_{k \in T} p_{ik} b_{kj},

where T is the set of transient states.^[32] In matrix form, if B is the matrix of absorption probabilities with rows for all states and columns for absorbing states, then for the transient block, B_T = N R, where N = (I - Q)^{-1} is the fundamental matrix and R is the transient-to-absorbing transition submatrix.^[33] This setup allows solving for B via matrix inversion, providing the distribution over absorbing states reached from any starting point. For example, in a gambler's ruin problem modeled as an absorbing chain with states representing capital levels (0 and maximum capital as absorbing), the absorption probabilities b_{ij} compute the chance of ruin or success starting from intermediate capital i.^[32] The fundamental matrix N = (I - Q)^{-1} plays a central role in analyzing absorbing chains, as its entry N_{ij} represents the expected number of visits to transient state j starting from transient state i before absorption occurs.^[32] This matrix admits the Neumann series expansion N = I + Q + Q^2 + \cdots, which converges because the transient subchain is substochastic and absorption is certain.^[33] The expected time to absorption from transient state i, denoted t_i, is the sum of the i-th row of N, or equivalently t_i = \sum_{j \in T} N_{ij}, representing the total expected steps spent in transient states before reaching an absorbing one.^[32] In the gambler's ruin example, row sums of N yield the expected duration of play until ruin or success, scaling with the initial capital in fair games.^[32] These quantities enable practical applications, such as modeling decision processes or queueing systems where absorption corresponds to termination or equilibrium.^[33]

Stationary Distributions

Existence and Computation

A stationary distribution for a discrete-time Markov chain is a probability row vector \pi = (\pi_i)_{i \in S} satisfying \pi = \pi P, where P is the transition matrix, along with the normalization condition \sum_{i \in S} \pi_i = 1.^[34] This equation implies that \pi is the left eigenvector of P corresponding to the eigenvalue 1.^[2] Equivalently, the components of \pi obey the global balance equations

\pi_j = \sum_{i \in S} \pi_i p_{ij}, \quad \forall j \in S,

which express the conservation of probability flow in equilibrium.^[34] The existence of a unique stationary distribution \pi requires the chain to be irreducible and positive recurrent, meaning all states communicate with one another and the expected return time to any state is finite. For finite-state irreducible chains, a unique stationary distribution exists, as finite irreducible chains are necessarily positive recurrent.^[34] In the infinite-state case, existence holds if the chain is irreducible and positive recurrent, where positive recurrence means that the expected return time to any state is finite.^[34] Under these conditions, the stationary distribution is unique and positive for all states, independent of the initial distribution.^[34] For reducible chains, multiple stationary distributions may exist, each supported on a distinct closed communicating class.^[2] To compute \pi for finite-state chains, solve the homogeneous linear system

\pi (P - I) = 0

subject to \sum_i \pi_i = 1, where I is the identity matrix; this system has a unique solution under irreducibility.^[34] Direct methods such as Gaussian elimination can be applied to the augmented system formed by replacing one equation with the normalization constraint to ensure solvability.^[35] Alternatively, iterative methods like power iteration approximate \pi by starting with an arbitrary probability vector \pi^{(0)} and repeatedly applying the transition matrix via \pi^{(k+1)} = \pi^{(k)} P, which converges to \pi for irreducible aperiodic chains.^[2]

Steady-State Analysis

In ergodic discrete-time Markov chains, the stationary distribution \pi provides a key interpretation for long-run behavior: the probability \pi_j represents the limiting proportion of time the chain spends in state j as the number of steps n \to \infty, regardless of the initial state.^[36] This holds under conditions of irreducibility and positive recurrence, ensuring the existence and uniqueness of \pi.^[37] The stationary distribution satisfies the global balance equations, \pi P = \pi, where P is the transition matrix, meaning the total probability flow into each state equals the flow out in steady state.^[38] In contrast, detailed balance requires \pi_i p_{ij} = \pi_j p_{ji} for all states i, j, a stronger condition that implies global balance but holds only for reversible chains, which are discussed separately.^[39] For reducible chains, the state space decomposes into multiple closed communicating classes, and any stationary distribution is a convex combination of the unique stationary distributions within each recurrent class, weighted by the initial probabilities absorbed into those classes.^[40] Transient states receive zero probability in the limit. In time-inhomogeneous Markov chains, where transition probabilities vary with time, a steady-state distribution may still exist if the limiting transition matrix is approached and satisfies ergodic conditions, allowing the marginal distribution to converge despite the variation.^[41] A representative example is the discrete-time birth-death chain on non-negative integers, with birth probabilities p_k (upward from k) and death probabilities q_k = 1 - p_k (downward, except at 0). The stationary distribution \pi satisfies the recursive relation \pi_{k+1} = \frac{p_k}{q_{k+1}} \pi_k for k \geq 0, derived from detailed balance, with normalization \sum_k \pi_k = 1.^[42] For constant rates p_k = \lambda and q_k = 1 - \lambda with \lambda < 1/2, this yields a geometric distribution \pi_k = (1 - \rho) \rho^k where \rho = \lambda / (1 - \lambda), illustrating convergence when the chain is positive recurrent.^[42]

Dynamic Properties

Hitting Times

In a discrete-time Markov chain with state space S and transition matrix P = (p_{ij}), the hitting time of a state j \in S starting from an initial state i \in S with i \neq j is defined as the first positive integer n at which the chain reaches j, formally T_j = \min\{n \geq 1 : X_n = j \mid X_0 = i\}, while T_i = 0 if i = j.^[34] This random variable captures the initial passage to the target state and serves as a key tool for analyzing transient behavior and absorption dynamics.^[43] The distribution of the hitting time T_j is given by the tail probabilities P(T_j > n \mid X_0 = i) for n \geq 0, which represent the probability that the chain has not yet reached j after n steps. These probabilities satisfy a recursive relation derived from the Chapman-Kolmogorov equations: P(T_j > n \mid X_0 = i) = \sum_{k \neq j} P(X_n = k, T_j > n \mid X_0 = i), and can be computed iteratively using the n-step transition probabilities in the subprocess on states excluding j (equivalent to the original chain with j made absorbing), given by P(T_j > n \mid X_0 = i) = \sum_{k \neq j} q_{ik}^{(n)}, where q^{(n)} are the n-step probabilities in this modified chain.^[34] For small state spaces, explicit distributions may be obtained via matrix exponentiation, while in larger or infinite spaces, bounds or approximations are often used.^[43] The expected hitting time m_{ij} = E[T_j \mid X_0 = i] provides the mean duration to reach j from i, with m_{jj} = 0. For i \neq j, it satisfies the system of linear equations

m_{ij} = 1 + \sum_{k \in S} p_{ik} m_{kj},

which arises from conditioning on the first transition step.^[34] This equation holds under the assumption that the expectation is finite, a condition guaranteed in finite irreducible chains but requiring verification in infinite-state cases.^[43] For finite state spaces, the expected hitting times are solved as the unique minimal non-negative solution to this linear system, typically via Gaussian elimination or matrix inversion after reordering states to isolate j. In infinite-state chains, such as birth-death processes or random walks on graphs, generating functions offer an alternative: the probability generating function G_{ij}(s) = E[s^{T_j} \mid X_0 = i] satisfies a functional equation derived from the first-step analysis, from which moments like m_{ij} are extracted by differentiation at s=1.^[34] Analytical solutions exist for canonical examples, such as the gambler's ruin problem where m_{ij} is proportional to the distance between states under fair odds.^[43] When j is an absorbing state—meaning p_{jj} = 1 and p_{jk} = 0 for k \neq j—the hitting time T_j coincides with the absorption time into j, and m_{ij} represents the expected steps until absorption starting from i. In this case, the equations simplify by setting m_{kj} = 0 for absorbing k, reducing to a subsystem over transient states, and the tail probability P(T_j > n \mid X_0 = i) = \sum_{k \neq j} p_{ik}^{(n)} holds since paths reaching j stay there.^[34] This connection extends hitting time analysis to absorption probabilities and mean absorption times in multi-absorbing setups.^[43]

Ergodic Theorem

The ergodic theorem for discrete-time Markov chains asserts that, under suitable conditions, the long-run time average of a function evaluated along the chain's trajectory converges almost surely to the expected value of that function under the chain's unique stationary distribution. Specifically, consider an irreducible, positive recurrent, and aperiodic Markov chain \{X_k\}_{k=0}^\infty on a countable state space with transition matrix P and unique stationary distribution \pi, where \pi P = \pi and \sum_j \pi_j = 1. For any bounded measurable function f: S \to \mathbb{R}, the empirical average satisfies

\frac{1}{n} \sum_{k=0}^{n-1} f(X_k) \to \sum_{j \in S} \pi_j f(j)

almost surely as n \to \infty, regardless of the initial distribution. This result equates the time average of f with its space average under \pi, establishing a fundamental link between sample path behavior and invariant measures. This convergence relies on the chain's ergodicity, characterized by irreducibility (every state communicates with every other), positive recurrence (finite mean return times to each state, ensuring \pi exists and is unique), and aperiodicity (greatest common divisor of return times equals 1, enabling geometric ergodicity). Without aperiodicity, the theorem still holds via Cesàro means for periodic chains of period d > 1, where the average over blocks of length d converges to the stationary value, but direct n-step convergence may oscillate cyclically. The proof applies Birkhoff's pointwise ergodic theorem to the shift transformation on the path space of the chain, viewing the Markov process as an ergodic measure-preserving dynamical system with respect to the invariant measure induced by \pi. In this framework, the time average equals the space average almost everywhere under the invariant measure. A related consequence is the convergence of the n-step distribution \pi_n = \pi_0 P^n to \pi in total variation (or stronger norms under additional assumptions), i.e., \|\pi_n - \pi\|_{TV} \to 0 as n \to \infty, which follows from the ergodic theorem applied to indicator functions. This distributional convergence holds almost surely in the strong sense (pathwise), but weaker versions guarantee convergence in probability for broader classes of chains. The strong law provides almost sure convergence, contrasting with the weak law's convergence in probability, which requires fewer conditions but lacks pathwise guarantees. These results underpin applications in simulation, queueing, and statistical inference for Markov models.

Advanced Concepts

Reversible Markov Chains

A discrete-time Markov chain with stationary distribution \pi is reversible if it satisfies the detailed balance equations \pi_i p_{ij} = \pi_j p_{ji} for all states i, j, ensuring that the probability flux between any pair of states is equal in both directions under the stationary regime.^[44] This condition implies that the chain's time-reversed process behaves identically to the forward process in stationarity.^[45] An equivalent characterization of reversibility is provided by Kolmogorov's criterion, which states that for every cycle of states i_1, i_2, \dots, i_k, i_1, the product of transition probabilities along the forward cycle equals that along the backward cycle: \prod_{m=1}^k p_{i_m i_{m+1}} = \prod_{m=1}^k p_{i_{m+1} i_m}, where i_{k+1} = i_1.^[46] This cycle condition holds if and only if detailed balance is satisfied, offering a practical test for reversibility without explicitly computing the stationary distribution.^[47] For a reversible chain in stationarity, the time-reversed process \{X'_n = X_{T-n}\} for large terminal time T is also a Markov chain, with transition probabilities p'_{ji} = \frac{\pi_j}{\pi_i} p_{ij}.^[48] This reversibility simplifies analysis, as the reversed chain shares the same stationary distribution \pi and facilitates techniques like backward simulation in Monte Carlo methods.^[49] Reversible chains exhibit advantageous spectral properties: their transition matrix P is similar to a symmetric matrix via the diagonal matrix \Pi = \operatorname{diag}(\pi), yielding real eigenvalues and orthogonality of eigenvectors, which eases convergence rate analysis and diagonalization.^[50] Such chains are prevalent in queueing theory, particularly birth-death processes, where transitions occur only between adjacent states, naturally satisfying detailed balance and enabling efficient steady-state computations.^[49] A classic example is the Ehrenfest urn model, which simulates diffusion with N molecules distributed between two urns; at each step, a molecule is moved from the occupied urn to the other with equal probability. This chain is reversible, with stationary distribution \pi_k = \binom{N}{k} / 2^N for k molecules in the first urn, satisfying detailed balance due to symmetric transitions.^[51]

Time-Inhomogeneous Chains

In time-inhomogeneous discrete-time Markov chains, the transition probabilities vary with time, such that the one-step transition probability from state i to state j at time n is given by p_{ij}(n) = P(X_{n+1} = j \mid X_n = i), where each P(n) = (p_{ij}(n)) forms a stochastic matrix with non-negative entries summing to 1 in each row.^[52] Unlike time-homogeneous chains, which rely on a fixed transition matrix P, time-inhomogeneous chains do not admit a single invariant distribution in general, as the dynamics evolve without a constant structure.^[53] The n-step transition probabilities for such chains are obtained by successive matrix multiplication of the time-varying matrices, specifically P_{0,n}(i,j) = P(X_n = j \mid X_0 = i) satisfies the Chapman-Kolmogorov equations and equals the (i,j)-entry of the product P(0) P(1) \cdots P(n-1).^[53] If a limiting distribution \lim_{n \to \infty} \pi_n exists, where \pi_n denotes the distribution at time n, it may satisfy a time-averaged balance equation, but no unique stationary distribution \pi generally holds, contrasting with the homogeneous case where \pi P = \pi.^[54] Convergence of \pi_n to a unique limit can occur under conditions like Dobrushin's contraction coefficient, which measures the contraction rate in total variation distance for the Markov operators; specifically, if the supremum of these coefficients over time is less than 1, the chain exhibits uniform ergodicity, ensuring exponential convergence regardless of the initial distribution.^[55] For instance, in finite-state spaces, assumptions such as periodic minorization—where there exists r > 0 and \delta \in (0,1) such that P_{t,t+r}(x,y) \geq \delta for all states x, y and times t—guarantee that the total variation distance between any two distributions decreases exponentially.^[53] Time-inhomogeneous Markov chains find applications in modeling non-stationary environments, such as queueing systems with time-varying arrival rates due to fluctuating demand, where the transition matrices reflect seasonal or periodic changes in service dynamics.^[54] They are also used in finance to analyze exchange rates under evolving market conditions, capturing inhomogeneities that homogeneous models overlook.^[56]

References

[1]
[PDF] 1 Discrete-time Markov chains
Definition 1.1 A stochastic process {Xn} is called a Markov chain if for all times n ≥ 0 and all states i0,...,i,j ∈ S,. P(Xn+1 = j|Xn = i, Xn−1 = in−1 ...
[2]
[PDF] Discrete-Time Markov Chains - CMU School of Computer Science
Definition 24.10 A Markov chain for which the limiting probabilities exist is said to be stationary or in steady state if the initial state is chosen according.
[3]
[PDF] Markov Chains Handout for Stat 110 1 Introduction
Markov chains were first introduced in 1906 by Andrey Markov, with the goal of showing that the Law of Large Numbers does not necessarily require the random.
[4]
[PDF] MARKOV CHAINS: ROOTS, THEORY, AND APPLICATIONS
Introduction. The purpose of this paper is to develop an understanding of the theory underlying Markov chains and the applications that they have.
[5]
[PDF] A Short History of Markov Chain Monte Carlo - uf-statistics
Abstract. We attempt to trace the history and development of Markov chain. Monte Carlo (MCMC) from its early inception in the late 1940s through its.
[6]
[PDF] MATH858D MARKOV CHAINS Contents 1. Discrete ... - UMD MATH
In general, a discrete-time Markov chain is defined as a sequence of random variables. (Xn)n≥0 taking a finite or countable set of values and characterized by ...
[7]
[PDF] Chapter 3 Discrete Time Markov Chains
Any process Xn, n ≥ 0, satisfying the Markov property (3.3) is called a discrete time Markov chain. Note that the processes described in Examples 3.1. 1 and 3. ...
[8]
[PDF] Lecture 17 (10/23/2019): Markov Chains
Oct 23, 2019 · Definition 3 (Markov Chains). A discrete time stochastic process X = (X0,X1,... ) is called a. (discrete time) Markov chain if for every t ...<|control11|><|separator|>
[9]
[PDF] 18.440: Lecture 33 Markov Chains - DSpace@MIT
Simple example. ▷ For example, imagine a simple weather model with two states: rainy and sunny. ▷ If it's rainy one day, there's a .5 chance it will be rainy ...<|control11|><|separator|>
[10]
[PDF] Chapter 4 - Markov Chains
If we say that the process is in state 0 when it rains and state 1 when it does not rain, then'the above is a two-state Markov chain whose transition.Missing: scholarly | Show results with:scholarly
[11]
Section 3 Gambler's ruin | MATH2750 Introduction to Markov ...
Consider the following gambling problem. Alice is gambling against Bob. Alice starts with £a a and Bob starts with £b b . It will be convenient to write ...
[12]
[PDF] Gambler's Ruin and The Three State Markov Process
The gambler's ruin problem involves a player betting one dollar, winning or losing one dollar per bet, and the player's fortune is visualized as a Markov chain.
[13]
Section 2 Random walk | MATH2750 Introduction to Markov Processes
When p=q=12 p = q = 1 2 , we're equally as likely to go up as down, and we call this the simple symmetric random walk. The simple random walk is a simple but ...
[14]
[PDF] Markov Chains
The simple symmetric random walk on Z is clearly irreducible, and by Example 6.1 it is recurrent. Consider the measure λi = 1 for all i. Then λi = λi−1(1/2) + ...
[15]
[PDF] Discrete-Time Markov Chains - Lancaster University
This report considers homogeneous Markov Chains over discrete time, and with countable (either finite or countably infinite) state space. We analyse Markov ...
[16]
[PDF] Markov Chains and Mixing Times David A. Levin Yuval Peres ...
It is amusing to interpret random walks on the symmetric group as card shuffles—and real shuffles have inspired some extremely serious mathematics—but these ...
[17]
[PDF] Chapter 3 Markov Chains
A discrete-time Markov chain (M.C.), {Xt : t = 0, 1, ···}, is a stochastic ... For a Markov chain, P(Xn+1 = j|Xn = i) is called a one-step transition proba-.
[18]
[PDF] 7. Markov Chains (Discrete-Time Markov Chains) 7.1. Introduction
Introduction: Markov Chains. Consider a system which can be in one of a countable number of states 1,2,3,... . The system is observed at the time.
[19]
Finite Markov Chains - SpringerLink
Free delivery 14-day returnsJul 1, 1976 · Book Title: Finite Markov Chains. Book Subtitle: With a New Appendix "Generalization of a Fundamental Matrix". Authors: John G. Kemeny, J. Laurie Snell.
[20]
[PDF] 4. Markov Chains (9/23/12, cf. Ross) 1. Introduction 2. Chapman ...
Markov Chains. 4.2 Chapman-Kolmogorov Equations. Definition: The n-step transition probability that a process currently in state i will be in state j after n.
[21]
[PDF] Lecture 3: Discrete-Time Markov Chain – Part I 3.1 Introduction
Each random variable Xn can have a discrete, continuous, or mixed distribution. For example, in a queue. Xn could represent the time that the n-th customer ...
[22]
[PDF] Lecture 1: Markov Chains-Part I 1.1 Definition and characterization
Definition 1.1. (Markov Chain) A discrete-time stochastic process X = {X0,X1,X2, ···} with a countable state space X is a Markov Chain if. P (Xk+1 = j|Xk = i ...
[23]
[PDF] 7 Communication Classes
Feb 26, 2009 · Any absorbing state constitutes its own communication class (because it cannot reach any other state). However, a Markov chain may be absorbed ...
[24]
[PDF] Discrete Time Markov Chains 1 Examples
Apr 14, 2011 · Consider a random walk on Z, where pi,i+1 = p and pi+1,i = 1 − p, for all i ∈ Z, 0 <p< 1 The chain is an infinite and closed class. For.
[25]
[PDF] Markov Chains - CAPE
This book is an account of the elementary theory of Markov chains, with applications. It was conceived as a text for advanced undergraduates or master's level ...
[26]
[PDF] Lecture 10: Random walks, Markov chains, and how to analyse them
Example 5 (Drunkard's walk on n-cycle). Consider a Markov chain defined by the following random walk on the nodes of an n-cycle. At each step, stay at the same ...
[27]
[PDF] 6 Discrete Time Markov Chains
(The Ci's are called communicating classes.) Example: Random walk with Absorbing Barriers. Definition 6.11 A Markov chain is said to be irreducible if all the ...
[28]
[PDF] MARKOV CHAINS: BASIC THEORY 1.1. Definition and First ...
Definition 1. A (discrete-time) Markov chain with (finite or countable) state space X is a se- quence X0,X1,... of X −valued random variables such that for all ...
[29]
[PDF] Random walks
Theorem 2.22 The simple symmetric random walk on Zd is recurrent in dimensions d = 1, 2 and transient in dimensions d ≥ 3. The integral is finite if and only ...
[30]
[PDF] p´olya's random walk theorem - MIT Mathematics
The simple random walk on Zd is recurrent in dimensions d = 1, 2 and transient in dimension d ≥ 3. This note presents a fairly direct proof of Pólya's ...
[31]
[PDF] Markov Chains - UW Math Department
In other words, a state i is transient if there is a way to leave state i that never returns to state i. In the gambler's ruin example, states 1, 2, and 3 are ...
[32]
[PDF] Chapter 11: Markov Chains
Kemeny, J. L. Snell, G. L. Thompson, Introduction to Finite Mathematics, 3rd ed. (Englewood Cliffs, NJ: Prentice-Hall, 1974).
[33]
[PDF] Finite Markov Chains
Kemeny/Snell: Finite Markov Chains. 1976. ix, 224 pages. I! illus. Lang: Undergraduate Analysis. 1983. xiii, 545 pages. 52 illus. Lax/Burstein/Lax: Calculus ...
[34]
[PDF] Markov Chains - Chris Wells
This book is an account of the elementary theory of Markov chains, with applications. It was conceived as a text for advanced undergraduates or master's level ...
[35]
[PDF] computing the stationary distribution of a finite markov chain through ...
This work presents an approach for reducing the number of arithmetic operations involved in the computation of a stationary distribution for a finite Markov ...
[36]
https://www.columbia.edu/~ks20/stochastic-I/stochastic-I-MCII.pdf
[37]
[PDF] 25 Ergodicity for Finite-State Discrete-Time Markov Chains
This theorem is important because it allows us to simply solve the stationary equations to get the limiting distribution. In Chapter 24, we did not spend time ...
[38]
[PDF] Markov Chains
These equations are known as the global balance equations. They state that, at equilibrium, the probability of a transition out of j (left side of Eq. (3A.2)) ...
[39]
[PDF] Detailed Balance, and Markov Chain Monte Carlo (MCMC) πi
Therefore detailed balance is a much stronger condition than the condition that π be a stationary distribution; a general Markov chain won't satisfy detailed ...
[40]
[PDF] A Tutorial on the Spectral Theory of Markov Chains - arXiv
Aug 19, 2022 · When the number of recurrent classes r is bigger than 1, stationary distributions can be formed via convex combinations of each distribution πk, ...
[41]
[PDF] Uniform Acceleration Expansions for Markov Chains with Time ...
Mar 9, 2004 · The UA expansions can be used to justify, evaluate and refine the pointwise sta- tionary approximation, which is the steady-state distribution ...
[42]
[PDF] Introduction to Discrete Time Birth Death Models
Mar 1, 2013 · Let π be the stationary distribution for the Birth Death Chain. Then we have: πk = πk−1pk−1 + πk(1 − pk − qk)πk+1qk+1, if k ≥ 1 π0 = π0 ...Missing: recursive | Show results with:recursive
[43]
[PDF] Markov Chains and Mixing Times, second edition David A. Levin ...
Preface to second edition. Since the publication of the first edition, the field of mixing times has continued to enjoy rapid expansion.<|control11|><|separator|>
[44]
[PDF] Markov Chains and Markov Chain Monte Carlo
Detailed balance: the flow of probability mass between each pair of states is balanced: • A Markov chain satisfying detailed balance is called reversible.Missing: criterion | Show results with:criterion
[45]
[PDF] 1 Time-reversible Markov chains
A time-reversible Markov chain has the same distribution when time is reversed, where the transition rate from i to j equals the rate from j to i.
[46]
[PDF] Convergence Rates of Markov Chains
In words, Kolmogorov's Criterion asserts that a Markov chain is reversible if and only if for every cycle, the probability of traversing the cycle is the same ...
[47]
[PDF] TIME REVERSAL AND REVERSIBLE PROCESSES
One can show that the Kolmogorov criterion is equivalent with the detailed balance conditions and thus gives a necessary and sufficient condition for the ...
[48]
7. Time Reversal in Discrete-Time Chains - Random Services
Time reversal in Markov chains involves running a process backwards in time, creating a reversed chain, which is a Markov chain, but not time homogeneous in ...
[49]
5.3: Reversible Markov Chains - Engineering LibreTexts
May 22, 2022 · Every birth-death chain with a steady-state probability distribution is reversible. We saw that for birth-death chains, the equation ...
[50]
A Tutorial on the Spectral Theory of Markov Chains - MIT Press Direct
Oct 10, 2023 · Let X be a reversible Markov chain with transition matrix P ⁠. Then X is reversible if and only if it is diagonalizable with real eigenvalues ...
[51]
[PDF] Lecture 20: Reversible Processes and Queues - ECE, IISc
The M/M/1 queue's generator defines a birth-death process. Hence, if it is stationary, then it must be time-reversible, with the equilibrium distribution π ...
[52]
[PDF] Time-reversible Markov chains - San Jose State University
Example 0.3 (Ehrenfest Model for Diffusion). Suppose that M molecules are distributed among two urns; and at each time point one of the molecules is chosen ...
[53]
[PDF] Lecture 2: Markov Chains (I)
Definition. The process Xt = X0,X1,X2,... is a discrete-time Markov chain if it satisfies the Markov prop- erty: P(Xn+1 = s|X0 = x0,X1 = x1,...,Xn = xn) = P ...
[54]
[PDF] Merge Times and Hitting Times of Time-inhomogeneous Markov ...
Time-inhomogeneous Markov chains only converge under certain assumptions. In [2, p.759], Griffeath proved a form of convergence for time-inhomogeneous Markov.Missing: discrete- Dobrushin
[55]
[PDF] Local stationarity and time-inhomogeneous Markov chains - ENSAI
This paper defines locally stationary Markov models for time-inhomogeneous data, extending local stationarity, and introduces a probabilistic framework for ...Missing: steady | Show results with:steady
[56]
[PDF] A Martingale Proof of Dobrushin's Theorem for Non ... - Arizona Math
Dobrushin proved in his thesis [2] an important central limit theorem (CLT) for Markov chains in discrete time that are not necessarily homogeneous in time.
[57]
Analysis of Exchange Rates as Time‐Inhomogeneous Markov ...
Feb 22, 2022 · This paper considers the analysis of exchange rate as time inhomogeneous Markov chain with finite states since analysing exchange rates as ...Introduction · Material and Methods · Results and Discussions · ConclusionsMissing: steady | Show results with:steady