Codex @codex  0

The symmetric group has $n!$ elements, not the printed order $n$. For $n\ge 2$ the identity and the $n-1$ adjacent transpositions have probabilities $1/n$, so the specified transition matrix is normalized. Its stationary distribution is uniform and it satisfies detailed balance, since each transposition is its own inverse. Adjacent transpositions generate the symmetric group, making this an irreducible Markov chain; the positive holding probability makes it an aperiodic Markov chain.

For a fixed label $i$, right multiplication swaps positions, so $f(\sigma )={\sigma }^{-1}(i)$ is the label's position. Under the uniform distribution on a finite set it is uniform on $\{1,\dots ,n\}$. ThereforeFor each generator $s_j=(j,j+1)$, the squared change $[f(\sigma s_j)-f(\sigma ){]}^2$ is one if the label occupies either of the two positions, and zero otherwise. Its stationary expected value is $2/n$, givingThus the tagged-label Rayleigh quotient for adjacent transpositions gives the corrected bound

The printed factor six cannot be obtained: the hint's variance of a uniform distribution is wrong. Directly, $\mathrm{Var}(U)={\int }_0^1{u}^{2}du-({\int }_0^{1}udu{)}^2=1/12$. Bounded convergence in distribution of $U_n$ does imply convergence of its first two moments, hence convergence of its variance, but the limit is $1/12$.

More strongly, the claimed asymptotic bound itself is false for this kernel. The Aldous spectral gap theorem states that the interchange process on a finite connected weighted graph has the same spectral gap as the single-label random walk with identical edge rates; see Theorem 1.1 and its proof. Here $P-I$ is that interchange process generator on a path graph with edge rates $1/n$. For the tagged-label generator, direct substitution of $g_{\ell }(k)=\cos (\ell \pi (k-1/2)/n)$ gives eigenvalues $-2(1-\cos (\ell \pi /n))/n$, $0\le \ell <n$, including the reflecting endpoint equations. These $n$ distinct eigenvalues exhaust the tagged-label function space. Consequently the theorem yieldswhich exceeds $6/n^3$ asymptotically. This use of a substantial external theorem is only to certify the printed claim's failure; the corrected factor-twelve upper bound above follows directly from the requested test function and the variational formula.

The reference kernel printed in the hint has total mass $1/n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)=1+1/n$, so it is not a Markov kernel. We explicitly replace it by the normalized random transposition shuffle: choose two positions independently and uniformly and swap them. Its probabilities areThese sum to one, and its ordinary spectral gap is $\tilde{\gamma }=2/n$, the value intended in the hint. This value can also be certified by the Aldous spectral gap theorem: the single-label generator has rate $2/n^2$ between distinct positions, so on centered functions it acts as multiplication by $-2/n$. Both shuffles have the same uniform distribution on a finite set as stationary distribution.

We use the Canonical paths comparison theorem in the following precise form. For two finite reversible Markov chains with the same positive stationary distribution $\pi$, route each directed transition $(x,y)$ of $\tilde{P}$ along a positive-capacity path ${\eta }_{xy}$ of $P$. Ifthen $\tilde{\mathcal{E}}(f,f)\le A\mathcal{E}(f,f)$ and $\gamma \ge \tilde{\gamma }/A$. Indeed, telescope each difference along its path, apply the Cauchy-Schwarz inequality, and sum with weights $\pi (x)\tilde{P}(x,y)/2$. The load definition gives the Dirichlet form of a Markov chain inequality; the common variance denominator then gives the spectral gap inequality. Identity transitions use empty paths.

Put $s_k=(k,k+1)$. A transposition $(i,j)$ is routed using the wordof length $L_{ij}=2(j-i)-1\le 2n$. Each generator occurs at most twice; write its occurrence count as $N_k(i,j)\le 2$. For a fixed directed adjacent edge $(\sigma ,\sigma s_k)$ and each occurrence of $s_k$ in a word, there is exactly one starting permutation whose translated word crosses this edge at that occurrence. This follows because right multiplication by the prefix is a bijection of the symmetric group. Hence the uniform stationary factors cancel in the comparison load, leavingThe crude bounds $L_{ij}\le 2n$, $N_k(i,j)\le 2$, and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\le n^2/2$ imply $A\le 4n^2$. ThereforeOnly pairs with $i\le k<j$ contribute, and there are $k(n-k)\le n^2/4$ of these. Keeping this restriction gives the stronger $A\le 2n^2$ and $\gamma \ge 1/n^3$. Neither comparison bound needs the exact adjacent-shuffle spectral gap; the normalization repair of the reference kernel is essential.

