Phi-irreducibility Created 2026-10-06 Updated 2026-11-05
A Markov chain with transition kernel is -irreducible if is a nonzero sigma-finite measure and every measurable set with satisfies from every starting state . This is positive reachability, not certain eventual hitting.
P. H. Peskun 2026-11-05
P. H. Peskun authored the 1973 paper underlying Peskun ordering, a comparison of the efficiency of Markov chain Monte Carlo algorithms with the same stationary target.[ref]
For finite reversible Markov chains, increasing every off-diagonal transition probability while preserving the stationary law cannot increase the asymptotic variance of time averages. The comparison formalizes why spending less time repeating the current state can help statistical estimation, provided the ordering's hypotheses hold. It compares the variance of estimators, not merely their one-step acceptance rates.[ref]
Pseudo-Poisson process Created 2026-10-25 Updated 2026-11-05
A Markov chain with transition kernel , sampled at an independent Poisson process of rate , is a Pseudo-Poisson process. Its infinitesimal generator is and its transition semigroup is . Conditioning on proves the latter formula, and differentiation at zero gives the former. Its resolvent operator is for , by integrating the nonnegative scalar Poisson weights. The series converge in operator norm on bounded Borel measurable functions.
For a prepared normalized pure state and a final projective measurement onto the normalized state , unitary time evolution gives the displayed probability, by the Born rule. This depends on the preparation, final measurement, and time-evolution operator; it does not assume a classical Markov chain of transitions.
For a simple random walk on an infinite regular tree of degree , every vertex other than the chosen root has one neighbour closer to the root and farther away. The graph distance from the root is therefore a nearest-neighbour Markov chain on the nonnegative integers, with the displayed bulk transition probabilities and a certain outward step from zero. For shell probabilities ,
Shell probabilities include all vertices at the given distance. They differ from single-vertex probabilities by the shell size, at the root and for .
On the symmetric group , this Markov chain chooses uniformly from the identity and the 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 to existing neighbours.
Random transposition shuffle Created 2026-10-06 Updated 2026-11-05
Choose two positions independently and uniformly from and swap them. This Markov chain on the symmetric group holds with Probability and assigns Probability to each unordered transposition. Its stationary distribution is uniform, and its ordinary spectral gap is for . The latter follows from the Aldous spectral gap theorem: the single-label continuous-time Markov chain has rate between every pair of positions, whose mean-zero eigenvalues are all .
Random walk on a graph Created 2026-09-24 Updated 2026-11-05
A random walk on a graph is a Markov chain whose allowed moves follow the graph edges. For the simple random walk on an unweighted graph, a graph vertex of positive finite vertex degree chooses each neighbor with transition probability . A weighted graph instead uses normalized edge weights, and directed graph edges permit asymmetric transitions. At an isolated graph vertex, a holding or termination convention is needed.
On a three-vertex path , the transition matrix in that order is
Its stationary distribution is because the central graph vertex has twice the vertex degree of either endpoint. Starting at , the probability distribution nevertheless alternates between the two parts of the bipartite graph, so stationarity does not by itself imply convergence. Hitting times, recurrence, and mixing times ask different questions about the same Markov chain.
Ravi Montenegro 2026-11-05
Ravi Montenegro contributed, with Sharad Goel and Prasad Tetali, to bounds on mixing time of a Markov chain using the spectral profile. Their approach adapts Faber-Krahn inequalities to finite Markov chains and compares the resulting bounds with conductance of a Markov chain methods. It captures information at multiple set sizes that a single bottleneck estimate can miss.[ref]
A reactive strategy cooperates with probability after the opponent cooperated and probability after the opponent defected. It ignores its own previous action. Independent behavioural randomization gives a four-state joint-action Markov chain. The reduced marginal recurrences depend on the prescribed initial action distribution.
An irreducible Markov chain is recurrent exactly when every nonnegative superharmonic function for a Markov chain is constant. In the recurrent case, absorb the chain at . The inequality and almost-sure hitting give ; exchange . In the transient case, the hitting probability of a state is one there and satisfies the superharmonic inequality, but its one-step average at is the strictly smaller return Probability. It is a nonconstant example.
Recurrence survives deletion of self-transitions Created 2026-10-14 Updated 2026-11-05
An irreducible recurrent discrete-time Markov chain with at least two states has everywhere. Removing repeated consecutive states from a positive-probability path proves irreducibility of its discrete-time jump chain. Each sojourn in a state is almost surely finite; infinitely many visits to a recurrent state therefore correspond to infinitely many distinct returning sojourns. The jump chain remains recurrent, although deleting holding times may change periodicity.
Recurrent state Created 2026-09-24 Updated 2026-11-05
A state is recurrent when a Markov chain started there returns to it with Probability one.
Relaxation time Created 2026-09-24 Updated 2026-11-05
The Relaxation time of a finite reversible lazy Markov chain is the reciprocal of its spectral gap: .
Renewal equation Created 2026-10-06 Updated 2026-11-05
A renewal equation decomposes a process at its first renewal. For returns of a Markov chain to a fixed state, is the first-return probability and the probability of being at that state at time . Their probability generating functions satisfy .
For , consider the Markov chain on the nonnegative integers with the displayed transition probabilities. From zero it starts a new upward run; from each positive state it either increments or resets. Writing , its stationary distribution is
The balance equations give and for ; the geometric series normalizes the result, and the zero-state equation agrees. It is an irreducible Markov chain and is positive recurrent. Equivalently, its first return time to zero is one plus a geometric random variable with success probability , so its mean recurrence time is . Return paths of lengths two and three also make it aperiodic.
Reversible Markov chain Created 2026-09-24 Updated 2026-11-05
A stationary Markov chain is reversible in equilibrium when it has the same finite-dimensional distributions as its time reversal . Equivalently, its stationary flow satisfies Detailed balance.
Separation distance Created 2026-09-24 Updated 2026-11-05
For a finite Markov chain with stationary distribution , the Separation distance from an initial state is
If is a strong stationary time, then , and total variation distance is at most Separation distance.
Simple random walk on the integer line Created 2026-09-24 Updated 2026-10-14
A simple random walk on the integer line starts at and takes independent and identically distributed random variables as unit increments, with
The simple symmetric random walk has ; a biased random walk has . At or every step is deterministic, giving or respectively.
Count the rightward steps using indicator functions:
Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at the endpoint means exactly three rightward steps and one leftward step. There are possible orders, so its probability is , equal to in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass function
In particular, the endpoint must have the same integer parity as : . For the support of a probability distribution is exactly . At only even integers in are reachable; at only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.
Figure 1.
Exact binomial endpoint probabilities for fair walks of 20 and 80 steps and a biased walk of 80 steps; only even endpoints are possible.
Details.
The endpoint identity and the binomial distribution give the expected value, variance, and standard deviation
A short direct check gives and , hence . Then apply linearity of expectation and the variance of a sum of independent random variables.
The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from to , while shrinks from to . At , the standard deviation is , or times the fair width, and . Centering and dividing by each walk's own standard deviation gives, for ,
This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is : approximately for the fair -step walk, for the fair -step walk, and for the biased -step walk.
The positions themselves are dependent. For , , where the second term is independent of . Their covariance is therefore
For example, in the fair case allows or , whereas allows or . Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities are
These transition probabilities are the same at every time and every integer position: shifting both and by the same integer leaves unchanged. Thus the Markov property and independent increments coexist with dependent positions.
Stationarity equations 2026-10-25
For a discrete-time Markov chain with transition matrix , these equations, together with and , say that is a stationary distribution. Incoming probability mass equals the current mass at each state. They are global balance equations and do not require detailed balance.