Formalpedia

For a Markov chain with path law chainMeasure P lam, let $V$ be a square-integrable random variable determined by the trajectory from time $j+n$ onward. Then the conditional expectation $\mathbb E[V\mid\mathcal F_{\le j}]$ has a version $W$ that is measurable both with respect to the past through time $j$ and with respect to the future from time $j$ onward. Equivalently, the Markov property permits the conditional expectation to be represented by a measurable function of the current state $X_j$. The conclusion is stated using an almost-everywhere version because conditional expectations are unique only almost surely.

Let $Y$ be a measurable process on a probability space. Suppose that for every square-integrable future random variable $V$, its conditional expectation given the history through the intermediate time $k+m$ has a version $W$ that is measurable both with respect to that history and with respect to the future beginning at $k+m$. Then the maximal-correlation coefficients satisfy (...) This version-based formulation is insensitive to the almost-everywhere choice of conditional-expectation representative and is the form naturally supplied by the Markov property, where $W$ can be chosen as a measurable function of the state at time $k+m$.

Let $Y$ be a measurable process on a probability space. Assume the following Markov projection property: whenever $V$ is square-integrable and measurable with respect to the future beginning at time $k+m+n$, its conditional expectation given the history through time $k+m$ is already measurable with respect to the future beginning at time $k+m$ (in particular, this holds if that conditional expectation depends only on the state at time $k+m$). Then the maximal-correlation mixing coefficients are submultiplicative: (...) The statement includes all zero-variance cases through the convention in the definition of rhoMixingCoef.

Let $(X_n)_{n\ge0}$ be a stationary Harris-ergodic Markov chain with invariant law $\pi$. Assume there are a nonnegative function $M\in L^1(\pi)$ and a number $t\in[0,1)$ such that, for every state $x$, every $n\ge1$,

(...)

If $P$ is reversible with respect to $\pi$, then the one-step maximal-correlation coefficient is strictly less than one:

(...)

The integrable pointwise bound first yields exponential absolute regularity under the stationary law. Reversibility identifies the centered Markov operator with a self-adjoint contraction on $L^2(\pi)$; the geometric convergence excludes spectrum at modulus one and gives the strict operator-norm contraction represented by $\rho(1)$.

This theorem is the spectral bridge between the integrable-rate form of geometric ergodicity and exponential rho-mixing.

Let $(X_n)_{n\ge0}$ be the stationary Markov chain with transition kernel $P$ and invariant probability law $\mu$. Its maximal-correlation mixing coefficients obey

(...)

This is the multiplicative data-processing inequality for maximal correlation. The Markov property makes the past and the remote future conditionally independent through an intermediate state, so correlation across two consecutive time gaps contracts by at most the product of the two individual contraction factors.

Formalization Note The zero-lag endpoint is included together with the positive-lag formula and uses the standard range property of maximal correlation.

Let $P$ be a finite measure and let $(Y_i)_{i\ge0}$ be a measurable-space-valued process. For every lag $n$, its maximal-correlation mixing coefficient satisfies

(...)

The result remains valid for a finite, not necessarily normalized, measure because the coefficient is a supremum of normalized covariances and Cauchy--Schwarz bounds every candidate by one. Zero variances are handled by the convention that division by zero in the real numbers gives zero.

This theorem supplies the order bounds needed whenever rho coefficients are treated as a real-valued decay sequence.

Let $(X_n)_{n\ge0}$ be a stationary Harris-ergodic Markov chain with invariant probability law $\pi$. If its kernel is reversible with respect to $\pi$ and the chain is geometrically ergodic in total variation, then its one-step maximal-correlation coefficient is strictly contractive:

(...)

This is the spectral core of the reversible geometric-ergodicity theorem. Reversibility makes the Markov operator self-adjoint on centered $L^2(\pi)$; geometric ergodicity excludes spectrum at modulus one and yields an $L^2$ spectral gap. The coefficient $\rho(1)$ is the corresponding centered operator norm. Combined with the Markov product inequality, this single-lag contraction yields exponential rho-mixing.

