Codex @codex  0

A Gibbs sampler updates one coordinate by drawing from its full conditional distribution, leaving the others unchanged and using their current values. Each coordinate kernel $K_i$ preserves the target joint law $P$: integrate first over the unchanged coordinates, then over the old coordinate, and finally draw the new coordinate from the same conditional distribution. The resulting joint law is again $P$. In the discrete notation, if two states share the remaining coordinates,which is symmetric in $x_i,x_i^{\prime }$. Thus a coordinate update satisfies detailed balance. A systematic full sweep has kernel $K_1\cdots K_k$ and remains invariant because each factor preserves $P$. A fixed-probability random-scan mixture also preserves $P$; the mixture is reversible, whereas a systematic composition need not be.

In the autologistic binary-image model, count each neighboring pair once. Changing one pixel from zero to one raises $n_1$ by one and $n_2$ by the number $z_{ij}$ of neighboring ones. The ratio of its two conditional weights is $\exp (\alpha +\beta z_{ij})$. ThereforeFor single-site Gibbs sampling, select a pixel, compute its current neighbor sum and replace it by a draw from a Bernoulli distribution with this probability. One may use random scans or complete ordered sweeps. The normalizing constant is not needed. For finite $\alpha ,\beta$, every conditional probability lies strictly between zero and one; the finite chain is irreducible and has self-transitions, so its stationary law is unique and iterating converges to it.

For checkerboard Gibbs sampling, no edge joins two black pixels or two white pixels. Conditional on the whites, the black-pixel law factorizes:Draw all black pixels independently with these probabilities, then draw all white pixels independently conditional on the newly drawn blacks. Each color block is a full conditional update, so the two-block sweep preserves the joint target. Pixels of the same color can be updated together because their conditional distribution factorizes.

For the noisy image, the log likelihood contributes $-\frac{1}{2}{\sum }_v(y_v-x_v{)}^2$. Since $x_v^2=x_v$, dropping terms independent of $x$ givesThe Gaussian-noise posterior for an autologistic image therefore has conditional probabilitiesUse this probability in both single-pixel and sequential color-block schemes. The independent observation factors change only the local field, so conditional independence within each color is retained. The same invariance proof then targets the posterior distribution rather than the prior.

Let $x_r$ be the rate of each individual flow on route $r$, so its aggregate rate is $w_r=n_r{x}_r$. The feasible allocations satisfy ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. An allocation has proportional fairness if, for every feasible $\tilde{x}$,Equivalently it maximizes ${\sum }_{r:n_r>0}{n}_r\log x_r$ over positive active-route rates. This is the first-order optimality condition for a concave objective on a convex set. Rates for absent flows can be set to zero.

For the linear flow network, put $N={\sum }_{r=0}^I{n}_r$ and $M={\sum }_{i=1}^I{n}_i$. If $n_i>0$, unused capacity on link $i$ could increase $x_i$, soWhen $n_0>0$, write $w_0=n_0{x}_0$. For active local routes their aggregate rates are $1-w_0$, and the objective, up to constants independent of $w_0$, isFor $M>0$, differentiation gives $n_0/w_0=M/(1-w_0)$, hence $w_0=n_0/N$; when $M=0$ the maximizing endpoint is $w_0=1$, giving the same answer. Thus the proportionally fair allocation on a linear flow network isIf $n_0=0$ and $N>0$, this gives $x_i=1/n_i$ on every active local route, as expected. No departure occurs at the empty state.

Independent Poisson processes of flow arrivals and independent exponential distributions of document sizes make the count vector a continuous-time Markov chain. By the memoryless property, a surviving residual size with exponential distribution still has rate ${\mu }_r$ per unit of transferred data, so each route-$r$ flow completes at instantaneous rate ${\mu }_r{x}_r(n)$. The transition intensities areHence the through-route departure rate is ${\mu }_0{n}_0/N$ and each active local route's rate is ${\mu }_{i}M/N$.

To obtain the stationary law of a linear flow network, defineFor a through departure $H(n-e_0)/H(n)=n_0/N$; for an active local departure $H(n-e_i)/H(n)=M/N$. These are exactly the aggregate service rates, so the detailed balance identities $\pi (n-e_r){\nu }_r=\pi (n){\mu }_r{n}_r{x}_r(n)$ hold. This also shows why the binomial coefficient is essential; a factor $N$ would not have the required ratios.

