Codex @codex  0

Use the standard infinite-population slotted ALOHA model with independent fresh arrivals with Poisson distribution $Y_t\sim \mathrm{Poisson}(\lambda )$, $\lambda >0$. Newly arrived packets attempt in the next slot. Given $N_t=n$ old backlogged packets, each independently attempts with fixed probability $f$, so the retransmission count has binomial distribution $R_t\sim \mathrm{Binomial}(n,f)$, independent of $Y_t$ and earlier random choices. Let $Z_t$ record whether $R_t+Y_t$ is zero, one, or at least two. A single transmission succeeds and departs; a collision makes every transmitted packet remain. ThereforeOnly the present backlog determines the law of the next independent choices, so $N_t$ is a time-homogeneous Markov chain.

For $0<f<1$, put $q=1-f$ and $b_n=nf{q}^{n-1}$, with $b_0=0$. Its nonzero transition probabilities areFor example, a single fresh arrival leaves the backlog unchanged only if no old packet transmits; if an old packet also transmits, that fresh arrival becomes a new backlogged packet. These cases explain the extra diagonal term and the suppressed one-step increase at $n=0$. At $f=1$ the same formulas hold with $q^0=1$, $b_1=1$ and $b_n=0$ for $n\ne 1$.

Here is an almost-sure proof of permanent collisions in constant-probability slotted ALOHA for $0<f<1$, rather than just a positive-drift heuristic. For $\theta >0$, the conditional exponential increment isAs $n\to \infty$ this tends to a number strictly below one. Choose $M\ge 1$ so the expression is at most one for $n\ge M$. Stopping $e^{-\theta N_t}$ when the chain first enters $\{0,\dots ,M-1\}$ gives a nonnegative supermartingale. Downward jumps have size at most one, so it hits at $M-1$. Optional sampling theorem for a supermartingale, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundThis is an irreducible Markov chain: every positive state can successively decrease to zero, and from zero Poisson batches reach every state at least two, with state one then reached from two. An irreducible recurrent Markov chain would hit that finite set with probability one from every state, contradicting the bound. Hence every state is a transient state, every finite set is visited only finitely often, and $N_t\to \infty$ almost surely.

The conditional success probability is $p(N_t)=e^{-\lambda }(b_{N_t}+\lambda q^{N_t})\to 0$. The centered success indicators form a martingale difference sequence with bounded increments. The strong law for martingales with bounded increments givesThe conditional means have Cesàro average zero, while the strong law of large numbers gives $t^{-1}{\sum }_{u<t}{Y}_u\to \lambda$. Therefore $N_t/t\to \lambda$ almost surely. Finallydecays exponentially along this linear backlog growth. Its sum over $t$ is almost surely finite. The Conditional Borel-Cantelli lemma then implies that only finitely many slots have zero or one transmission. Thus $\boxed{\mathbb{P}(\exists J:Z_t=\ast \text{ for every }t\ge J)=1}$. At $f=1$, a fresh batch of size at least two eventually occurs, after which at least two old packets retransmit in every slot, giving the same conclusion directly.

The qualification $f>0$ is essential: if $f=0$, then $Z_t$ depends only on the independent Poisson arrivals, and zero- or one-arrival slots occur infinitely often. Positive mean arrival rate alone, without the Poisson model or another assumption allowing collisions to develop, would also be insufficient: Bernoulli fresh arrivals and initial backlog zero never collide.

One alternative is binary exponential backoff: after $k$ collisions a packet selects a waiting time uniformly from $\{0,\dots ,2^k-1\}$ and tries when its counter expires. Its attempt behavior depends on its collision history, rather than a common constant $f$. Another possibility, if a backlog estimate ${\hat{N}}_t$ is available, is to set the attempt probability near $1/{\hat{N}}_t$, keeping the offered retransmission count near one. These descriptions illustrate adaptive access rules; they do not assert that every backoff variant is stable at arbitrary load.

For a Markov chain invariant measure, $xP=x$, and hence $x{P}^n=x$. The irreducible Markov chain property supplies, for each $j$, an $n$ with $(P^n{)}_{kj}>0$. Nonnegativity gives $x_j\ge x_k(P^n{)}_{kj}>0$. Every coordinate of a nonzero invariant measure is positive.

