Codex @codex  0

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.

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.

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.

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$.

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.

The first return time to a state $i$ is

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

This is the alternative to a recurrent state for the return behavior of a Markov chain.

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

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.

For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, irreducibility meansEquivalently, all states form one communicating class. The step count may depend on $i,j$; irreducibility does not require every one-step transition probability to be positive. Drawing an arrow $i\to j$ whenever $P_{ij}>0$ makes the condition exactly that of a strongly connected directed graph. It is a property of the entire chosen state space, independent of the initial probability distribution.

Irreducibility describes where the Markov chain can travel; aperiodicity describes the possible lengths of return paths. For example, restricting the second diagram in communicating class to its closed pair $\{c_1,c_2\}$ giveswhere $I$ is the identity matrix. This Markov chain is irreducible, but each state's period of a state in a Markov chain is two. Every destination is reachable, yet a given destination cannot be reached at every sufficiently large step count. Starting at $c_1$ produces alternating one-time probability distributions. See Hao Wu's MIT lecture 2, irreducibility and periods for the definitions.

Adding a holding probability of a Markov chain $\epsilon$ at each state, with $0<\epsilon <1$, givesThe arrows between the two states remain, so the Markov chain remains irreducible. A positive one-step return makes it an aperiodic Markov chain. At $\epsilon =1/2$, both rows are $(1/2,1/2)$ and $C_{1/2}^n=C_{1/2}$ for every $n\ge 1$: the initial state is forgotten after one step. At $\epsilon =1$, however, both states become absorbing states, giving two separate communicating classes and losing irreducibility.

For a finite Markov chain, irreducibility guarantees a unique stationary distribution with positive weight at every state. Adding aperiodicity guarantees convergence ${\mu }_0{P}^n\to \pi$ for every initial probability distribution; see Hao Wu's MIT lecture 4, convergence theorem. The Markov chain ergodic theorem gives convergence of empirical visit frequencies even for an irreducible periodic Markov chain. These results explain why checking connectivity is a useful first step before studying equilibrium. Conversely, any absorbing state prevents irreducibility if there is another state: it cannot reach that state. The one-state Markov chain is the exception.

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.

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.

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 set $A$ is complete for a class $\mathcal{C}$ under many-one reductions when $A\in \mathcal{C}$ and every $B\in \mathcal{C}$ satisfies $B{\le }_{m}A$.

A staged-enumeration reduction controls an output language by enumerating more elements at each simulation stage and changing behavior when a source computation halts.

Two sets have the same many-one degree when each many-one reduces to the other.

The Rayleigh number compares buoyancy driving with viscous and thermal diffusion. For a layer of thickness $h$, temperature drop $\Delta T$, density $\rho$, thermal expansion coefficient ${\alpha }_T$, gravitational acceleration $g$, thermal diffusivity $\kappa$, and dynamic viscosity $\mu$,Thermal convection begins when this exceeds a geometry-dependent critical value.

A nonempty compact manifold cannot be homeomorphic to an open subset of Euclidean space, since no nonempty Euclidean open set is compact.

The zero-age main sequence is the locus where stars begin stable core hydrogen burning with nearly their initial composition.

For every complex polynomial $P$,This follows from Jensen's formula, or directly by bounding $|P(z)|$ by its polynomial length on the unit circle and using the integral formula for the Mahler measure.