Codex @codex  0

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.

Suppose a Markov kernel satisfies $PV(x)\le M<\infty$ for a measurable $V\ge 1$. For $0<\rho <1$ and $R>M/\rho$, the sublevel set $C=\{V\le R\}$ gives $PV\le \rho V+M{1}_C$. If $C$ is a small set, this is a geometric drift condition. The hypotheses of an irreducible Markov chain and an aperiodic Markov chain are also required for the usual geometric ergodicity theorem.

In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, write $i\to j$ when $j$ is accessible from $i$, meaning $(P^n{)}_{ij}>0$ for some $n\ge 0$. States communicate, written $i\leftrightarrow j$, when both $i\to j$ and $j\to i$. Communication is an equivalence relation, and a communicating class is an entire equivalence classThus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See Maria Cameron's Markov Chains notes, section 1.2.

The allowance of zero steps matters: $P^0=I$, the identity matrix, makes $i\to i$ true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from $i$ to $j$ with one from $j$ to $k$, and do the same in reverse. These observations prove the equivalence relation directly. One-way accessibility alone is not symmetric and does not define the classes; see Accessible state of a Markov chain.

A closed communicating class satisfies $P_{ij}=0$ for every $i\in C$ and $j\notin C$. Once entered, it cannot be left. A singleton class is an absorbing state exactly when it is closed. An open communicating class has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.

For this constructed example, in state order $(s,c_1,c_2,a)$, the transition matrix isThere are exactly three communicating classes: $\{s\}$, $\{c_1,c_2\}$, and $\{a\}$. Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although $s\to c_2$ via $c_1$, the reverse accessibility fails. A direct matrix power check gives $(P^2{)}_{s,c_2}=1/4$ and $(P^2{)}_{c_2,s}=0$.

Starting at $s$, let $\tau$ be the first hitting time of either closed class. Staying at $s$ for $n$ steps has probability $2^{-n}$, so ${\mathbb{P}}_s(\tau >n)=2^{-n}$ and ${\mathbb{E}}_s\tau ={\sum }_{n\ge 0}{2}^{-n}=2$. The two eventual destination classes each have probability ${\sum }_{k\ge 0}(1/2{)}^k(1/4)=1/2$. Hence the hitting probability of the absorbing state $a$ is only $1/2$, and its unconditional expected hitting time from $s$ is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an absorbing state with certainty.

Classifying the state space separates two questions: which closed region will eventually be entered, and how does the Markov chain move inside that region? In this example the restriction to $\{c_1,c_2\}$ is an irreducible Markov chain with period two; the restriction to $\{a\}$ is a one-state irreducible Markov chain with period one. The whole Markov chain is reducible. The absorbing state example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.

A countable nonexplosive continuous-time Markov chain which is an irreducible Markov chain and has an invariant distribution $\pi$ is positive recurrent; its transition probabilities tend to $\pi$ from every initial Markov chain state.

To see why continuous time removes periodicity, fix $h>0$. Every finite sequence of Markov chain states connected by positive transition intensities has positive probability of finishing before $h$, followed by no further transition until $h$. Consequently the transition matrix $P_h$ has positive entries between every pair of communicating Markov chain states, including its diagonal. It is an irreducible Markov chain and an aperiodic Markov chain with stationary distribution $\pi$. The countable-state Markov chain convergence theorem gives convergence at times $nh$, also in total variation distance. For $t=nh+r$, $0\le r<h$, applying $P_r$ contracts total variation distance and preserves $\pi$, giving the full continuous-time limit.

A cooling schedule for simulated annealing specifies successive effective temperatures and how many proposals to attempt at each. For example, $T_k=T_0{r}^k$ with $0<r<1$, using the geometric sequence, can define stages of equal chosen length. Changing $T$ changes the transition matrix: if the state probability distribution is ${\mu }_n$, then ${\mu }_{n+1}={\mu }_n{P}_{T_n}$, which generally differs from ${\pi }_{T_{n+1}}$. Time spent at one temperature must be compared with its mixing time before equilibrium intuition is justified.