Start the Markov chain at $k$, and let $T_k=\inf \{n\ge 1:X_n=k\}$ be its first return time. Each product in the series is the probability of a path with no intermediate visit to $k$. ThusThis is the expected number of visits to $j$ in an excursion, including the return endpoint and excluding the starting point. Because the chain is recurrent Markov chain, $T_k<\infty$ almost surely, and exactly one visit to $k$ is counted: ${\gamma }_k^k=1$. Counting the starting point instead of the return endpoint gives the equivalent usual excursion occupation measure.

For the lower bound, let $J=I\setminus \{k\}$, $Q=(p_{ij}{)}_{i,j\in J}$, and $r=(p_{kj}{)}_{j\in J}$. The stationarity equations on $J$, with $x_k=1$, are $x_J=r+x_{J}Q$. Iterating and using nonnegativity yieldsThe $j$th coordinate on the right is precisely the partial excursion series for $j\ne k$. Taking its increasing limit gives $x_j\ge {\gamma }_j^k$; for $j=k$ equality follows from $x_k={\gamma }_k^k=1$. The iteration is valid also on a countable state space because all summands are nonnegative.

For a finite graph $G=(V,E)$, let $o(\omega )={\sum }_{e\in E}\omega (e)$, and let $k_G(\omega )$ count connected components of the spanning open subgraph, including isolated graph vertices. The random-cluster model with $p\in [0,1]$ and $q>0$ isThe partition function $Z_{G,p,q}$ is the sum of these weights over all configurations, making the expression a probability measure.

For the lattice box, take all nearest-neighbor edges with both endpoints in ${\Lambda }_n$. A random-cluster boundary condition $\xi$ is a partition of the boundary graph vertices. Vertices in one block are identified, or wired together, before counting components; the identifications do not add random edges. Let $k_{\xi }(\omega )$ be the number of components of the resulting quotient open graph. ThenThe free random-cluster boundary condition has singleton blocks, while the wired random-cluster boundary condition has one boundary block. Arbitrary partitions are allowed; no assumption that the partition itself has a planar realization is needed for the monotonicity statement.

Write $\xi ⪯\zeta$ if every block of $\xi$ is contained in a block of $\zeta$, so $\zeta$ makes at least as many identifications. The precise boundary monotonicity of the random-cluster measure isEquivalently, the expectation of every real-valued order-preserving function is larger under the more wired measure. This is stochastic domination of probability measures on the coordinatewise configuration order.

To prove it, condition on every edge except $e=\{u,v\}$. If $u,v$ are already connected using those open edges and the boundary wiring, opening $e$ does not change $k_{\xi }$, so its conditional open probability is $p$. If they are not connected, opening it reduces $k_{\xi }$ by one. The ratio of the open weight to the closed weight is then $p/[q(1-p)]$. Thus the random-cluster single-edge conditional probability isFor $q\ge 1$ the second number is at most the first. Adding open edges or making the boundary partition coarser can only turn a disconnected pair into a connected one. Therefore these conditional open probabilities are increasing in both the exterior configuration and the amount of wiring.

Run a heat-bath Markov chain for each boundary partition. At every step choose the same uniformly sampled edge in both chains, sample the same independent uniform variable $U$, and set that edge open if $U$ is below its conditional open probability. Start both chains at the all-closed configuration. By the preceding inequality, the two configurations remain ordered at every update. Each marginal chain has its corresponding random-cluster measure as its stationary distribution: resampling one coordinate from its conditional distribution preserves that law. Because $0<p<1$ and $q>0$, every update gives both possible states positive probability; the finite chain is an irreducible Markov chain with aperiodicity, and hence converges to its unique stationary distribution. Taking expectations of any order-preserving function and passing to the limit proves the claimed stochastic domination of probability measures. At $q=1$ the two conditional probabilities agree, and the boundary condition has no effect on the independent bond percolation law.