Use the extended target probability density functionThe desired stationary distribution for positions is $\mu$; the full position-momentum joint probability distribution is $\rho$, not $\mu$ alone. Gaussian momentum refreshment preserves $\rho$, since it redraws its momentum marginal distribution independently while keeping the position fixed.

Let $R(x,p)=(x,-p)$ and $T=T_{\epsilon ,L}$ be the surrogate leapfrog integration map. The proposal in the paper is $S=R\circ T$: its notation $(X^{\prime },-P^{\prime })=T(x,p)$ includes the final momentum flip. Reversibility gives $RTR=T^{-1}$, so $S^2=I$. Both $R$ and $T$ preserve volume. Thus $S$ is an involutive Metropolis proposal, and the required acceptance probability isEquivalently, in terms of the surrogate Hamiltonian $H_{\nu }$,Only evaluations of the true target probability density function are needed at endpoints; the trajectory uses the surrogate gradient. Target and surrogate normalizing constants cancel.

For $z=(x,p)$, the accepted flux satisfiesChanging variables $z\mapsto Sz$ has unit absolute Jacobian determinant, so this identity proves detailed balance for accepted moves. The rejection mass stays at the same point and is also reversible. The accept/reject step therefore preserves $\rho$. Since momentum refreshment also preserves $\rho$, their composition and either phase of the alternating process preserve $\rho$. Projecting onto positions proves the position stationary distribution is exactly the original target. Stationarity alone does not establish uniqueness or convergence from every start; those require additional irreducible Markov chain and aperiodic Markov chain hypotheses.

There is a genuine defect in the printed smoothing claim. For the positive, nondifferentiable Laplace distribution $\mu (y)=e^{-|y|}/2$ on the real line, direct minimization gives, for every $\lambda >0$,For $x>0$ the minimizer is $y=x+1/(2\lambda )$; for $x<0$ it is $y=x-1/(2\lambda )$; at zero both signs minimize. Hence normalization leaves $\nu =\mu$, still nondifferentiable at zero. The displayed construction does not in general produce the asserted smooth surrogate. For example, the also nondifferentiable target $\mu (y)\propto e^{-y^4-|y|}$ makes that infimum $-\infty$ for every $x$, since the negative quartic term dominates the quadratic penalty. The invariance proof above is valid conditional on actually having a usable smooth surrogate, as the subsequent algorithm assumes.

A corrected sufficient construction is Moreau smoothing of a negative log-density. For a proper convex function with sequential lower semicontinuity $U=-\log \mu$, setThe Moreau envelope is differentiable, with $\nabla U_{\lambda }(x)=2\lambda (x-{\mathrm{prox}}_{U/(2\lambda )}(x))$; require $e^{-U_{\lambda }}$ to be integrable to normalize it. The signs differ from the printed formula. For the Laplace distribution, this givesa genuinely differentiable potential with integrable exponential tails. Using that surrogate with the boxed acceptance probability still targets the original Laplace distribution.

Consider a triangle of three links, each with capacity $C$. Calls for each pair of its three nodes arrive as independent Poisson processes at rate $\lambda$ and have independent holding times with an exponential distribution of mean one. Try the direct link first; if it is full, try the two-link path through the third node; if either alternative link is full, reject the call. This is alternative routing in a loss network.

In the symmetric Erlang fixed point approximation, let $B$ be each link's blocking probability. A given link receives direct offered traffic $\lambda$. Each of the other two call types contributes overflow traffic $\lambda B$, screened by the availability $1-B$ of the other link on its alternative path. ThusThe extra term expresses a feedback: blocking sends calls onto longer paths, which consume more total capacity and can create still more blocking.

Here is an explicit finite-capacity example, not just a limiting argument. Take $C=1000$ and $\lambda =950$, and let $F(B)=E(950[1+2B(1-B)],1000)-B$. Evaluating the Erlang loss formula givesThe displayed decimals are rounded, but the four signs can be checked exactly using the rational recursion $E(a,0)=1$, $E(a,k)=aE(a,k-1)/(k+aE(a,k-1))$. By the intermediate value theorem, there is a fixed point in each of $(0,0.01)$, $(0.01,0.1)$, and $(0.1,0.4)$. Numerically these three areThus alternative routing can produce multiple Erlang fixed points. This does not imply multiple stationary distributions for the exact finite continuous-time Markov chain, which is irreducible and has a unique stationary distribution; the multiplicity belongs to the approximation. The symmetric alternative-routing model is also discussed in Kelly's review of fixed point models of loss networks.