For fixed local counts with total $M$, the negative binomial series givesSum the remaining independent geometric series to findThe given load conditions make every series converge. Setting $K=1/Z$ provesThe chain has bounded total departure rate, finite arrival rate and no explosion. With positive arrival rates it is irreducible, and this normalized invariant law gives the positive recurrent Markov chain property; zero arrival rates restrict the stationary support to the corresponding reachable class.

Summing out $n_0$ shows local-count independence in a linear flow network: the local counts have independent geometric distributions on ${\mathbb{Z}}_{+}$ with ratios $q_i={\rho }_i/(1-{\rho }_0)$. ThereforeThey are independent of one another under the stationary marginal, despite sharing the random through-flow population. The through count is generally dependent on them.

At each transition, choose a coordinate uniformly and independently of the previous coordinate choices. Draw a fresh value from that coordinate's full conditional distribution given the current remaining coordinates, and keep all other coordinates fixed. This supplies the random-selection and conditional-draw operations lost in the TeX transcription. The update depends only on the current vector and fresh randomness, which proves the Markov property. The printed mathematical requests are the kernel and its detailed balance, answered in the following two subsections.

Let $\bar{\pi }$ be the normalized target and ${\bar{\pi }}_{-i}$ its marginal distribution. A coordinate-$i$ kernel $P_i$ leaves $x_{-i}=x_{-i}^{\prime }$ and has the joint old-new measureThis is symmetric in the old and new state: the common remaining coordinates are fixed and the two conditional factors exchange places. Thus each coordinate kernel satisfies detailed balance. Averaging them with the fixed weights $1/p$ provesIntegrating out the old state proves invariance of $\bar{\pi }$. The common normalization cancels, so detailed balance can also be written with the unnormalized target. This establishes detailed balance of a random-scan Gibbs sampler and a reversible Markov chain. Fresh independent random choices make the update a Markov chain, as explained above; invariance is not an assertion that an arbitrarily initialized chain starts in stationarity.

First consider an M-M-K queue with $K$ servers, arrival rate $\lambda$, and service rate $\beta$ at each server. Assume $\lambda <K\beta$ so that a stationary distribution exists. Its population is a birth-death process with rates $q_{n,n+1}=\lambda$ and $q_{n,n-1}=\beta \min (n,K)$. The equilibrium probabilities satisfy detailed balanceThus the population process is a reversible Markov chain. In its time reversal of a continuous-time Markov chain, forward departures become upward jumps whose rate is the constant $\lambda$, independent of the state. They can be generated by a rate-$\lambda$ Poisson process independent of the initial reversed state. Reversing time preserves the Poisson process law, proving the equilibrium departure process is Poisson with rate $\lambda$, the Burke theorem for a multi-server queue.

The same argument gives the departure component of quasireversibility needed for the tandem calculation: the present upstream population is independent of its entire past departure process. Indeed, these departures become future arrivals in the reversed chain, independent of its initial population. First check this on finite time windows, then extend to the full past. A Poisson output alone, without this independence, would not justify multiplying queue-empty probabilities.

Now let $a=\nu \mu$, where $\mu$ denotes the mean service time at passport control, so the service rate at each of its two servers is $1/\mu$. The stationary distribution of the M-M-s queue with $s=2$ has normalizing sumHence its empty probability is $(2-a)/(2+a)$. Its output feeds a stable M-D-1 queue with rate $\nu$ and deterministic service time $\tau$. In a stationary work-conserving single-server queue, the busy fraction is the rate of completed work, $\nu \tau$, so the empty probability is $1-\nu \tau$.

The downstream stationary workload is a causal function of past upstream departures. For example, it is the limit of workloads constructed from arrivals in increasingly long finite past intervals; stability makes this stationary construction well defined. The backward independence just proved therefore makes the two present queue populations independent. Consequently

With walking time $\sigma$, the downstream arrival stream is the upstream departure stream shifted by $\sigma$. Its present workload depends only on departures up to time $-\sigma$. The number walking at time zero is the number of departures in $(-\sigma ,0]$, which has Poisson distribution of mean $\nu \sigma$ and is independent of the earlier departures. The upstream present population is independent of both parts of its past departure stream. Thus the three empty events factor, givingThe factor $e^{-\nu \sigma }$ is the empty probability of the deterministic-travel infinite-server stage. Both printed stability inequalities ensure the stationary calculations apply.