For the final identity fix a plane embedding of the finite planar graph, and include the unbounded face in its planar dual graph. In the dual configuration ${\bar{\omega }}^{\ast }$, a dual edge is open exactly when its crossed primal edge is closed. Let $m=o(\omega )$. The spanning open primal subgraph has $|V|$ graph vertices, $m$ edges, and $k(\omega )$ components. The Euler formula for a connected planar graph, applied componentwise with the common exterior face accounted for, gives its number of faces asDeleting a closed primal edge merges its incident original faces precisely when its dual edge joins distinct dual components. Consequently the faces of the open primal subgraph correspond exactly to components of the open complementary dual subgraph. This remains true for bridges and loops, with their dual loops and bridges, and for a disconnected primal graph. Thus the planar cluster-count identity isAt the self-dual parameter of the random-cluster model, put $s=\sqrt{q}$ andFor fixed $G$ the factor $(1-p_{\mathrm{sd}}{)}^{|E|}$ is independent of $\omega$. The weight is therefore proportional toAbsorbing the remaining graph-dependent factor into the normalization gives the symmetric cluster weight at the self-dual parameter:Counting the outer dual face and all isolated primal graph vertices is essential for the constant in the Euler identity. No assumption that $G$ is self-dual is required for this proportionality.

Let $P$ be the transition kernel of the Markov chain. It is phi-irreducible if there is a nonzero sigma-finite measure $\phi$ such that, for every measurable $A$ and every starting state $x$,Equivalently, there is positive probability of eventually reaching every set of positive reference measure. For a finite state space with counting measure, this becomes ordinary irreducible Markov chain accessibility. On a continuous space, requiring access to each individual point would usually be inappropriate; positive-measure sets play that role. Irreducibility requires positive probability, rather than probability one, and does not itself assert recurrence or a finite mean return time.

Fix any configurations $s$ and $s^{\prime }$. List the sites where they differ and update those sites in turn to their target signs. Every specified site has positive probability $1/K^2$ of being selected. At every intermediate configuration, both values of its full conditional distribution have positive probability, since all weights $w_i(\pm 1)$ are finite and strictly positive. The finite prescribed sequence therefore has positive probability and reaches $s^{\prime }$.

Thus every configuration is accessible from every other configuration, so the sampler is an irreducible Markov chain, or equivalently phi-irreducible with counting measure. If $s=s^{\prime }$, a single update that keeps its selected spin unchanged also has positive probability. This simultaneously proves positive self-transition probability and aperiodicity, including $K=1$. The sign of finite $J$ does not alter the accessibility argument.

A finite irreducible Markov chain is positive recurrent. Its mean recurrence time to state $i$, starting at $i$ and counting the first positive return, is $1/{\pi }_i$. This identity comes from the long-run fraction of time spent at that state: successive return cycles each contain one visit at their start, so the fraction is the reciprocal of the mean cycle length. It remains valid for a periodic chain.

Here ${\pi }_0=2^{-k}$, henceFor $k=1$ the return is deterministically after two minutes, which checks the formula.

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.

In a loss network with fixed routing, calls of type $r$ arrive as independent Poisson processes with rates ${\nu }_r$. Every accepted call occupies $A_{jr}$ units of resource $j$ throughout its holding time. The link-route incidence matrix $A$ has nonnegative integer entries, $C$ is the resource-capacity vector, $n_r$ counts calls currently present, and $e_r$ is the $r$th coordinate unit vector. The feasible occupancy space isThe inequalities are coordinatewise. A call that would leave this space is rejected immediately, without queuing or changing $n$. With independent unit-rate exponential distributions for holding times, the memoryless property makes $n$ a continuous-time Markov chain, whose nonzero off-diagonal transition rates areThere are $n_r$ independent clocks of rate one for the second transition. Rejected arrivals are not jumps and do not appear in the off-diagonal transition rates.

Let $a(n)={\prod }_r{\nu }_r^{n_r}/n_r!$. For every feasible adjacent pair,Thus detailed balance for a continuous-time Markov chain gives the product-form stationary distribution of a loss network:In this convention $G(C)$ is the reciprocal normalizing sum. If every route consumes some resource, finite capacities make $S(C)$ finite. Even zero-resource routes cause no normalization difficulty: the sum is at most $\exp ({\sum }_r{\nu }_r)$. With positive arrival rates the reachable feasible class is an irreducible Markov chain, since calls can depart to the empty state and any feasible occupancy can be built from it. The stationary distribution is therefore unique on that class.

