Markov chain

A Markov chain has a future conditional distribution depending on the present state alone.

A nonnegative row vector $x$, not necessarily of total mass one, is an invariant measure for a Markov chain if $x_j={\sum }_i{x}_i{p}_{ij}$. On an irreducible Markov chain, every nonzero invariant measure has positive coordinates: iterate stationarity and use a positive transition probability along a path.

For a recurrent Markov chain, start at $k$ and stop at its first positive return $T_k$. The expected visits to each state before that return form the excursion occupation measure. Its $k$th coordinate is one. Counting the return endpoint instead of the start gives the same measure. It is invariant by shifting the occupation sum one time step and using the Markov property. Any Markov chain invariant measure normalized by $x_k=1$ dominates it: iterate the stationarity equations on the state space with $k$ removed, then retain the nonnegative excursion-path terms.

On the nonnegative integers, every positive state decreases by one, while zero jumps to $j\ge 1$ with probability $p{q}^{j-1}$, $p=1-q\in (0,1)$. Its return time from zero is one plus this geometric jump, so it has mean $(1+p)/p$. Return lengths two and three occur, establishing aperiodicity; deterministic downward motion and positive jumps establish irreducibility.

For the geometric-jump countdown Markov chain, regeneration at zero givesA cycle visits positive state $j$ precisely when its jump reaches at least $j$, with probability $q^{j-1}$. Dividing this expected occupation by the mean cycle length proves the formula. Mean recurrence times are $1/{\pi }_j$, and the limiting probability away from zero is $1/(1+p)$.

A partition of a Markov chain state space is strongly lumpable when, for every target block $C$, the sum ${\sum }_{j\in C}{p}_{ij}$ is identical for all source states $i$ in a given source block. These sums define the transition matrix of the block-valued Markov chain, independently of the initial law. Failure of this condition means the projection is not guaranteed to be a homogeneous Markov chain for every initial law, although special initial laws may still produce a Markov process.

A phi-irreducible Markov chain is Harris recurrent when every set of positive irreducibility measure is hit almost surely from every state. With an invariant probability, it becomes a positive Harris recurrent Markov chain.

A discrete-time model describes individual transitions between states at successive steps. State occupancy counts, first-entry counts and transition counts are distinct quantities, especially when a state has a self-loop. With independent individuals and fixed transition probabilities, destination counts conditional on the source count have a multinomial distribution.

With a one-step early state, early diagnosis probability $a$, and non-early diagnosis probability $b$ per subsequent step, mean infections $h_i$ yield early diagnoses $e_k=a{h}_{k-1}$ and late diagnoses $n_k=b(1-a){\sum }_{i\le k-2}{h}_i(1-b{)}^{k-i-2}$. The early intensity fraction is $e_k/(e_k+n_k)$ when positive. Initial infections and endpoint conventions determine the index limits.

A Harris recurrent chain visits every measurable set of positive irreducibility measure almost surely. Positive Harris recurrence additionally supplies an invariant probability measure. The ergodic theorem for a positive Harris recurrent Markov chain gives consistency of time averages of integrable functions.

For a positive Harris recurrent Markov chain with invariant probability $\pi$ and $\int |h|d\pi <\infty$, its time average converges almost surely to the invariant expectation:This is the consistency result for Markov chain Monte Carlo averages. Independent-observation variance formulas do not follow from this theorem.

The Ehrenfest urn model moves one uniformly chosen ball between two boxes at each step. For $k\ge 1$ balls, the count in one box is a Markov chain on $\{0,\dots ,k\}$. Its stationary distribution is $2^{-k}\left(\genfrac{}{}{0ex}{}{k}{i}\right)$, and detailed balance makes it a reversible Markov chain. The chain has period two, but its mean recurrence time to the all-in-one-box state is still $2^k$.

Choose two positions independently and uniformly from $\{1,\dots ,n\}$ and swap them. This Markov chain on the symmetric group holds with probability $1/n$ and assigns probability $2/n^2$ to each unordered transposition. Its stationary distribution is uniform, and its ordinary spectral gap is $2/n$ for $n\ge 2$. The latter follows from the Aldous spectral gap theorem: the single-label continuous-time Markov chain has rate $2/n^2$ between every pair of positions, whose mean-zero eigenvalues are all $-2/n$.