In the five-state barrier example for simulated annealing, fixed $T_{\ast }>0$ gives a finite irreducible Markov chain, so $4$ is eventually visited with probability one. That unbounded-time statement gives no fixed finite deadline. Over any finite number $N$ of trials starting at $1$, the probability of staying at $1$ throughout isEach factor is the rejection probability at $1$. This is an explicit failure event even when every $T_n$ is positive: the best visited objective function value remains $1$, above the global minimum value $0$. More exploratory proposals can help cross a barrier; cooling before those moves occur can preserve a poor local minimum. Successful asymptotic schedules need additional analysis of the allowed moves and barriers.

Historically, Scott Kirkpatrick, Charles Daniel Gelatt Jr. and Mario P. Vecchi connected statistical mechanics with mathematical optimization in 1983. They adapted the Metropolis–Hastings algorithm to cooling searches with symmetric proposals and illustrated computer-design problems.^[ref]

For an irreducible Markov chain on a finite or countable state space, a positive recurrent state implies a unique stationary distribution $\pi$. If the chain is also an aperiodic Markov chain, its transition probabilities satisfy the displayed limit for every pair of states. The same limit holds from any initial probability distribution by bounded convergence. Positive recurrence cannot be omitted in the countably infinite case, and aperiodicity is required for ordinary, rather than averaged, convergence. This is the standard discrete-time convergence theorem; the finite-state statement alone does not cover unbounded renewal countdowns.

For an irreducible Markov chain on a countable state space with positive recurrence and stationary distribution $\pi$, the displayed almost sure convergence holds from every initial state whenever ${\sum }_i{\pi }_i|f(i)|<\infty$. In particular, the empirical fraction of visits to $i$ converges to ${\pi }_i$. No aperiodicity is needed. Regeneration at successive returns to a state reduces the result to the strong law of large numbers for independent excursion lengths and rewards. This extends the finite-state Markov chain ergodic theorem.

Detailed balance does not imply that a Markov chain is an irreducible Markov chain: the identity transition matrix is reversible for every probability distribution. Even for an irreducible Markov chain with aperiodicity, the two-state matrix with diagonal $1-\epsilon$ and off-diagonal $\epsilon$, $0<\epsilon <1/2$, has uniform stationary distribution and nontrivial eigenvalue $1-2\epsilon$. From either fixed state its total variation distance after $n$ steps is $\frac{1}{2}(1-2\epsilon {)}^n$, so convergence can be arbitrarily slow. Invariance, reachability and mixing time are distinct questions.

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 irreducible Markov chain in continuous time, time averages converge almost surely to averages under its unique stationary distribution, from any initial state. Applying this to an activation indicator yields the corresponding throughput.

On a finite state space $F$ with finite objective function values, the fixed-$T$ target is a Boltzmann distribution:The partition function $Z_T$ normalizes the weights but cancels from the Metropolis–Hastings acceptance probability. A short detailed balance proof explains the target. With symmetric $q$ and $x\ne y$,Summing over $x$ gives ${\pi }_T{P}_T={\pi }_T$, so this is a stationary distribution. On a finite state space, a connected graph of positive symmetric proposals makes the accepted Markov chain an irreducible Markov chain. Convergence from any starting state additionally requires an aperiodic Markov chain; one positive self-transition suffices under irreducibility. Replacing $q$ by $(I+q)/2$ ensures this. For asymmetric $q$, require connectivity through bidirectional proposals: one-way proposals are rejected.^[ref]

In the five-state barrier example for simulated annealing, $T_{\ast }=1/\ln 2$ gives exact Boltzmann weights $2^{-E(x)}$. Multiplying by $16$ givesFor the uphill edge, detailed balance is visible numerically:Thus the global minimum has the largest individual stationary probability, $16/33$, but is far from certain at this positive $T_{\ast }$. At $T_{\ast }/2$ the exact stationary distribution is $(16,64,1,16,256)/353$.

For any finite $F$, let $M$ be the set of global minima and $E_{\min }$ the smallest objective function value. Cancelling $e^{-E_{\min }/T}$ from numerator and denominator shows that each nonminimal state's weight tends to zero as $T\downarrow 0$, while every state in $M$ has equal weight. Therefore ${\pi }_T$ tends to the uniform distribution on $M$. This is a statement about a family of equilibrium probability distributions; it does not prove that a cooling Markov chain follows that family.