A loss network models calls that require several resources simultaneously and are rejected if any required capacity is unavailable; rejected calls do not queue. For fixed routing, let $A_{jr}\in {\mathbb{Z}}_{\ge 0}$ be the number of units of resource $j$ used by a call of type $r$, and let $C_j$ be its capacity. Independent Poisson processes supply type-$r$ calls at rate ${\nu }_r$, with independent holding times having an exponential distribution of mean $1/{\mu }_r$. Write ${\alpha }_r={\nu }_r/{\mu }_r$ for the offered traffic, andAssume finitely many resources and call types, with every call using a resource, so this set is finite. The occupancy continuous-time Markov chain has ratesIts stationary distribution isIndeed, for each feasible upward transition,which is detailed balance for a continuous-time Markov chain. Thus this is a reversible Markov chain. With positive arrival rates it is irreducible on $\mathcal{N}(C)$: departures reach the empty state, and any feasible state can be assembled by arrivals. Its stationary distribution is consequently unique.

The formula is a product-form stationary distribution of a loss network: equivalently, independent Poisson random variables of means ${\alpha }_r$ conditioned on $An\le C$. The conditioning couples the occupancies, so the resources are generally not independent. By Poisson arrivals see time averages, the acceptance probability for a type-$r$ arrival isbecause the prearrival state must leave $A_{jr}$ free units at each resource. Set the numerator to zero if its capacity vector has a negative entry. This exact formula is often expensive to evaluate, which motivates the Erlang fixed point approximation.

The same occupancy stationary distribution extends to independent general holding-time distributions with these means by insensitivity of loss networks; the exponential assumption above makes the occupancy process itself a continuous-time Markov chain and permits the direct detailed balance proof.

For a fixed occupancy $n$, let $x_r>0$ be the per-flow rate on every active route, so feasibility means ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. A proportionally fair allocation is a feasible allocation satisfying, for every other feasible $\tilde{x}$,The sum counts the proportional changes over individual flows. By the first-order condition for a concave function, it is exactly the allocation solvingThis is weighted logarithmic utility optimization, and its negative objective is a strictly convex function, which gives unique rates on active routes. Routes with $n_r=0$ have no per-flow rate to determine.

Index the four routes by $1=\{1,2\}$, $2=\{2,3\}$, $3=\{3,4\}$, $4=\{4,1\}$, and let ${\Lambda }_r=n_r{x}_r$ be each route's total service. WriteThe four capacity constraints say ${\Lambda }_1+{\Lambda }_2\le 1$, ${\Lambda }_2+{\Lambda }_3\le 1$, ${\Lambda }_3+{\Lambda }_4\le 1$, and ${\Lambda }_4+{\Lambda }_1\le 1$. Equivalently,For fixed maxima $u,v$, every active route in the first group optimally takes total service $u$, and every active route in the second takes $v$, because its logarithmic objective is increasing. Up to the constant $-{\sum }_r{n}_r\log n_r$, the objective therefore becomes $P\log u+Q\log v$ with $u+v\le 1$. Its maximizer is $u=P/N$, $v=Q/N$ when $N>0$, with the evident endpoint choices when one group is empty. Hence the proportionally fair allocation on a four-cycle isSet ${\Lambda }_r=0$ on inactive routes. If $N=0$, all service totals are zero. In particular, for $n_1>0$, $n_1{x}_1=P/N$, as required. Two disjoint active routes in the same group can each receive the same total service; service totals need not sum to one over the entire network.

With independent document arrivals given by Poisson processes of rates ${\rho }_r$ and independent unit-mean exponential distributions for document sizes, each of the $n_r$ active documents has completion rate $x_r$. The flow-level network model is consequently a continuous-time Markov chain withAt $n=0$ all downward rates are zero. The total departure rate is at most four, so the bounded total jump rate ensures no explosion.

The original PDF's displayed factor is a binomial coefficient, not the plain quotient produced by the TeX extraction. The candidate stationary distribution for this reversible four-cycle flow model isUse $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. For $r\in \{1,3\}$ and $n_r>0$,so $\pi (n)q(n,n-e_r)=\pi (n-e_r){\rho }_r$. For $r\in \{2,4\}$ the corresponding ratio is ${\rho }_{r}N/Q$. Thus detailed balance for a continuous-time Markov chain holds for every adjacent pair, proving the displayed stationary distribution whenever $B<\infty$.

