bibkey: boyddiaconisxiao2004fastestmixing
authors: Stephen Boyd; Persi Diaconis; Lin Xiao
year: 2004
title: Fastest Mixing Markov Chain on a Graph
doi: 10.1137/S0036144503423264
url: https://web.stanford.edu/~boyd/papers/pdf/fmmc.pdf
claim: Fastest mixing on a fixed graph has a convex semidefinite formulation and dual optimality bounds, with an extension to prescribed reversible equilibrium laws.
strata_touched: []
license: citation-only
triage: anchor

Fastest mixing and the constrained site-kernel family

The primary source is SIAM Review 46(4), 667–689, DOI:10.1137/S0036144503423264, available as the author-hosted PDF. This note cites the source without redistributing its text or PDF.

The paper minimizes the second-largest eigenvalue modulus of a Markov transition matrix under the stochastic and graph-support constraints. It supplies a convex formulation, a semidefinite program and dual bounds. Its extensions include reversible chains with a specified equilibrium distribution.

For the positive FIB activity law, the phase-information matrix $H_{\omega }$ gives a random-scan heat-bath transition matrix $P_{\omega }=D_{\psi }^{-1}(I-H_{\omega })D_{\psi }$. The matrix $I-H_{\omega }$ is a convex combination of orthogonal projections, so its spectrum is nonnegative. Its second-largest eigenvalue modulus is therefore one minus the nonconstant gap of $H_{\omega }$.

This is a fastest-mixing problem inside the affine family generated by three fixed site kernels. The two endpoint edges share a site-selection probability. Optimizing all graph-edge probabilities independently would enlarge the feasible set. The paper’s general convex and dual mechanisms retain their supplier ownership; the exact FIB site weights and their positive-activity uniqueness require their own certificate.