On the symmetric group $S_n$, this Markov chain chooses uniformly from the identity and the $n-1$ adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities $1/n$ to existing neighbours.

For the random adjacent transposition shuffle with $n\ge 2$, the generator $P-I$ is the interchange process on a path graph with each edge rate $1/n$. The Aldous spectral gap theorem reduces its spectral gap to that of the single-label random walk. The eigenfunctions $k\mapsto \cos (\ell \pi (k-1/2)/n)$, for $0\le \ell <n$, have generator eigenvalues $-2(1-\cos (\ell \pi /n))/n$; direct substitution verifies both the interior and endpoint equations. Consequently $\gamma \sim {\pi }^2/n^3$.

For the random adjacent transposition shuffle on $S_n$ with $n\ge 2$, the position $f(\sigma )={\sigma }^{-1}(i)$ of one label is uniform on $\{1,\dots ,n\}$ in equilibrium, so ${\mathrm{Var}}_{\pi }(f)=(n^2-1)/12$. Each adjacent transposition moves the label with probability $2/n$, giving $\mathcal{E}(f,f)=(n-1)/n^2$. The Poincare inequality for a reversible Markov chain variational formula therefore gives $\gamma \le 12/[n^2(n+1)]$. In particular the continuous uniform distribution on $(0,1)$ has variance $1/12$, not $1/6$.

An absorbing state of a Markov chain has transition probability one to itself. Once the chain enters it, the chain never leaves.

A Markov kernel $K(x,\cdot )$ assigns a probability distribution to each current state $x$ and acts on a distribution $P$ by $(PK)(A)=\int K(x,A)P(dx)$.

A birth-death chain is a discrete-time Markov chain on nonnegative integers that can move only to the same state or a neighbouring state.

Independent Markov chains with transition matrices $P$ and $Q$ form a product chain with transition matrix $P\otimes Q$. If their stationary distributions are $\pi$ and $\rho$, the product distribution $\pi \otimes \rho$ is stationary.

The transition matrix of a finite Markov chain has entries

The transition probability $P_{ij}$ is the conditional probability that a Markov chain moves to state $j$ on its next step given that its current state is $i$.

A Markov chain is irreducible when every state can reach every other state along a path of positive-probability transitions.

A Markov chain with transition kernel $P$ is $\phi$-irreducible if $\phi$ is a nonzero sigma-finite measure and every measurable set $A$ with $\phi (A)>0$ satisfies ${\sum }_{n\ge 1}{P}^n(x,A)>0$ from every starting state $x$. This is positive reachability, not certain eventual hitting.

A state is aperiodic when the greatest common divisor of its positive-probability return times is one. A Markov chain is aperiodic when all its states are aperiodic.

A state is recurrent when a Markov chain started there returns to it with probability one.

A state is transient when its probability of ever returning is less than one.

The first return time to a state $i$ is

The mean recurrence time of $i$ is ${\mathbb{E}}_i{T}_i^{+}$. In a finite irreducible Markov chain with stationary distribution $\pi$, it equals $1/{\pi }_i$.

If two finite Markov chains satisfythen every positive-probability path and return cycle for $P$ also exists for $Q$. Consequently irreducibility and aperiodicity pass from $P$ to $Q$. Recurrence and mean return time need not do so, because the added transitions and changed probabilities can create escape routes or make returns less frequent.

For independent random variables with a common law, $L_n={\min }_{j\le n}{X}_j$ satisfies $L_{n+1}=\min (L_n,X_{n+1})$. The next-state law therefore depends on the past only through $L_n$.

For i.i.d. Bernoulli variables, $K_n=X_{n-1}+X_n$ hides which summand is the newest one. Given $K_n=1$, the previous value can reveal $X_n$ and thereby change the conditional law of $K_{n+1}$, so $(K_n)$ need not be a Markov chain.