The vector $m=C-An$ records the free units of each resource. Its probability distribution ${\pi }^{\prime }(m)$ sums $\pi (n)$ over all occupancies with the same free resources. The map from $n$ to $m$ generally loses information: different call mixtures may consume exactly the same resources.

For ${\pi }^{\prime }(m)>0$, the conditional expectation can be computed by removing one call. The factorial identity $n_r\pi (n)={\nu }_r\pi (n-e_r)$ givesIndeed, $n\mapsto n-e_r$ is a bijection from the occupancies in this sum with $n_r>0$ to occupancies using $C-m-A{e}_r$ units. Conversely, adding one call to any such occupancy is feasible because its final resource use is $C-m$. Consequentlyand the conditional expectation is zero otherwise. Conditioning the identity ${\sum }_r{A}_{jr}{n}_r=C_j-m_j$ and multiplying by ${\pi }^{\prime }(m)$ now yieldsAlternatively, multiply the preceding unnormalized factorial identity by $A_{jr}$ and sum over $r$ directly; this proves the same formula even when ${\pi }^{\prime }(m)=0$, without dividing by a zero probability. This gives both the conditional expectation argument and the direct summation argument.

Use an ideal carrier-sense multiple access scheme on the interference graph. An active station finishes its transmission after an independent unit-rate exponential distribution waiting time. An inactive station has an independent attempt clock with an exponential distribution of rate $e^{{\theta }_r}$; an attempt succeeds only when all its neighbors are inactive. Attempts that are blocked do not change the state. Thus, on the independent sets represented by $S$, the continuous-time Markov chain has transition ratesThe empty independent set can be reached by successive deactivations, and any other independent set can be reached from it by successive activations. Hence this finite chain is an irreducible Markov chain. The weight $a_{\theta }(n)=e^{\theta \cdot n}$ satisfiesBy detailed balance for a continuous-time Markov chain, its unique stationary law isThis is a finite exponential family. Its natural parameter of an exponential family is $\theta$ and its mean parameter of an exponential family is the vector of active fractions.

The throughput region of an interference graph is exactly $\Lambda =\mathrm{conv}S$. To see the possibly less immediate inclusion, suppose a random feasible schedule has mean $v\ge \lambda$. Retain each of its active vertices $r$ independently with probability ${\lambda }_r/v_r$, interpreting zero coordinates as always deleted. A subset of an independent set remains an independent set; the thinned schedule has mean exactly $\lambda$. Thus $\lambda$ lies in the convex hull of $S$. The opposite inclusion follows from the definition using equality. Moreover $0,e_1,\dots ,e_R\in S$, so this convex hull has full dimension.

Now choose $\epsilon >0$ such that $\mu =\lambda +\epsilon 1$ remains in the interior of $\mathrm{conv}S$. Use interior moment matching in a finite exponential family. Consider the convex functionThere is a ball of radius $\delta >0$ around $\mu$ contained in $\mathrm{conv}S$. Maximizing a linear functional over the convex hull is the same as maximizing over its generating set, so, for every $\theta$,The last inequality uses the point $\mu +\delta \theta /\Vert \theta \Vert$ when $\theta \ne 0$. Hence $F$ is a coercive function and has a finite minimizer ${\theta }^{\ast }$. Differentiating the finite normalizing sum givesThis covariance matrix is a positive-definite matrix: a linear functional constant on all states of positive weight must be constant on $0,e_1,\dots ,e_R$, so its coefficients vanish. Thus $F$ is a strictly convex function; its minimizer is unique. At that minimizer the desired strict service margins areFor a backlogged station that transmits at unit speed whenever active, the long-run throughput is ${\mathbb{E}}_{\theta }[n_r]$, by the ergodic theorem for a finite continuous-time Markov chain. Therefore the ideal carrier-sense multiple access scheme can supply a strict service margin for every arrival vector in the interior of the throughput region of an interference graph. The local attempt rates can realize the whole interior capacity region in this sense. Boundary points may require parameters tending to infinity, and the argument gives no uniform delay or mixing-time bound near the boundary.

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

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.

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.

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

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.

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.