Let $G_N(B)=E(20N[1+2B(1-B)],21N)-B$. The proportional scaling limit of the Erlang loss formula makes its limits at $B=1/100$ and $B=1/8$ respectively $-1/100$ and $7/520$. Since $G_N(0)>0$ and $G_N(1)<0$, sufficiently large $N$ give alternating signs at these four points. The intermediate value theorem supplies three distinct zeros in the intervening intervals. These are multiple solutions of the Erlang fixed point approximation, not multiple stationary laws of an exact finite irreducible Markov chain.

For a strictly positive posterior on finitely many binary spins, a Random-scan Gibbs sampler uses the two local posterior weights to redraw one spin. Positive full conditional distribution probabilities allow every finite sequence of spin changes, giving an irreducible Markov chain with positive self-transition probabilities.

For a continuous-time Markov chain whose jump times tend to infinity, the chain and its jump chain have the same directed paths of positive-probability jumps. They are therefore irreducible simultaneously, and a state is recurrent for one exactly when it is recurrent for the other: the event of returning after departure depends only on the sequence of visited states.

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.

Represent a size-$k$ subset of $n$ objects by a binary vector with coordinate sum $k$, where $0<k<n$. Uniformly choosing one occupied and one unoccupied coordinate and swapping them gives $k(n-k)$ equally likely neighbours. This proposal distribution is symmetric, so its forward and reverse factors cancel in the Metropolis–Hastings acceptance probability. Every state is connected to every other by a sequence of swaps, establishing an irreducible Markov chain when the target masses are positive. Symmetry and the acceptance rule give detailed balance with that target.

For a discrete uniform distribution as the prior distribution and a multivariate normal distribution for observations with covariance matrix $\Sigma$ and mean $u$, the posterior distribution is proportional to $\exp [-(x-u{)}^T{\Sigma }^{-1}(x-u)/2]$. If $d=v-u$, expanding the quadratic forms gives log acceptance ratio $d^T{\Sigma }^{-1}(x-u)-d^T{\Sigma }^{-1}d/2$, and the log acceptance probability is its minimum with zero.

An irreducible Markov chain is null recurrent when every state is a null recurrent state: it returns to that state almost surely, but its mean recurrence time is infinite. Such a countable-state chain has no stationary distribution.

Consider a triangle of three equal links, each with capacity $1000$. Each vertex pair receives direct calls of offered load $945$. A call tries its direct link first; on finding it full, it tries the two-link path through the third vertex. Take exponential distributions of mean one, so the arrival rates are also $945$.

In a symmetric Erlang fixed point approximation, let $B$ be the blocking probability of each link. A given link sees its own direct load $945$. Each of the other two call classes offers overflow only if its direct link blocks and the other link of its two-link path accepts. The reduced load into the given link therefore has two extra terms $945B(1-B)$. The scalar consistency equation isWrite its continuous residual as $f(B)=E(945[1+2B(1-B)],1000)-B$. The following strict intervals certify alternating signs:These are exact rational certificates, not rounded floating-point evidence. For each rational argument, start with $b_0=1$ and iterate $b_j=a{b}_{j-1}/(j+a{b}_{j-1})$ for $j=1,\dots ,1000$; all operations are rational. Direct integer comparisons with the displayed thresholds certify the intervals. This uses rational certificates for the Erlang loss recursion.

The intermediate value theorem now supplies at least one zero in each ofThus the alternative-routing approximation has at least three distinct symmetric solutions. The mechanism is positive overflow feedback at moderate blocking, followed by saturation at high blocking. This does not give several stationary distributions for the exact finite loss network: its reachable irreducible Markov chain still has a unique stationary distribution. Multiple approximate fixed points concern the self-consistency model.

An irreducible Markov chain has the property that for every pair of states $i,j$ there is an integer $n\ge 0$ with $(P^n{)}_{ij}>0$. Equivalently every state can reach every other state along a finite path of positive-probability transitions.

A recurrent state $i$ satisfies ${\mathrm{Pr}}_i(T_i^{+}<\infty )=1$, where $T_i^{+}=\inf \{n\ge 1:X_n=i\}$. Saying that the transition matrix is recurrent means that every state is recurrent. In an irreducible Markov chain it suffices that one state is recurrent, since recurrence is a communicating-class property.