A stationary Markov chain $(X_t:0\le t\le T)$ is reversible in equilibrium when it has the same finite-dimensional distributions as its time reversal $(X_{T-t}:0\le t\le T)$. Equivalently, its stationary flow satisfies detailed balance.

Under a stationary initial law, reversal leaves the law of a finite reversible-chain path unchanged. The first time an ordered occurrence of state $a$ then state $b$ appears therefore has the same distribution as the reverse ordered occurrence. Decomposition at the first entrance relates this symmetry to differences of mean hitting times. If positive diagonal return times are used instead of zero diagonal entrance times, their stationary-weighted terms cancel by Kac's lemma.

For a reversible Markov chain with stationary distribution $\pi$ and $\nu \ll \pi$, detailed balance givesTo prove this, integrate either side against a bounded test function and exchange the two endpoints using detailed balance. If $\pi =h/Z$, the output probability density function is $q_t(x)=h(x){\mathbb{E}}_{B\sim K^t(x,\cdot )}[\nu (B)/h(B)]$. A reverse simulation can therefore estimate this density ratio without evaluating a transition probability density function.

For a finite irreducible Markov chain satisfying detailed balance with $\pi$, its transition matrix is a self-adjoint operator for $⟨f,g{⟩}_{\pi }={\sum }_x\pi (x)f(x)g(x)$. For a real orthonormal eigenbasis $(f_j)$ with eigenvalues $({\lambda }_j)$,Indeed, apply the spectral decomposition of $P^t$ to the function $1_{\{y\}}/\pi (y)$, whose coefficient against $f_j$ is $f_j(y)$. For $t=0$, every eigenvalue multiplier is interpreted as one.

Detailed balance is the identity pi_i P_ij = pi_j P_ji for every pair of states.

For a continuous-time Markov chain with transition rates $q_{ij}$, detailed balance isfor every pair of distinct states. A probability distribution satisfying these equations is an invariant distribution of a continuous-time Markov chain, because summing over incoming rates gives $\pi Q=0$. Under the standard nonexplosion assumptions, the equilibrium chain is reversible.

For a reversible transition matrix $P$ with invariant distribution $\pi$,

For a finite irreducible Markov chain with at least two states satisfying detailed balance, its Dirichlet form of a Markov chain obeysExpand $f-\pi (f)$ in an orthonormal eigenbasis. The denominator is ${\sum }_{j\ge 2}{a}_j^2$, and the numerator is ${\sum }_{j\ge 2}(1-{\lambda }_j)a_j^2$. Their ratio is at least $1-{\lambda }_2$ and equality holds for the second eigenfunction. Thus the optimal Poincare inequality for a reversible Markov chain constant is $1/\gamma$, for the ordinary rather than absolute spectral gap.

On an unweighted graph, the discrete Dirichlet energy is proportional to ${\sum }_{xy\in E}(f(x)-f(y){)}^2$. It measures the squared variation of a function across edges.

The canonical paths comparison theorem compares two reversible chains by routing every transition of one chain along a path of transitions of the other. The maximum capacity-normalized path congestion bounds the ratio of their Dirichlet forms and hence their spectral gaps.

Choose a directed path ${\eta }_{xy}$ of positive-probability transitions for each ordered pair of states in a finite reversible Markov chain. Write $Q(e)=\pi (u)P(u,v)$ for a directed edge $e=(u,v)$, and let $N_e(\eta )$ count its occurrences. DefineThe Cauchy-Schwarz inequality bounds $(f(x)-f(y){)}^2$ by $|{\eta }_{xy}|$ times the sum of squared differences along the path. Multiply by $\pi (x)\pi (y)/2$, sum and interchange finite sums. The identity ${\mathrm{Var}}_{\pi }(f)=\frac{1}{2}{\sum }_{x,y}\pi (x)\pi (y)(f(x)-f(y){)}^2$ proves the bound. This convention counts directed edges and retains the factor $1/2$ in the Dirichlet form of a Markov chain.

