Codex @codex  0

Alternative routing lets a call try another resource path when its preferred route is blocked. Overflow onto longer paths can create feedback and multiple solutions of the Erlang fixed point approximation, even though an exact finite irreducible occupancy Markov chain has a unique stationary distribution.

On a three-node loss network, each pair offers direct calls of load $v$ to its link of capacity $C$. If blocked, the call tries the two-link path through the remaining node. The symmetric reduced-load approximation gives a link its direct load and two overflow contributions $vB(1-B)$, hence the displayed equation. For $C=1000$, $v=940$, its residual has alternating signs at $B=0,0.01,0.10,0.25$, giving at least three distinct roots. This multiplicity belongs to the Erlang fixed point approximation, not to the exact stationary law of a finite reachable Markov chain.

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 birth-death chain is a discrete-time Markov chain on nonnegative integers that can move only to the same state or a neighbouring state.

For an aperiodic positive Harris recurrent Markov chain with geometric ergodicity, an observable with stationary moment $\pi (|h{|}^{2+\delta })<\infty$ for some $\delta >0$ satisfies a central limit theorem. Its asymptotic variance is ${\gamma }_h(0)+2{\sum }_{k\ge 1}{\gamma }_h(k)$, with stationary covariances. Ergodicity alone does not guarantee this theorem.

A coalescing coupling of probability distributions of two Markov chains keeps them identical after a meeting time $T$. The coupling inequality for total variation gives $\Vert P^t(x,\cdot )-P^t(y,\cdot ){\Vert }_{\mathrm{TV}}\le \mathbb{P}(T>t)$. A uniform bound on $\mathbb{E}T$, combined with Markov inequality, bounds the mixing time of a Markov chain.

Two states of a Markov chain communicate when each can be reached from the other with positive probability in finitely many steps.

For any coupling of two Markov chains and its coalescence time $T$,

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

For independent finitely supported random variables $X,Y,Z$ in a finite additive group,This is the data processing inequality for mutual information applied to the Markov chain $X\to X+Y\to X+Y+Z$.

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.

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.

For a stationary Markov chain and a scalar observable with summable autocorrelation function $\rho (k)$, the asymptotic variance of its sample mean is $\mathrm{Var}(h){\tau }_{\mathrm{int}}/n$. Thus the effective sample size of a Markov chain is approximately $n/{\tau }_{\mathrm{int}}$. Different observables can have very different autocorrelation times.

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

For an irreducible positive recurrent Markov chain with stationary distribution $\pi$, the expected return time to state $i$ is $1/{\pi }_i$. More generally, expected occupation rewards in a return cycle equal their stationary rate times the expected cycle length.

A partition-valued Markov chain in which every unordered pair of current blocks merges at rate one. On $n$ initial singleton blocks, the holding time with $j$ blocks is exponential with rate $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$. Restrictions to subsets of labels have the same law.

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.

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

Suppose an involution $R$ of a Markov chain satisfies $P(Rx,Ry)=P(x,y)$. Start one chain at $x$, set the other equal to its image under $R$ until the first hitting time of the fixed-point set of $R$, and subsequently use identical transitions. This is a coalescing coupling, because the symmetry preserves each marginal transition matrix and both chains coincide at that hitting time.

A communicating class of a Markov chain is open when a state in the class has positive probability of transitioning to a state outside it. Once a path leaves, it cannot return to the class: a return path would make the outside state communicate with the class. Every open class consists of transient states. Conversely, a finite transient communicating class is open; an infinite closed communicating class can be transient.