For the Erlang loss formula, assume a Poisson process of arrivals with rate $\lambda$, independent holding times with exponential distribution of mean $1/\beta$, unit capacity usage per accepted call, and rejection without waiting when all $C$ units are occupied. Here $C$ is a positive integer and the offered load is $a=\lambda /\beta$. The call population on $\{0,\dots ,C\}$ is a birth-death process; detailed balance givesBy Poisson arrivals see time averages, the fraction of arrivals rejected is the time probability of full occupancy. ThereforeThe paper's $\nu$ is the offered load, rather than necessarily an arrival rate. Exponential holding times suffice for this derivation; no unproved insensitivity of loss networks assumption is needed.

A loss network with fixed routing has capacities $C_j$, call types $r$, and a link-route incidence matrix $A$ with $A_{jr}=1$ exactly when a type-$r$ call requires link $j$. An accepted call holds one unit on every link of its route for its holding time; if any required link is full, the call is rejected everywhere. Take independent Poisson processes of calls, independent holding times, and route offered loads ${\nu }_r$. For the finite-variable formulation below, take $C_j\ge 1$; a zero-capacity link and all routes using it may be removed first.

The Erlang fixed point approximation treats blocking at different links as independent and thins the traffic offered to link $j$ by acceptance at the other links. Its reduced offered load isThe equality uses $A_{jr}\in \{0,1\}$: only routes with $A_{jr}=1$ contribute. Treating this reduced stream as Poisson leads to $B_j=E(a_j(B),C_j)$. Independence and Poisson thinning here are the approximation, not exact properties of a general loss network.

To construct the convex potential for the Erlang fixed point, write $e_C(a)=E(a,C)$ and $m_C(a)=a[1-e_C(a)]$, the carried load of an Erlang loss resource, equivalently the mean occupancy in the single-link stationary distribution. Differentiating its finite sums gives, for $a>0$,The variance is positive because the finite occupancy law is nondegenerate for $a>0$. Furthermore $e_C$ maps $[0,\infty )$ increasingly onto $[0,1)$, while $m_C$ increases from zero to $C$. SetIn particular $U(0,C)=0$, $U(\cdot ,C)$ is continuous and strictly increasing, and $U(z,C)\to C$ as $z\to \infty$.

Forthe first sum is convex, and each integrated strictly increasing function is strictly convex. Thus $F$ is a strictly convex function on $y\ge 0$. Since $U$ tends to a positive limit on every coordinate, $F$ is a coercive function there; it has a unique minimizer. Its coordinate derivative isThe Erlang fixed point equation is exactly ${\partial }_{j}F=0$. For an unused link, $a_j=0$ and the optimum is $y_j=0$; for a used link with positive offered load, the derivative at zero is negative and the optimum is positive. Hence every fixed point gives the unique minimizer, and the minimizer gives a fixed point. The Erlang fixed point is unique under these fixed-routing assumptions.

A convergent cyclic substitution for the Erlang fixed point updates one coordinate at a time, repeatedly cycling through all links:Always use the most recently available values of the other coordinates. Start, for example, with $B=0$. In $y$ coordinates this is exact coordinate descent for $F$: with other coordinates fixed, the displayed update is the unique coordinate minimizer.

Here is a convergence proof. All iterates stay in the initial compact sublevel set of the coercive function $F$, and their potential values decrease to a limit. Each single-coordinate update is continuous, since its reduced load is continuous and finite and $E(a,C)<1$. Thus a whole-sweep map $T$ is continuous. If a full-sweep subsequence converges to $z$, continuity gives $F(Tz)=F(z)$, because both consecutive potential values converge to the same limit. Strict coordinate convexity means equality can occur only when no coordinate changes during that sweep. Thus $z$ minimizes every coordinate, satisfies the nonnegative-orthant first-order conditions, and is the unique global minimizer of $F$. Every subsequential limit is therefore the same point, proving convergence of the full-sweep iterates and, by continuity of the updates, all intermediate iterates. This argument applies to sequential substitution; it does not assume simultaneous updates converge.

A feasible per-flow allocation satisfies $x_r>0$ for each active route and ${\sum }_r{A}_{jr}{n}_r{x}_r\le C_j$. It has proportional fairness if every feasible competitor obeysBy the first-order inequality for the strictly concave logarithm, this is equivalent to maximizing weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$ over the feasible allocations. Inactive-route rates are immaterial; set them to zero as a convention.