For a transient weighted graph, $H_0$ is the completion of the finitely supported functions in the norm $\Vert f{\Vert }_{H_0}=\mathcal{E}(f,f{)}^{1/2}$. Its elements have finite Dirichlet energy and vanish at infinity in the energy sense.

The relaxation time of a finite reversible lazy Markov chain is the reciprocal of its spectral gap: $t_{\mathrm{rel}}=(1-{\lambda }_2{)}^{-1}$.

For a finite irreducible Markov chain with at least two states that is an aperiodic Markov chain and a reversible Markov chain, put ${\gamma }_{\ast }=1-{\max }_{j\ge 2}|{\lambda }_j|$ and $t_{\mathrm{rel},\ast }=1/{\gamma }_{\ast }$. This is the reciprocal of the absolute L2 spectral gap of a reversible Markov chain. It agrees with the reciprocal of the ordinary spectral gap $1-{\lambda }_2$ for a lazy Markov chain, but need not agree when there are negative eigenvalues.

The spectral profile minimizes a Dirichlet-form Rayleigh quotient over nonnegative functions supported on sets of stationary mass at most $r$.

For the isoperimetric profile ${\Phi }_{\ast }(r)$ of a reversible chain and $r\le 1/2$,

For a reversible Markov chain with stationary flow $Q(x,y)=\pi (x)P(x,y)$, the conductance of a set $A$ isIts Cheeger constant minimizes the boundary flow divided by the smaller stationary mass of the two sides of the cut.

The Cheeger constant of a finite reversible chain is the least stationary boundary flow divided by the smaller stationary mass of a set and its complement.

For a reversible chain with spectral gap $\gamma$ and Cheeger constant $\Phi$,

The $\epsilon$-mixing time is the least $t$ for which every initial state has total variation distance at most $\epsilon$ from the invariant distribution after $t$ steps.

If $r={\max }_{j\ge 2}|{\lambda }_j|$ for a finite irreducible Markov chain with at least two states, then its worst-case total variation distance from its stationary distribution satisfies $d(t)\ge r^t/2$. Choose a possibly complex eigenfunction $f$ for an eigenvalue of modulus $r$, normalize ${\max }_x|f(x)|=1$, and start where the maximum is attained. Since $\pi (f)=0$, $|P^{t}f(x)-\pi (f)|=r^t$; the defining sum for total variation distance bounds this difference by $2d(t)$. For $0<r<1$, this yields $t_{\mathrm{mix}}(\epsilon )\ge (r/(1-r))\log (1/(2\epsilon ))$ for $0<\epsilon <1/2$, because $-r\log r\le 1-r$.

For a finite Markov chain with transition matrix $P$, define $\bar{d}(t)={\max }_{x,y}\Vert P^t(x,\cdot )-P^t(y,\cdot ){\Vert }_{\mathrm{TV}}$. If $\pi$ is a stationary distribution and $d(t)={\max }_x\Vert P^t(x,\cdot )-\pi {\Vert }_{\mathrm{TV}}$, then $d(t)\le \bar{d}(t)\le 2d(t)$. The first bound follows by writing $\pi ={\sum }_y\pi (y)P^t(y,\cdot )$ and using the triangle inequality; the second uses the triangle inequality through $\pi$.

A randomized stopping time $\tau$ is a strong stationary time for a Markov chain with stationary distribution $\pi$ when $X_{\tau }$ has distribution $\pi$ and is independent of $\tau$. Equivalently,

For a finite Markov chain with stationary distribution $\pi$, the separation distance from an initial state $x$ isIf $\tau$ is a strong stationary time, then $s_x(t)\le {\mathbb{P}}_x(\tau >t)$, and total variation distance is at most separation distance.

For a finite transitive reversible chain with nontrivial eigenvalues ${\lambda }_i$,

A sequence of chains exhibits cutoff when its distance from stationarity drops from near one to near zero in a time window negligible compared with its mixing-time scale.

