Geometric bounds for eigenvalues of Markov chains

DOI10.1214/AOAP/1177005980zbMATH Open0731.60061OpenAlexW2043694962WikidataQ98839744 ScholiaQ98839744MaRDI QIDQ808102FDOQ808102

Authors: Persi Diaconis, Daniel W. Stroock 

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1214/aoap/1177005980

Recommendations

• Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
• Comparison theorems for reversible Markov chains
• On the Convergence of Reversible Markov Chains
• Explicit bounds for geometric convergence of Markov chains
• Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?

zbMATH Keywords

rates of convergencestationary distributionCheeger-like inequalitieseigenvalues of Markov chains

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Cited In (only showing first 100 items - show all)

• Tight estimates for convergence of some non-stationary consensus algorithms
• Pattern formation in auxin flux
• The mixing time of Glauber dynamics for coloring regular trees
• Convergence of independent particle systems
• Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation
• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• Dependence ordering for Markov processes on partially ordered spaces
• Optimization problems for weighted graphs and related correlation estimates
• Title not available (Why is that?)
• Analysis of top to bottom-\(k\) shuffles
• \(L^p\) estimates for Feynman-Kac propagators with time-dependent reference measures
• Mixing times for the swapping algorithm on the Blume-Emery-Griffiths model
• Computable bounds on the spectral gap for unreliable Jackson networks
• Pattern discrete and mixed hit-and-run for global optimization
• A note on Sobolev type inequalities on graphs with polynomial volume growth
• Simulated annealing with time-dependent energy function via Sobolev inequalities
• Approximating the number of double cut-and-join scenarios
• Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate
• The swapping algorithm for the Hopfield model with two patterns
• A general class of Markov processes with explicit matrix-geometric solutions
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Long-Range Percolation Mixing Time
• Stability and exponential convergence of continuous-time Markov chains
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Asymptotic optimality of isoperimetric constants
• Constructing optimal transition matrix for Markov chain Monte Carlo
• An empirical study of policy convergence in Markov decision process value iteration
• On improved bounds and conditions for the convergence of Markov chains
• Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions
• Multi-way dual Cheeger constants and spectral bounds of graphs
• On the rate of convergence of the Gibbs sampler for the 1-D Ising model by geometric bound
• Rapid mixing for lattice colourings with fewer colours
• Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
• Maximum flows and minimum cuts in the plane
• Rates of convergence for Gibbs sampling in the analysis of almost exchangeable data
• Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains
• Dynamic normal forms and dynamic characteristic polynomial
• Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure
• Markov chain approach to probabilistic guidance for swarms of autonomous agents
• Strong stationary duality for continuous-time Markov chains. I: Theory
• Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
• Geometric inequalities for the eigenvalues of concentrated Markov chains
• Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?
• A discipline of evolutionary programming
• When does allow the Hardy inequality to calculate an exact Poincaré constant on a line?
• Bounds for the second largest eigenvalue of a transition matrix
• A hierarchical method for obtaining eigenvalue enclosures
• On swapping and simulated tempering algorithms.
• Uniform estimates of nonlinear spectral gaps
• The mixing time of a random walk on a long-range percolation cluster in pre-Sierpinski gasket
• The worm process for the Ising model is rapidly mixing
• Characterization of equilibrium measures for critical reversible nearest particle systems
• Scalable learning and inference in Markov logic networks
• The normalized Laplacian spectrum of subdivisions of a graph
• A Markov chain sampler for contingency table exact inference
• Finite approximations to the critical reversible nearest particle system
• Efficient simulated annealing on fractal energy landscapes
• Lower bounds to the spectral gap of Davies generators
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• Thermalization time bounds for Pauli stabilizer Hamiltonians
• Isoperimetric Inequalities and Decay of Iterated Kernels for Almost-transitive Markov Chains
• Some results characterizing the finite time behaviour of the simulated annealing algorithm.
• Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
• On the Convergence of Reversible Markov Chains
• Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
• A cycle-based bound for subdominant eigenvalues of stochastic matrices
• Metropolis-Hastings reversiblizations of non-reversible Markov chains
• Moderate growth and random walk on finite groups
• Isoperimetric inequalities and Markov chains
• Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
• Randomized scheduling algorithm for queueing networks
• Convergence of clock processes and aging in Metropolis dynamics of a truncated REM
• The mathematics of mixing things up
• Upper bounds on algebraic connectivity via convex optimization
• A new upper bound for the isoperimetric number of de Bruijn networks
• Sensitivity and convergence of uniformly ergodic Markov chains
• Estimation of spectral gap for Markov chains
• Rate of convergence to an asymptotic profile for the self-similar fragmentation and growth-fragmentation equations
• Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region
• Normalized graph Laplacians for directed graphs
• Convergence rate for predictive recursion estimation of finite mixtures
• On the control of opinion dynamics in social networks
• Speed of convergence to equilibrium and to normality for diffusions with multiple periodic scales
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Maximum flows and minimum cuts in the plane
• Evaluation of formal posterior distributions via Markov chain arguments
• A one-dimensional coagulation-fragmentation process with a dynamical phase transition
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain
• A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
• Spectral gap for the zero range process with constant rate
• The spectral gap of the REM under Metropolis dynamics
• Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler
• Admissibility in quadratically regular problems and recurrence of symmetric Markov chains: Why the connection?
• Spectral gap, isoperimetry and concentration on trees
• Quantum ergodicity on graphs: from spectral to spatial delocalization
• On quantitative convergence to quasi-stationarity
• Decay of correlations for piecewise expanding maps.
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• On the two-dimensional dynamical Ising model in the phase coexistence region

This page was built for publication: Geometric bounds for eigenvalues of Markov chains

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