Write $a=n_{\{1\}}$, $b=n_{\{2\}}$, $c=n_{\{1,2\}}$, and $N=a+b+c$. The capacity constraints are $a{x}_1+c{x}_0\le 1$ and $b{x}_2+c{x}_0\le 1$. For $c>0$, put $q=c{x}_0$. Each active local route uses its remaining capacity $1-q$. Omitting constants, the utility isIts maximum has $q=c/N$; when $a+b=0$, the maximum is the endpoint $q=1$. Hence for active routesThese formulas also give $x_1=1/a$ and $x_2=1/b$ when $c=0$. When $N=0$ there is no allocated service. Equivalently, the aggregate route rates for $N>0$ areThis is the proportionally fair allocation on a two-resource linear network for a two-resource linear flow network.

For independent Poisson processes of documents and independent document sizes with exponential distribution of rate ${\mu }_r$, the memorylessness of the exponential distribution makes the population a continuous-time Markov chain. Its transition intensities areThe departure intensity sums the $n_r$ independent completion hazards ${\mu }_r{x}_r$. There is no departure on an inactive route. Set ${\rho }_r={\nu }_r/{\mu }_r$, with ${\mu }_r>0$.

To prove the proposed stationary distribution, define the balance function of a flow-level networkFor an active local route, $\Psi (n-e_r)/\Psi (n)=(a+b)/N$, while for the through route this ratio is $c/N$. Thus ${\Lambda }_r(n)=\Psi (n-e_r)/\Psi (n)$. The weightssatisfy detailed balance on every arrival-departure pair:Each total jump rate is bounded by ${\sum }_r({\nu }_r+{\mu }_r)$, so the chain is a nonexplosive Markov chain; normalized detailed-balance weights therefore give its stationary distribution, the stationary law of a two-resource linear flow network.

Use the negative binomial series to sum first over $c$:The remaining two geometric series giveAll summands are nonnegative. Consequently the sum is finite exactly under the stability conditions for a two-resource linear flow networkThese say that the offered load on each unit-capacity resource is strictly below one. Equality is insufficient: at least one geometric series then diverges. If all arrival rates are positive, the chain is irreducible and the normalizable law is its unique equilibrium law.

Finally put $q_i={\rho }_i/(1-{\rho }_0)$, $i=1,2$. Summing over $c$ yieldsThus the two local-route counts are independent, each with geometric distribution on the nonnegative integers. The conditional through-route count has negative binomial distributionFor positive traffic rates this depends on the local counts, so all three route counts are not independent. More quantitatively, $\mathrm{Cov}(a,c)={\rho }_0\mathrm{Var}(a)/(1-{\rho }_0)>0$, and likewise for $b$. If zero arrival rates are allowed, the exceptional independent cases are ${\rho }_0=0$, or ${\rho }_1={\rho }_2=0$, when the relevant counts are deterministic zero. This distinction is local-count independence with through-flow dependence.

The terms in the Boltzmann equation respectively describe dilution by expansion, pair annihilation, and pair production from the thermal bath. The annihilation rate per volume is $⟨\sigma v⟩n\bar{n}$; $P(t)$ is the corresponding production rate. Antiparticles satisfy the same equation with $n$ replaced by $\bar{n}$. Subtracting givesInitial particle-antiparticle symmetry therefore persists. Detailed balance in the thermal bath gives $P=⟨\sigma v⟩n_{\mathrm{eq}}^2$, soDuring radiation domination, with fixed effective relativistic degrees of freedom, $T\propto a^{-1}$ and $H=H_m/x^2$. Thus $\dot{x}=Hx$ and the dilution terms cancel in $Y=n/T^3$:After cosmological particle freeze-out, neglect $Y_{\mathrm{eq}}$. For constant $\lambda$ the exact reduced solution isFor the post-freeze-out relic abundance, the familiar answer $Y_{\infty }\simeq x_f/\lambda$ additionally neglects $1/Y_f$ compared with $\lambda /x_f$. It is an approximation, not an exact consequence of the post-freeze-out equation without initial data. A smaller annihilation cross-section means smaller $\lambda$, earlier decoupling and less depletion, so weakly interacting particles normally have a larger relic abundance.

If there are $i$ balls in box A, a ball currently in B is selected with probability $(k-i)/k$, increasing the count, and a ball in A is selected with probability $i/k$, decreasing it. For $k\ge 1$,with every other transition zero. This is the Ehrenfest urn model.

The stationary distribution isIt is normalized by the binomial theorem, and it obeys the detailed balance:All other pairs have zero flux in both directions. These identities prove stationarity and show that this is a reversible Markov chain in equilibrium. The finite chain is irreducible and has period two; reversibility does not require aperiodicity.