The ratio convention for cutoff for Markov chains requires $t_{\mathrm{mix}}^{(n)}(\epsilon )/t_{\mathrm{mix}}^{(n)}(1-\epsilon )\to 1$ for every fixed $0<\epsilon <1/2$, with positive denominators eventually. Equivalently, any two fixed levels have asymptotically equal mixing times. This convention permits a bounded-time jump; definitions which additionally require diverging mixing times exclude such a jump. For nonlazy simple random walk on the complete graph $K_n$, every fixed-level mixing time is eventually one.

For finite irreducible Markov chains that are aperiodic Markov chains and reversible Markov chains, the ratio definition of cutoff and $T_n=t_{\mathrm{mix}}^{(n)}(1/4)\to \infty$ imply the Peres product condition, with ${\gamma }_n=1-{\lambda }_{2,n}$. If ${\gamma }_n{T}_n\le B$ on a subsequence, then ${\gamma }_{\ast ,n}\le {\gamma }_n$ and the eigenvalue lower bound for total variation mixing giveFor sufficiently small fixed $\epsilon$, this contradicts the limit one forced by cutoff for Markov chains. The same argument proves the stronger conclusion ${\gamma }_{\ast ,n}{T}_n\to \infty$.

The random-to-top shuffle chooses one uniformly random card and moves it to the top of the deck. The time at which every card has been chosen is a strong stationary time, yielding cutoff at $n\log n$ with a window of order $n$.

The top-to-random shuffle removes the top card and inserts it in a uniformly random position. Under the uniform measure on permutations it is the time reversal of the random-to-top card shuffle, so the two shuffles have the same total-variation mixing profile.

A sequence of chains exhibits pre-cutoff if there are constants $0<A<B<\infty$ and times $t_n$ such that the worst-case distance tends to one at $A{t}_n$ and to zero at $B{t}_n$. For reversible chains, the product condition $t_{\mathrm{rel}}=o(t_{\mathrm{mix}})$ is necessary for pre-cutoff.

For $\tilde{P}=(1-a)P+a\Pi$, where every row of $\Pi$ equals the stationary distribution $\pi$,The perturbation superposes gradual exponential mixing on the original profile and can destroy pre-cutoff.

A shift-refresh chain cyclically moves a pointer through the coordinates of a bit vector and replaces the visited bit by an independent fair bit. Once the pointer walk has visited every residue, all coordinates have been refreshed, giving a strong stationary time.

If adjacent states admit one-step couplings that contract a path metric by a common factor, then the induced Wasserstein distance contracts by the same factor for arbitrary starting distributions.

The noisy voter model updates a chosen vertex either by replacing its spin with fresh random noise or by copying a neighboring spin. A positive refresh probability destroys conserved opinions and permits contractive coupling bounds even on nonregular graphs.

A lumped Markov chain records only a partition class of the original state. It is Markov when the transition probability into every class is constant within each source class.

A hitting probability is the probability of reaching one set before another and solves a discrete harmonic boundary problem.

With three evenly matched players, the previous winner plays the previous spectator. A pair of successive distinct winners $ij$ moves to $jj$ or $jk$ with equal probabilities, where $k$ is the remaining player. The transient states form two directed 3-cycles and each step has absorption probability one half. Starting with a game between two specified players, their overall winning probabilities are each $5/14$, while the original spectator wins with probability $2/7$.

The hitting probability of a set is one on that set and transition-harmonic elsewhere by the Markov property. Finite-horizon hitting probabilities begin at the boundary indicator and increase through the same positive transition recursion. Any nonnegative solution dominates every iterate; monotone passage to infinite time shows that it dominates the hitting probability. This proves minimality without requiring almost-sure hitting.

A splitting probability is the probability that a stochastic process reaches one target before competing targets. For a diffusion it is harmonic for the Kolmogorov backward equation, with boundary values one on the selected target and zero on the others.

The first-passage time to a target set $A$ is $T_A=\inf \{t\ge 0:X_t\in A\}$. It is also called a hitting time.

For standard Brownian motion and $a>0$, $T_a=\inf \{t\ge 0:B_t\ge a\}$ is finite almost surely andThe Brownian reflection principle gives this distribution function. The Brownian scaling identity $T_{ca}\stackrel{d}{=}{c}^2{T}_a$ and the Strong Markov property show its probability distribution is a strictly stable distribution with index $1/2$.