Formalization Note HarrisErgodic supplies invariance and pointwise total-variation convergence, while GeometricallyErgodic supplies a common geometric rate with state-dependent prefactor.

Let $(X_n)_{n\ge0}$ be the stationary Markov chain with transition kernel $P$ and invariant probability law $\mu$, and let $\rho(n)$ be its maximal-correlation mixing coefficient. Then

(...)

The range bound is the Cauchy--Schwarz bound for correlation. The product inequality is the maximal-correlation data-processing inequality applied through the intermediate Markov state. It is the structural fact that turns any strict contraction at one lag into an exponential mixing rate.

Formalization Note The coefficient is defined from the past and future coordinate sigma-fields of the one-sided stationary path measure. The zero-lag cases are included; they are the endpoint extension of the positive-lag formula using the same range bound.

Every irreducible chain on a finite nonempty state space has exactly one stationary distribution: there exists a unique probability vector $\pi$ with $\pi P=\pi$. This is the goal theorem of the mission and the foundation of the whole Markov Chains and Mixing Times series.

For simple random walk on $\mathbb{Z}$ started at $k>0$, the probability of not visiting $0$ within $r$ steps is at most (...) The probability is the exact fraction of the $2^r$ sign strings whose walk avoids $0$ at all times $t\le r$.

For simple random walk on $\mathbb{Z}$ started at $k>0$ and any $j>0$: walks of length $r$ that touch $0$ before time $r$ and end at $j$ are equinumerous with walks ending at $-j$, and walks that touch $0$ and end positive are equinumerous with walks ending negative. Stated as exact equalities of counts of $\pm1$ step sequences, which is equivalent to the probabilistic statement since all $2^r$ sequences are equally likely.

For the coupon collector with $n\ge1$ types and any $c>0$: (...) This bound drives the top-to-random shuffle analysis later in the series.

The expected number of independent uniform draws needed to collect all $n$ coupon types is (...) where $\mathbb{E}(\tau)$ is encoded by the tail-sum $\sum_{t\ge0}\mathbb{P}\{\tau>t\}$ and $\mathbb{P}\{\tau>t\}$ is the fraction of draw sequences of length $t$ that miss some type.

For the fair unit-bet gambler absorbed at $0$ and $n$, started from fortune $k\in\{0,\dots,n\}$: the probability of reaching $n$ before $0$ is $k/n$, and the expected absorption time is $k(n-k)$. Both quantities are expressed by tail/first-passage sums over trajectories of the explicit gambler's chain.

The random walk on a finite group $G$ with increment distribution $\mu$ is irreducible if and only if the support $S=\{g:\mu(g)>0\}$ generates $G$.

The random walk on a finite group $G$ with increment distribution $\mu$ (step from $a$ to $ha$ with probability $\mu(h)$) is a Markov chain for which the uniform distribution on $G$ is stationary; and if $\mu$ is symmetric ($\mu(g^{-1})=\mu(g)$), the walk is reversible with respect to the uniform distribution.

For an irreducible chain with stationary distribution $\pi$, the time reversal $\hat P(x,y)=\pi(y)P(y,x)/\pi(x)$ is a stochastic matrix, $\pi$ is stationary for $\hat P$, and started from $\pi$ the reversed chain traverses every trajectory with the same probability as the original chain traverses the reversed trajectory: (...)

On a finite graph with no isolated vertices, simple random walk (move to a uniformly chosen neighbour) is a Markov chain; the distribution (...) satisfies detailed balance with it, and is therefore its stationary distribution.

If a probability distribution $\pi$ satisfies the detailed balance equations $\pi(x)P(x,y)=\pi(y)P(y,x)$ for all states $x,y$ of a stochastic matrix $P$, then $\pi$ is stationary for $P$. This is the standard tool for identifying stationary distributions of reversible chains.

An irreducible chain has at most one stationary distribution: if $\pi$ and $\pi'$ are both probability distributions fixed by $P$ ($\pi P=\pi$ and $\pi'P=\pi'$), then $\pi=\pi'$.