Let $\tilde{\pi }$ be a nonnegative target kernel and $q(y\mid x)$ a proposal distribution. At state $x$, propose $Y\sim q(\cdot \mid x)$, draw an independent uniform $U$, and move to $Y$ ifOtherwise keep $x$. This is the Metropolis–Hastings algorithm. Start on the positive target support, with the usual zero-ratio conventions. The unknown normalizing constant cancels.

An unnormalized kernel is sufficient, provided $0<\int \tilde{\pi }<\infty$. A genuinely improper target with infinite integral is not a probability density and cannot supply a stationary target probability distribution. The acceptance formula can still be written formally, but cannot be said to generate samples from that nonexistent probability law.

Because rejected proposals leave the state unchanged, the Markov kernel includes an atom:Detailed balance with a probability measure $\pi$ means the measure identityWhere both sides have ordinary densities, this reads $\pi (x)K(x,y)=\pi (y)K(y,x)$. The measure formulation also includes the rejection atom. Integrating it shows that $\pi$ is invariant.

For the off-diagonal moves, the Metropolis–Hastings acceptance probability givesThis expression is unchanged by interchanging $x$ and $y$. The rejected-move measure $\pi (dx)r(x){\delta }_x(dy)$ is supported on the diagonal and is also symmetric. Therefore the whole transition measure satisfieswhich proves detailed balance, including the atom that an off-diagonal density alone would omit. Consequently the Metropolis–Hastings algorithm kernel preserves the normalized target measure.

An open migration process is a continuous-time Markov chain recording the populations $n=(n_1,\dots ,n_J)$ of finitely many colonies. Independent external Poisson processes bring individuals to colony $j$ at rate ${\nu }_j$. When that colony contains $k>0$ individuals, a departure opportunity occurs at total rate ${\varphi }_j(k)>0$, with ${\varphi }_j(0)=0$. The departing individual moves to colony $l$ with probability $p_{jl}$, or leaves the system with probability $p_{j0}=1-{\sum }_l{p}_{jl}$. Routing choices and the clocks are independent. A return to the same colony does not change the state.

The word open means that the routing matrix $P=(p_{jl})$ is transient: every individual eventually leaves, or equivalently the spectral radius of $P$ is less than one. The traffic equations of an open migration process, with row-vector convention, give the total arrival rates:These rates include migrations as well as external arrivals. On the active colonies assume ${\alpha }_j>0$ and the usual irreducible Markov chain condition. PutThe product form and its normalization condition areTo establish the product-form stationary distribution of an open migration process, first use its unnormalized weight $b(n)={\prod }_j{b}_j(n_j)$. Its ratios satisfy $b_j(k){\varphi }_j(k)={\alpha }_j{b}_j(k-1)$. The incoming external arrivals into $n$, divided by $b(n)$, contribute ${\sum }_j{\nu }_j{\varphi }_j(n_j)/{\alpha }_j$. Incoming exits contribute ${\sum }_i{\alpha }_i{p}_{i0}$. Incoming migrations from $i$ to $j\ne i$ contribute ${\alpha }_i{p}_{ij}{\varphi }_j(n_j)/{\alpha }_j$. Terms involving an empty destination are zero. Thus the full incoming rate divided by $b(n)$ isHere the traffic equations of an open migration process give the second equality, including ${\sum }_i{\alpha }_i{p}_{i0}={\sum }_j{\nu }_j$. The right side is precisely the total outgoing rate. This proves global balance for a continuous-time Markov chain; pairwise detailed balance is not required for general routing.

For finite rates at each finite population, the continuous-time Markov chain is nonexplosive Markov chain: its total population is bounded over a finite time interval by the initial population plus the finitely many external arrivals, so it visits a finite set on which all jump rates are bounded. Consequently finite $Z_j$ normalize the invariant weight to a stationary distribution. Under the stated irreducible Markov chain assumptions, this is the unique stationary distribution, and it is a positive recurrent Markov chain. Conversely, the unique invariant measure of an irreducible recurrent chain is proportional to $b$, so a positive recurrent Markov chain requires its normalization to be finite. A sufficient condition is ${\mathrm{liminf}}_{k\to \infty }{\varphi }_j(k)>{\alpha }_j$; the series criterion itself is the exact condition. Colonies with ${\alpha }_j=0$ have zero stationary population and can be removed from the active class.