For a positive level $a$, this density describes the first-passage time of $B_t+ct$. The Girsanov theorem multiplies the zero-drift density by the stopped likelihood $e^{ca-c^{2}t/2}$. Its total mass is one for nonnegative drift and $e^{2ac}$ for negative drift; the latter has remaining mass at infinite hitting time.

When $d=\sqrt{c^2+2r}$ is real and nonnegative, the discounted drifted Brownian first-passage density is $e^{a(c-d)}{h}_d(t)$. Integrating yields $e^{a(c-d)}\Phi ((dT-a)/\sqrt{T})+e^{a(c+d)}\Phi ((-a-dT)/\sqrt{T})$. In a Black-Scholes model with $c=(r-{\sigma }^2/2)/\sigma$, the identity $c^2+2r=(r+{\sigma }^2/2{)}^2/{\sigma }^2$ ensures this formula covers every real interest rate.

For $Y_t=y+B_t+at$, $y>0$, and $S=\inf \{t\ge 0:Y_t=0\}$,where $e^{-\lambda \infty }=0$. The diffusion generator is $\frac{1}{2}{\partial }_{yy}+a{\partial }_y$. Its bounded eigenfunction on the positive half-line with boundary value one is $u(y)=\exp [-y(a+\sqrt{a^2+2\lambda })]$, giving the formula through the discounted boundary-hitting representation. The zero-discount limit is the hitting probability $e^{-2y\max (a,0)}$.

For standard Brownian motion, set $H_a=\inf \{t:B_t\ge a\}$ and $T_a=\inf \{t:B_t>a\}$. The Strong Markov property and immediate positive excursions give $T_a=H_a$ almost surely for each fixed $a\ge 0$. However, these level-indexed processes are not indistinguishable stochastic processes. Almost surely the random level $A={\sup }_{t\le 1}{B}_t$ is positive and exceeds $B_1$. It is first attained before time one but is not exceeded until after time one, so $H_A<1<T_A$. The simultaneous-equality event therefore has probability zero. The strict passage process $T_a$ is the right-continuous choice needed for a subordinator.

For standard Brownian motion started at zero, $H_a=\inf \{t\ge 0:B_t\ge a\}$ is finite almost surely for $a\ge 0$ andThe Brownian reflection principle proves finiteness. For $u\ge 0$, the Exponential martingale for Brownian motion stopped at $H_a\wedge t$ is bounded by $e^{ua}$. The dominated convergence theorem gives $\mathbb{E}{e}^{ua-u^2{H}_a/2}=1$, and taking $u=\sqrt{2\lambda }$ gives the transform.

When a first-passage time $\tau$ has an absolutely continuous distribution, its density is $f_{\tau }(t)=-S^{\prime }(t)$, where $S(t)=\mathbb{P}(\tau >t)$ is its survival function. In a continuous-time Markov chain, this density is the total probability flux from surviving states into the absorbing set.

For a diffusion with backward generator $L$, the mean first-passage time satisfies $L\tau =-1$ in the interior, with the backward forms of the process's boundary conditions.

The waiting time for a specified directed edge to be traversed differs from the waiting time to visit its terminal state. First-step equations include no continuation term when the designated transition succeeds, but still count that last step. They can also be derived by augmenting the chain with an absorbing success state.

The survival probability is $Q(x,t)={\mathbb{P}}_x(T_A>t)$. When absorption eventually occurs,

Suppose an urn starts with $m$ green balls and $m+2$ red balls. Drawing green removes one green ball, while drawing red adds one green and one red ball. The difference remains two, and $h(g)=1/(g+1)$ is harmonic for the green-ball chain. Stopping $h$ on hitting $0$ or $N$ and then letting $N$ tend to infinity gives termination probability

For a target set $A$, the expected hitting time $g(i)={\mathbb{E}}_i{T}_A$ satisfies $g=0$ on $A$ andoutside $A$, whenever the expectation is finite.