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.

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 simple random walk on two disjoint complete graphs of size $n\ge 2$ joined through one new vertex $w$, let $h_1$ be the expected hitting time of $w$ from either vertex attached to $w$, and $h_o$ the expected hitting time from any other clique vertex. First-step analysis gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The expected hitting time from $w$ is zero. In discrete time the random walk is an aperiodic Markov chain only for $n\ge 3$.

Apply the Monte Carlo estimator to the observable $h(s)=\exp ({\sum }_{i\in D}\sqrt{2+s_i})$:The theoretical justification is the ergodic theorem for a positive Harris recurrent Markov chain, not an independent-sample law of large numbers. The Markov chain has finite state space, is irreducible, and has the strictly positive posterior distribution as invariant law, so it is positive recurrent and Harris recurrent with counting measure. The observable is bounded: $e^{K^2}\le h(s)\le e^{\sqrt{3}{K}^2}$. Thus the estimator converges almost surely to the posterior expected value from any initial configuration.

Each state also has positive self-transition probability, so the chain is an aperiodic Markov chain. Finiteness then gives geometric convergence and the relevant central limit theorem; serial dependence determines the Markov chain Monte Carlo asymptotic variance if error bars are required. A fixed finite burn-in can be discarded without changing consistency, but independence of the retained states should not be assumed.

The only closed communicating class is $\{b,d\}$; the class $\{a,c\}$ is open and transient. Its one-step probability of staying inside is at most $2/3$, so if $\tau$ is the entrance time into $\{b,d\}$, then $\mathbb{P}(\tau >n)\le (2/3{)}^n$ for an initial state in $\{a,c\}$. Hence entrance occurs almost surely in finite time.

On $\{b,d\}$ it is an irreducible aperiodic Markov chain, because both states have positive self-loop probabilities. The finite irreducible aperiodic countable-state Markov chain convergence theorem says that its transition probabilities converge to its unique stationary distribution. The balance equation ${\pi }_b(3/4)={\pi }_d(2/3)$ with ${\pi }_b+{\pi }_d=1$ gives ${\pi }_b=8/17$ and ${\pi }_d=9/17$.

This limit also holds from $a,c$: condition on the finite entrance time and entrance state. For $\tau \le M$, convergence in the closed class applies to a finite sum; the remaining probability is bounded by $\mathbb{P}(\tau >M)$, which tends to zero as $M\to \infty$. Thus in the order $a,b,c,d$,

Every reachable state $i$ reaches zero deterministically in $i$ steps. For $j\in E$, choose a supported lifetime $k>j$; zero can jump to $k-1$ and then count down to $j$. Thus the chain is an irreducible Markov chain on $E$. Its positive-probability first return lengths are exactly the support of $Y_1$; all other return lengths are sums of such lengths. Their greatest common divisor is therefore one by assumption, so the chain is an aperiodic Markov chain.

The equilibrium residual-life distribution isIt is a probability distribution because the tail-sum identity gives ${\sum }_{j\ge 0}\mathbb{P}(Y_1>j)=\mathbb{E}{Y}_1=\mu$. With zero masses outside $E$,so it is a stationary distribution. This also displays why finite mean is needed for normalization.

Use the countable-state Markov chain convergence theorem: an irreducible, aperiodic, positive recurrent discrete-time chain on a countable state space has a unique stationary distribution and $P^n(i,j)\to {\pi }_j$ for every pair of states. All hypotheses were verified, including positive recurrence in part (b). Since $X_0=0$ and $\mathbb{P}(Y_1>0)=1$,The finite-state convergence theorem alone would not suffice when the lifetimes are unbounded. The gcd hypothesis is also necessary for this ordinary limit: deterministic lifetime 2, for example, produces alternating renewal probabilities rather than convergence.

For probability distributions on a finite set, the total variation distance isThe equality follows by taking $A=\{z:\mu (z)\ge \nu (z)\}$: the positive and negative parts of $\mu -\nu$ have the same mass, since its total mass is zero.

Use the stationary distribution identity $\pi P^t=\pi$. For each initial state $x$,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over $x$ proves $\boxed{d(t)\le \bar{d}(t)}$. This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.