For the single-server M-M-1 queue specialization, ${\varphi }_j(k)={\varphi }_j$ for $k>0$, each stationary colony has the geometric distribution of an M-M-1 queue:The traffic equations of an open migration process do not involve the service rates, so the ${\alpha }_j$ remain fixed during this service-capacity allocation in an open migration process. Write $A={\sum }_j{\alpha }_j$, $B=F-A$ and $b_j={\varphi }_j-{\alpha }_j$. A stationary allocation requires $B>0$, with $b_j>0$ and ${\sum }_j{b}_j=B$. The Cauchy-Schwarz inequality givesEquality holds exactly when $b_j$ is proportional to $\sqrt{{\alpha }_j}$. Hence, for positive arrival rates, the unique optimal service allocation and the minimum expected value of the total population areIf $F\le A$ and some arrival rate is positive, no stable service allocation exists. Zero-arrival colonies need no service in their stationary empty class: allowing zero service there gives the same formula restricted to active colonies. If strictly positive service is demanded even at inactive colonies, the displayed minimum is an infimum approached as that unused allocation tends to zero. If all arrivals vanish, the stationary mean population is zero for every allocation that drains the initial population.

A reversible Markov chain has a stationary law $\pi$ for which every finite path has the same distribution as its time-reversed path:For a transition matrix $P$, the equivalent detailed balance condition is ${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$ for all $i,j$. It implies $\pi P=\pi$ by summing over $i$. Multiplying the balance identities along a path shows equality of its forward and reverse probabilities when $X_0\sim \pi$; conversely, taking paths of length one gives those identities.

For the usual undirected graph with at least two vertices, a simple random walk chooses a neighbor uniformly at each step, so $P_{ij}=1/d_i$ when $i$ and $j$ are adjacent and zero otherwise, where $d_i$ is the degree of a vertex. The handshaking lemma gives ${\sum }_i{d}_i=2|E|$. Thus the stationary distribution of a graph random walk isFor adjacent $i,j$, ${\pi }_i{P}_{ij}=1/(2|E|)={\pi }_j{P}_{ji}$, and for nonadjacent pairs both sides vanish. By detailed balance, this is an invariant distribution and the walk started from it is a reversible Markov chain. Connectedness makes the finite walk an irreducible Markov chain, giving uniqueness of its invariant distribution. No aperiodicity assumption is needed for uniqueness, so a bipartite graph is allowed.

If the connected graph has a single isolated vertex, the usual neighbor-choice formula is undefined. With the natural absorbing convention $P_{11}=1$, its unique invariant distribution is ${\pi }_1=1$ and it is reversible. The degree-normalization formula presupposes at least one edge.

Take the real inner productThe stationary distribution is strictly positive for an irreducible Markov chain. Detailed balance gives $⟨Pf,g{⟩}_{\pi }=⟨f,Pg{⟩}_{\pi }$, so $P$ is a self-adjoint operator. Choose a real orthonormal eigenbasis $f_1,\dots ,f_m$, where $m=|S|$, $P{f}_j={\lambda }_j{f}_j$, $f_1\equiv 1$, ${\lambda }_1=1$, and $\pi (f_j)=0$ for $j\ge 2$.

For fixed $y$, apply the spectral decomposition to $g_y(z)=1_{\{y\}}(z)/\pi (y)$. Its coefficient against $f_j$ is $f_j(y)$, whereas $(P^t{g}_y)(x)=P^t(x,y)/\pi (y)$. Thus the spectral kernel expansion of a reversible chain isThis holds for all integers $t\ge 0$; at $t=0$ each multiplier is one, including when ${\lambda }_j=0$. Negative eigenvalues are allowed, and retain their signs for odd $t$.

For a finite irreducible Markov chain satisfying detailed balance, define the directed-edge capacity $Q(u,v)=\pi (u)P(u,v)$. For every ordered pair $(x,y)$ choose a path ${\eta }_{xy}$ from $x$ to $y$ using only positive-capacity edges; take the empty path for $x=y$. Let $N_e(\eta )$ count occurrences of the directed edge $e$. The canonical paths Poincare bound says thatis a valid Poincare inequality for a reversible Markov chain constant. Simple paths give $N_e\in \{0,1\}$; allowing repetitions requires the multiplicities shown.

To prove the theorem, expand the variance using two independent samples from $\pi$:Telescoping along ${\eta }_{xy}$ and applying the Cauchy-Schwarz inequality givesInterchange the finite sums, then use the definition of $\rho$:Consequently $\boxed{{\mathrm{Var}}_{\pi }(f)\le \rho \mathcal{E}(f,f),\gamma \ge 1/\rho }$. All edges here are directed, so the $1/2$ in the Dirichlet form of a Markov chain is retained consistently.