Comparison inequalities and fastest-mixing Markov chains

DOI10.1214/12-AAP886zbMATH Open1288.60089arXiv1109.6075OpenAlexW3105460891MaRDI QIDQ373832FDOQ373832

Authors: James Allen Fill, Jonas Kahn 

Publication date: 25 October 2013

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: We introduce a new partial order on the class of stochastically monotone Markov kernels having a given stationary distribution $pi$ on a given finite partially ordered state space $mathcalX$. When $KpreceqL$ in this partial order we say that $K$ and $L$ satisfy a comparison inequality. We establish that if $K_1,ldots,K_t$ and $L_1,ldots,L_t$ are reversible and $K_{s}preceq{L}_s$ for $s=1,ldots,t$, then $K_{1}cdots{K}_{t}preceq{L}_{1}cdots{L}_t$. In particular, in the time-homogeneous case we have $K^{t}preceq{L}^t$ for every $t$ if $K$ and $L$ are reversible and $KpreceqL$, and using this we show that (for suitable common initial distributions) the Markov chain $Y$ with kernel $K$ mixes faster than the chain $Z$ with kernel $L$, in the strong sense that at every time $t$ the discrepancy - measured by total variation distance or separation or $L^2$-distance - between the law of $Y_t$ and $pi$ is smaller than that between the law of $Z_t$ and $pi$. Using comparison inequalities together with specialized arguments to remove the stochastic monotonicity restriction, we answer a question of Persi Diaconis by showing that, among all symmetric birth-and-death kernels on the path $mathcalX=0,ldots,n$, the one (we call it the uniform chain) that produces fastest convergence from initial state 0 to the uniform distribution has transition probability 1/2 in each direction along each edge of the path, with holding probability 1/2 at each endpoint.

Full work available at URL: https://arxiv.org/abs/1109.6075

Recommendations

• Fastest Mixing Markov Chain on a Graph
• Bounding fastest mixing
• Markov chain comparison
• scientific article; zbMATH DE number 1301966
• Comparison theorems for reversible Markov chains

zbMATH Keywords

Markov chainslog-concave distributionsbirth-and-death chainscomparison inequalitiesfastest mixingstochastic monotonicity

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Title not available (Why is that?)
• Inequalities: theory of majorization and its applications
• Title not available (Why is that?)
• Strong uniform times and finite random walks
• Title not available (Why is that?)
• Strong stationary times via a new form of duality
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
• Comparison theorems for reversible Markov chains
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Proof of Aldous' spectral gap conjecture
• An interruptible algorithm for perfect sampling via Markov chains
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• Merging for time inhomogeneous finite Markov chains. I: Singular values and stability
• Bounds on the coarseness of random sums
• Time inhomogeneous Markov chains with wave-like behavior
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• Bounding fastest mixing
• Time to Stationarity for a Continuous-Time Markov Chain
• Fastest mixing Markov chain on graphs with symmetries
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fastest Mixing Markov Chain on a Graph
• Absolute algebraic connectivity of trees
• Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities
• Fastest Mixing Markov Chain on a Path
• Some circumstances where extra updates can delay mixing

Cited In (12)

• Stochastic orderings of multivariate elliptical distributions
• Variational formulas for asymptotic variance of general discrete-time Markov chains
• Comparison of hit-and-run, slice sampler and random walk Metropolis
• Fastest mixing Markov chain problem for the union of two cliques
• Monotonicity for continuous-time random walks
• Title not available (Why is that?)
• Geometric bounds on the fastest mixing Markov chain
• Monte Carlo Markov chains constrained on graphs for a target with disconnected support
• Comparison theory for Markov chains on different state spaces and application to random walk on derangements
• Existence condition of strong stationary times for continuous time Markov chains on discrete graphs
• Comparison theorems for Green functions of Markov chains
• Strong stationary duality for diffusion processes

This page was built for publication: Comparison inequalities and fastest-mixing Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q373832)