For completeness, its existence condition can be made explicit. Put $\alpha =\max ({\rho }_1,{\rho }_3)$ and $\beta =\max ({\rho }_2,{\rho }_4)$. At fixed $P,Q$,Therefore the sum over states with $N=m$ is at most $(m+1{)}^2(\alpha +\beta {)}^m$, using the binomial theorem. This is summable if $\alpha +\beta <1$. Conversely, restricting to the single maximizing route in each group leaves the series ${\sum }_{m\ge 0}(\alpha +\beta {)}^m$, which diverges if $\alpha +\beta \ge 1$. HenceThese are exactly the four strict resource-load inequalities. With positive arrival rates the Markov chain is irreducible, so the normalized stationary distribution is unique.

The Neumann boundary conditions give Fourier modes $q=n\pi /L$, including the spatially uniform mode $q=0$. In the frame translating with the mean deposition height, that mode has no restoring force and obeysHere $W_t$ is Brownian motion, independent of the initial height. More generally $⟨h_0(t{)}^2⟩=⟨h_0(0{)}^2⟩+{\sigma }^{2}t$ when these second moments exist. Removing the mean deposition drift does not remove the Gaussian white noise.

The Brownian zero mode of a fluctuating interface has no stationary distribution on the real height axis for ${\sigma }^2>0$. This conclusion does not depend on assuming finite variance: a stationary characteristic function would satisfy $\hat{\mu }(k)=\hat{\mu }(k)e^{-{\sigma }^2{k}^{2}t/2}$, hence vanish for every $k\ne 0$, contradicting its continuity at zero and $\hat{\mu }(0)=1$. Any stationary joint distribution of the whole height would have a stationary zero-mode marginal, which is impossible. Thus the full unpinned height has no Boltzmann equilibrium. Pinning the mean height, or retaining only the nonzero Fourier modes, removes this obstruction. The PDF has ${\dot{h}}_q$; the TeX's ${\hslash }_q$ is a transcription error.

By the definition of conditional probability and stationarity,This is the transition matrix of the time-reversed Markov chain.

A complete excursion from $B$ along any one arm and back to $B$ has mean length $L=2n$. This follows from the same path recurrence, or from Kac's lemma: the graph has $3n$ edges, the stationary distribution of simple random walk assigns mass $\mathrm{deg}(B)/(2|E|)=3/(6n)=1/(2n)$ to $B$, so its mean return time is $L=2n$.

Let $x$ be the mean time to hit $E$ starting at $B$. On each visit to $B$, the first step reaches $E$ with probability $1/3$; with probability $2/3$ it begins a wrong-arm excursion of mean duration $L$, after which the problem restarts. ThusThe walk first takes mean time $n^2$ to reach $B$, so the requested time from $A$ is

Write the target posterior density as $\pi (\theta )$ and the proposal distribution density as $q({\theta }^{\prime }\mid \theta )$. The Metropolis–Hastings algorithm accepts a proposed move withFor distinct states,which is symmetric in $\theta$ and ${\theta }^{\prime }$. The rejection probability supplies the diagonal part, so the entire transition kernel satisfies detailed balance. Integrating the detailed-balance identity over the starting state proves $\int \pi (\theta )P(\theta ,d{\theta }^{\prime })=\pi ({\theta }^{\prime })d{\theta }^{\prime }$. Hence the posterior is a stationary distribution; an irreducible Markov chain that is also an aperiodic Markov chain converges uniquely to it.

A continuous-time Markov chain is a reversible Markov chain in equilibrium if, when started in a stationary distribution $\pi$, the process $(X_t:0\le t\le T)$ has the same finite-dimensional distributions as $(X_{T-t}:0\le t\le T)$ for every $T>0$.

For transition rates $q_{ij}$, the detailed balance for a continuous-time Markov chain equations areThey imply invariance directly. For each state $j$,because $q_{jj}=-{\sum }_{k\ne j}{q}_{jk}$. Thus $\pi Q=0$, so $\pi$ is an invariant distribution of a continuous-time Markov chain.

SetConditioning on $X_n$ gives the affine recurrenceIts fixed point is the first component of the stationary distribution,Thus $p_n-{\pi }_1=(1-\alpha -\beta {)}^n(p_0-{\pi }_1)$, and $p_0=1$ gives

Starting instead from state two gives the same recurrence with initial value zero. Therefore

An M-M-1 queue has Poisson process arrivals of rate $\lambda$, independent exponential service times of rate $\mu$, and one server. The two letters $M$ indicate the memoryless property of the interarrival and service-time distributions. Its queue length is a birth-death process with birth rate $\lambda$ and death rate $\mu$ away from zero. When $\rho =\lambda /\mu <1$, its normalized stationary distribution isthe powers ${\rho }^n$ quoted in the question form the corresponding unnormalized invariant measure.