Let $R$ interchange the two complete graphs, sending $v_i$ to $v_i^{\prime }$ and fixing $w$. This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts $X$ at $v_i$, keeps $Y_t=R(X_t)$ until the hitting time $\tau$ of $w$, and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at $\tau$. The coupling inequality for total variation gives

There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For $n\ge 2$, write $a={\mathbb{E}}_{v_1}\tau$ and $b={\mathbb{E}}_{v_i}\tau$ for $i\ne 1$. From every clique vertex there is a positive chance of reaching $w$ within two steps, uniformly over the finite state space for each fixed $n$, so $\tau$ has finite expected value. First-step analysis, using the degree of a vertex $n$ at $v_1$ and $n-1$ at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is ${\max }_x{\mathbb{E}}_x\tau \le n^2$, the hitting time of the bridge vertex between two cliques formula.

We must also handle arbitrary starting states, including $w$, before applying the mirror argument. Identify related vertices and consider the lumped Markov chain $Z$ on $\{1,\dots ,n,w\}$. Its transition matrix $Q$ has $Q(1,j)=1/n$ for $j\ne 1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne 1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne 1$ only ranges over $j\in \{1,\dots ,n\}$.

For $n\ge 3$ and $j\in \{2,\dots ,n\}$, direct two-step calculation givesAll these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot )\ge \alpha \nu (\cdot )$ for every $z$, where $\nu$ is the uniform distribution on a finite set $\{2,\dots ,n\}$ and $\alpha =(n-1)/(2n)\ge 1/3$. This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from $\nu$ with probability $\alpha$, using the residual probability distributions otherwise. The first successful block has expected value at most $1/\alpha$, so the alignment time $A$ has $\mathbb{E}A\le 6$. Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.

At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time $T$ satisfying $\mathbb{E}T\le 6+n^2$ for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least $1-2/n$: for two ordinary indices it is $(n-2)/(n-1)$; for one attachment index it is $(n-2)/n$. A maximal coupling therefore aligns those indices with probability $1-O(1/n)$, as suggested. The two-step argument above additionally covers $w$.

The nonlazy walk is an aperiodic Markov chain for $n\ge 3$, because the connected graph contains a triangle. For $n=1,2$ it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass $1/2$, and the walk stays on a single class at each time. Hence $d(t)\ge 1/2$ and the $1/4$ mixing time is infinite. The asymptotic conclusion is valid for $n\ge 3$.

For a finite irreducible Markov chain that is an aperiodic Markov chain, setHere ${\pi }_n$ is its unique stationary distribution, and the distance is total variation distance. Applying a Markov kernel contracts total variation distance, so $d_n(t)$ is nonincreasing and the minimum is finite.

Use the ratio definition of cutoff: a family has cutoff for Markov chains if, for every fixed $0<\epsilon <1/2$,with the denominator positive eventually. Thus the transition between any two fixed distance levels takes negligible time compared with the mixing time scale. By monotonicity and squeezing, this also gives $t_{\mathrm{mix}}^{(n)}(\alpha )/t_{\mathrm{mix}}^{(n)}(\beta )\to 1$ for any fixed $\alpha ,\beta \in (0,1)$.

Some definitions of cutoff for Markov chains additionally require the mixing time to diverge. That extra requirement cannot be built into the definition here: the final request in part (d) explicitly asks for a bounded-time counterexample. The ratio convention is the one consistent with that request.

Let $m\ge 2$ be the number of states and putThe absolute L2 spectral gap of a reversible Markov chain is ${\gamma }_{\ast }$; in this question the relaxation time means the absolute relaxation time. For a nonlazy reversible Markov chain, it may differ from the reciprocal of the ordinary spectral gap $1-{\lambda }_2$. For a finite irreducible Markov chain that is an aperiodic Markov chain, $r<1$.

For $r>0$, choose a real eigenfunction $f$ whose eigenvalue has modulus $r$, and an initial state $x$ maximizing $|f(x)|=\Vert f{\Vert }_{\infty }$. It has $\pi (f)=0$, and the definition of total variation distance impliesThis is the eigenvalue lower bound for total variation mixing, $d(t)\ge r^t/2$. At $t=t_{\mathrm{mix}}(\epsilon )$, for $0<\epsilon <1/2$,The second inequality follows from $-r\log r\le 1-r$, the supplied inequality with $x=1-r$. Since $r/(1-r)=t_{\mathrm{rel}}-1$,When $r=0$ the left side is zero, so no logarithm of zero is needed. For $\epsilon \ge 1/2$ the left side is nonpositive and the conclusion is automatic. A one-state chain has mixing time zero; with the convention ${\gamma }_{\ast }=1$ the bound is again trivial.

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.

