Geometric bounds for eigenvalues of Markov chains
From MaRDI portal
Consider an irreducible Markov chain with a finite state space x and denote by P(x,y), x,y\(\in X\), its transition probability. Assume that it has a stationary distribution \(\pi\) and P(x,y) is reversible with respect to \(\pi\). If so, as well-known, the Markov associated operator P is a self-adjoint contraction \(L^ 2(\pi)\), whose eigenvalues are \(1=\beta_ 0>\beta_ 1\geq...\geq \beta_{m-1}\geq -1\), where \(m=| X|\). The first aim of this paper is to develop methods for deriving bounds for \(\beta_ 1\), \(\beta_{m-1}\) and \(\beta_*=\max (\beta_ 1,| \beta_{m-1}|).\) The bounds depend on geometric quantities such as the maximum degree, diameter and covering number of associated graphs. Then simple examples (involving random walks on graphs) are given where the bounds are easily obtained and compared with the exact values. These examples seem to point out that the bounds obtained by the present authors are better than those derived through Cheeger-like inequalities. Finally, the bounds are used to get improved rates of convergence for a random walk associated with a problem of interest in theoretical computer science.
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?
Cited in
(only showing first 100 items - show all)- Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
- Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
- Isoperimetric inequalities and Markov chains
- A general class of Markov processes with explicit matrix-geometric solutions
- Choosing a random spanning subtree: A case study
- Strong stationary duality for continuous-time Markov chains. I: Theory
- Expectations for nonreversible Markov chains
- Simulated annealing with time-dependent energy function via Sobolev inequalities
- Relaxation of product Markov chains on product spaces
- What do we know about the Metropolis algorithm?
- Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?
- The spectral gap of the REM under Metropolis dynamics
- Piecewise constant triangular cooling schedules for generalized simulated annealing algorithms
- The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem
- Finite approximations to the critical reversible nearest particle system
- Comparison theorems for reversible Markov chains
- Asymptotic behaviour of time-inhomogeneous evolutions on von Neumann algebras
- Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region
- Moderate growth and random walk on finite groups
- Coupling, spectral gap and related topics. II
- A new upper bound for the isoperimetric number of de Bruijn networks
- Admissibility in quadratically regular problems and recurrence of symmetric Markov chains: Why the connection?
- A rapidly mixing stochastic system of finite interacting particles on the circle
- Algebraic convergence of Markov chains
- Honest exploration of intractable probability distributions via Markov chain Monte Carlo.
- A discipline of evolutionary programming
- Importance sampling for families of distributions
- Multiscale diffusion processes with periodic coefficients and an application to solute transport in porous media
- Decay of correlations for piecewise expanding maps.
- Speed of convergence to equilibrium and to normality for diffusions with multiple periodic scales
- Bounds on regeneration times and convergence rates for Markov chains
- Reversible algorithm of simulating multivariate densities with multi-hump
- Security from the adversary's inertia-controlling convergence speed when playing mixed strategy equilibria
- Spectral gap of random hyperbolic graphs and related parameters
- Random cluster dynamics for the Ising model is rapidly mixing
- The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
- The normalized Laplacian spectrum of subdivisions of a graph
- A framework for imperfectly observed networks
- Efficiency test of pseudorandom number generators using random walks
- Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains
- On the control of opinion dynamics in social networks
- Sensitivity analysis of a railway station track layout with respect to a given timetable
- Algebraic algorithms for sampling from conditional distributions
- The smallest eigenvalue for reversible Markov chains
- Random walks on a finite graph with congestion points
- Optimization problems for weighted graphs and related correlation estimates
- Finding optimal routings in Hamming graphs
- Markov chain decomposition for convergence rate analysis
- Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
- Extreme eigenfunctions of adjacency matrices for planar graphs employed in spatial analyses
- An empirical study of policy convergence in Markov decision process value iteration
- An adaptive simulated annealing algorithm.
- Note on the knapsack Markov chain.
- Convergence of independent particle systems
- Exponential convergence for attractive reversible subcritical nearest particle systems
- On the two-dimensional dynamical Ising model in the phase coexistence region
- Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure
- Markov chain convergence: From finite to infinite
- Poisson approximations for Markov-driven point processes
- Walks on generating sets of Abelian groups
- The long-run behavior of Markov chains
- On the number of Eulerian orientations of a graph
- Geometric ergodicity and the spectral gap of non-reversible Markov chains
- Bounds for the Kirchhoff index via majorization techniques
- Convergence rate of Markov chain methods for genomic motif discovery
- An interlacing technique for spectra of random walks and its application to finite percolation clusters
- Analytic proof of dual variational formula for the first eigenvalue in dimension one
- On the rate of convergence to equilibrium for reflected Brownian motion
- Estimating the spectral gap of a trace-class Markov operator
- Characterizing limits and opportunities in speeding up Markov chain mixing
- Homophily outlier detection in non-IID categorical data
- Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates
- Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
- Eigenvalues of Cayley graphs
- A quantitative McDiarmid's inequality for geometrically ergodic Markov chains
- On the convergence time of some non-reversible Markov chain Monte Carlo methods
- Speed of convergence to the quasi-stationary distribution for Lévy input fluid queues
- On the limitations of single-step drift and minorization in Markov chain convergence analysis
- Pattern formation in auxin flux
- Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
- A note on geometric bounds for eigenvalues
- The convergence rate of the Gibbs sampler for generalized 1-D Ising model
- Flocking with general local interaction and large population
- Metropolis-Hastings reversiblizations of non-reversible Markov chains
- Convergence time to equilibrium of the Metropolis dynamics for the GREM
- A note on Sobolev type inequalities on graphs with polynomial volume growth
- Quantum ergodicity on graphs: from spectral to spatial delocalization
- Consistent estimation of the spectrum of trace class data augmentation algorithms
- A version of Aldous' spectral-gap conjecture for the zero range process
- Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate
- Invariance principle for the random conductance model in a degenerate ergodic environment
- Network cohesion
- A note on Markov normalized magnetic eigenmaps
- Uniform upper bound of the second largest eigenvalue of stochastic matrices with equal-neighbor rule
- Aging in metropolis dynamics of the REM: a proof
- Randomized scheduling algorithm for queueing networks
- A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
- The dual Cheeger constant and spectra of infinite graphs
- On asymptotics for Vaserstein coupling of Markov chains
- On perturbation bounds for continuous-time Markov chains
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)