Take observation periods to have positive lengths $t_i>0$, and let $P$ be the Markov kernel of a sweep which first draws $b$ given the current $\theta$ and then draws the new vector ${\Theta }^{\prime }$. Write $A_i=a+y_i$. Conditional on $b$, independence and the gamma distribution mean and variance giveAveraging over the full conditional distribution of $b$ preserves this bound, uniformly in the current state. Therefore $PV(\theta )\le M:=1+D<\infty$. This is the mechanism in bounded conditional moments imply a geometric drift.

Choose $0<\rho <1$, $R>M/\rho$, and $C=\{\theta :V(\theta )\le R\}$. Outside $C$, $PV\le M<\rho V$; inside $C$, $PV\le M\le \rho V+M$. HenceFor completeness, $C$ is a small set, even though it approaches the boundary of the positive orthant. Choose $\delta >0$ small enough that $B=[\delta ,2\delta {]}^n\subset C$. On $C$, $s={\sum }_i{\theta }_i\le \sqrt{R-1}$. The conditional gamma distribution of $b$ has fixed shape $na+c$ and rate $1+s$ in a compact positive interval. Its probability density function therefore has a positive common lower bound on $b\in [1,2]$. For those $b$, the product probability density function of ${\Theta }^{\prime }$ similarly has a positive common lower bound on $B$, since every shape is positive and every rate $b+t_i$ lies in a compact positive interval. Integrating over $b\in [1,2]$ gives $P(\theta ,\cdot )\ge \epsilon \eta (\cdot )$ on $C$, where $\eta$ is the uniform distribution on $B$ and $\epsilon >0$.

The transition probability density function is positive throughout the positive orthant, giving an irreducible Markov chain. Since $B\subset C$, the box minorization includes starts in the same box, which gives an aperiodic Markov chain. The proper prior distributions and bounded Poisson distribution likelihood have positive finite evidence, so the invariant posterior distribution is proper. Together with the geometric drift condition, these hypotheses imply geometric ergodicity. In particular, the argument proves the required drift rather than assuming that every Gibbs sampler is geometrically ergodic.

The positive-period convention matters. If zero lengths are allowed, the printed assertion can fail: take $n=1$, $a=c=1$, $t_1=y_1=0$. Then $b\mid \theta \sim \mathrm{Gamma}(2,1+\theta )$ and ${\Theta }^{\prime }\mid b\sim \mathrm{Gamma}(1,b)$, soThis example has a proper posterior distribution but cannot satisfy a finite quadratic geometric drift condition. Thus the proof establishes the intended claim for positive observation periods, not an unrestricted extension to zero exposure.

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.

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.

The self-loop at zero makes the irreducible chain aperiodic. The convergence theorem for irreducible, aperiodic, positive recurrent countable-state chains givesBecause $X$ and $Y$ are independent,Therefore

True. For a state $i$, letbe its possible return times under $P$, and define ${\mathcal{R}}_Q(i)$ similarly. Every positive $P$-path is a positive $Q$-path, soThe greatest common divisor of the larger set divides that of the smaller set. Since the latter is one by the assumed aperiodic Markov chain property, the former is also one. Hence every state is aperiodic under $Q$.

A Markov kernel $K$ with stationary distribution $\pi$ is geometrically ergodic if there are $\rho <1$ and a finite function $M(x)$ such thatfor every $m\ge 0$ and almost every starting point $x$, where $\Vert \cdot {\Vert }_{\mathrm{TV}}$ is total variation distance.

A measurable set $A$ is a small set with minorisation constant $\alpha >0$ if some integer $r\ge 1$ and some probability measure $\nu$ satisfyfor every $x\in A$ and every measurable $B$.

A standard drift-minorisation condition is that the chain be irreducible and aperiodic, and that there exist a measurable $V\ge 1$, a small set $A$, constants $\lambda <1$ and $b<\infty$ such thatThese conditions imply geometric ergodicity.