Geometric bounds for eigenvalues of Markov chains
From MaRDI portal
Publication:808102
DOI10.1214/aoap/1177005980zbMath0731.60061OpenAlexW2043694962WikidataQ98839744 ScholiaQ98839744MaRDI QIDQ808102
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
Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)
Related Items
Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region, Markov chain decomposition for convergence rate analysis, Moderate growth and random walk on finite groups, 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, Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation, Spectral gap, isoperimetry and concentration on trees, An empirical study of policy convergence in Markov decision process value iteration, Security from the adversary's inertia-controlling convergence speed when playing mixed strategy equilibria, An adaptive simulated annealing algorithm., Note on the knapsack Markov chain., Convergence of independent particle systems, \(L^p\) estimates for Feynman-Kac propagators with time-dependent reference measures, Obtaining a linear combination of the principal components of a matrix on quantum computers, Upper bounds on algebraic connectivity via convex optimization, Spectral gap of random hyperbolic graphs and related parameters, Random cluster dynamics for the Ising model is rapidly mixing, Logarithmic Sobolev, isoperimetry and transport inequalities on graphs, Exponential convergence for attractive reversible subcritical nearest particle systems, Spectral gap for the zero range process with constant rate, On the two-dimensional dynamical Ising model in the phase coexistence region, Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure, The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions, Spectral partitioning works: planar graphs and finite element meshes, Oja's algorithm for graph clustering, Markov spectral decomposition, and risk sensitive control, Markov chain convergence: From finite to infinite, 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, Constructing optimal transition matrix for Markov chain Monte Carlo, Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion, On the rate of convergence of the Gibbs sampler for the 1-D Ising model by geometric bound, Normalized graph Laplacians for directed graphs, Bayesian analysis of stochastic volatility models with fat-tails and correlated errors, Convergence rate for predictive recursion estimation of finite mixtures, A one-dimensional coagulation-fragmentation process with a dynamical phase transition, On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes, Dynamic normal forms and dynamic characteristic polynomial, Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain, Algebraic convergence of Markov chains, Rate of convergence to an asymptotic profile for the self-similar fragmentation and growth-fragmentation equations, Approximating the number of double cut-and-join scenarios, The mathematics of mixing things up, Pattern discrete and mixed hit-and-run for global optimization, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Exact and asymptotic results on coarse Ricci curvature of graphs, Multi-way dual Cheeger constants and spectral bounds of graphs, Honest exploration of intractable probability distributions via Markov chain Monte Carlo., Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions, Characterization of equilibrium measures for critical reversible nearest particle systems, The normalized Laplacian spectrum of subdivisions of a graph, Choosing a random spanning subtree: A case study, On the spectrum of the normalized Laplacian of iterated triangulations of graphs, Strong stationary duality for continuous-time Markov chains. I: Theory, 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, Nash inequalities for finite Markov chains, Aging of the Metropolis dynamics on the random energy model, Scalable learning and inference in Markov logic networks, Thermalization time bounds for Pauli stabilizer Hamiltonians, Tight estimates for convergence of some non-stationary consensus algorithms, Evaluation of formal posterior distributions via Markov chain arguments, When does allow the Hardy inequality to calculate an exact Poincaré constant on a line?, A framework for imperfectly observed networks, Efficiency test of pseudorandom number generators using random walks, Intermediate range migration in the two-dimensional stepping stone model, On the control of opinion dynamics in social networks, Maximum flows and minimum cuts in the plane, Explicit error bounds for lazy reversible Markov chain Monte Carlo, The swapping algorithm for the Hopfield model with two patterns, Asymptotic optimality of isoperimetric constants, Sensitivity analysis of a railway station track layout with respect to a given timetable, Algebraic algorithms for sampling from conditional distributions, Expectations for nonreversible Markov chains, Simulated annealing with time-dependent energy function via Sobolev inequalities, Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions, Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions, Relaxation of product Markov chains on product spaces, What do we know about the Metropolis algorithm?, 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, 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, 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, Decay of correlations for piecewise expanding maps., Finite approximations to the critical reversible nearest particle system, Speed of convergence to equilibrium and to normality for diffusions with multiple periodic scales, Bounds on regeneration times and convergence rates for Markov chains, Efficient simulated annealing on fractal energy landscapes, Finding optimal routings in Hamming graphs, Asymptotic behaviour of time-inhomogeneous evolutions on von Neumann algebras, Reversible algorithm of simulating multivariate densities with multi-hump, Convergence of clock processes and aging in Metropolis dynamics of a truncated REM, Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration, Network cohesion, Ordering in voter models on networks: exact reduction to a single-coordinate diffusion, Eigenvalues of Cayley graphs, Monte Carlo algorithms for computing \(\alpha \)-permanents, Right order spectral gap estimates for generating sets of ℤ4, Comparisons of Three Approaches for Discrete Conditional Models, Distributed Optimization in Networking: Recent Advances in Combinatorial and Robust Formulations, Sampling Edge Covers in 3-Regular Graphs, Improved bounds for the large-time behaviour of simulated annealing, Stability and exponential convergence of continuous-time Markov chains, Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains, Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow, Poisson approximations for Markov-driven point processes, Walks on generating sets of Abelian groups, Some remarks on replicated simulated annealing, The long-run behavior of Markov chains, On the number of Eulerian orientations of a graph, Optimal Variance Reduction for Markov Chain Monte Carlo, Uniform upper bound of the second largest eigenvalue of stochastic matrices with equal-neighbor rule, Geometric bounds for convergence rates of averaging algorithms, Geometric ergodicity and the spectral gap of non-reversible Markov chains, Aging in metropolis dynamics of the REM: a proof, Bounds for the Kirchhoff index via majorization techniques, The Quantum Complexity of Markov Chain Monte Carlo, Randomized scheduling algorithm for queueing networks, Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs, Estimation of spectral gap for Markov chains, Isoperimetric Inequalities and Decay of Iterated Kernels for Almost-transitive Markov Chains, Convergence rate of Markov chain methods for genomic motif discovery, Long-Range Percolation Mixing Time, An interlacing technique for spectra of random walks and its application to finite percolation clusters, A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces, The dual Cheeger constant and spectra of infinite graphs, Analytic proof of dual variational formula for the first eigenvalue in dimension one, On the convergence time of some non-reversible Markov chain Monte Carlo methods, On asymptotics for Vaserstein coupling of Markov chains, Speed of convergence to the quasi-stationary distribution for Lévy input fluid queues, On perturbation bounds for continuous-time Markov chains, Dynamic Phase Diagram of the REM, Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler, A note on random walks with absorbing barriers and sequential Monte Carlo methods, Self-testing algorithms for self-avoiding walks, Analyzing Glauber dynamics by comparison of Markov chains, On the limitations of single-step drift and minorization in Markov chain convergence analysis, A semidefinite bound for mixing rates of Markov chains, A hierarchy of gaussian and non-gaussian asymptotics of a class of Fokker-Planck equations with multiple scales, Maximum Flows and Minimum Cuts in the Plane, On the rate of convergence to equilibrium for reflected Brownian motion, Pattern formation in auxin flux, Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs, A note on geometric bounds for eigenvalues, Rate of convergence of the Swendsen-Wang dynamics in image segmentation problems: a theoretical and experimental study, Une variante de l'inégalité de Cheeger pour les chaînes de Markov finies, Estimating the spectral gap of a trace-class Markov operator, Estimate of exponential convergence rate in total variation by spectral gap, A Markov chain sampler for contingency table exact inference, Markov-chain monte carlo: Some practical implications of theoretical results, Functional inequalities for discrete gradients and application to the geometric distribution, Analysis of top to bottom-\(k\) shuffles, Systematic scan for sampling colorings, An Extension of the Metropolis Algorithm, The convergence rate of the Gibbs sampler for generalized 1-D Ising model, The mixing time of Glauber dynamics for coloring regular trees, Characterizing limits and opportunities in speeding up Markov chain mixing, Random walks on the vertices of transportation polytopes with constant number of sources, Error bounds for computing the expectation by Markov chain Monte Carlo, Flocking with general local interaction and large population, Homophily outlier detection in non-IID categorical data, Metropolis-Hastings reversiblizations of non-reversible Markov chains, Capacity of an associative memory model on random graph architectures, A dynamic programming approach to efficient sampling from Boltzmann distributions, A cycle-based bound for subdominant eigenvalues of stochastic matrices, Markov Chain Approach to Probabilistic Guidance for Swarms of Autonomous Agents, Convergence time to equilibrium of the Metropolis dynamics for the GREM, Simulated annealing for tensor network states, An Almost m-wise Independent Random Permutation of the Cube, Bounds for the second largest eigenvalue of a transition matrix, Fastest mixing Markov chain problem for the union of two cliques, Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice, Conductance bounds on the L2 convergence rate of Metropolis algorithms on unbounded state spaces, A note on Sobolev type inequalities on graphs with polynomial volume growth, Quantum ergodicity on graphs: from spectral to spatial delocalization, A monotonicity in reversible Markov chains, Consistent estimation of the spectrum of trace class data augmentation algorithms, Logarithmic Sobolev inequalities for finite Markov chains, A version of Aldous' spectral-gap conjecture for the zero range process, Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates, Spectral homogenization of reversible random walks on \(\mathbb Z^d\) in a random environment., On swapping and simulated tempering algorithms., The exit path of a Markov chain with rare transitions, Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate, A hierarchical method for obtaining eigenvalue enclosures, Unnamed Item, Extremal first passage times for trees, Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians, Generalization of discrete-time geometric bounds to convergence rate of Markov processes on Rn, Invariance principle for the random conductance model in a degenerate ergodic environment, Mixing times for the Swapping Algorithm on the Blume-Emery-Griffiths model, Diffusions on graphs, Poisson problems and spectral geometry, Equi-energy sampling does not converge rapidly on the mean-field Potts model with three colors close to the critical temperature, Unnamed Item, On improved bounds and conditions for the convergence of Markov chains, Fixed Precision MCMC Estimation by Median of Products of Averages, Rates of convergence for Gibbs sampling in the analysis of almost exchangeable data, Mixing times for the simple exclusion process with open boundaries, Mixing of MCMC algorithms, Latent uniform samplers on multivariate binary spaces, Unnamed Item, Universal Features for High-Dimensional Learning and Inference, Time-Inhomogeneous Diffusion Geometry and Topology, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Unnamed Item, Unnamed Item, Mod-ϕ Convergence, II: Estimates on the Speed of Convergence, The Spatial Smoothing Method of Clock Synchronization in Wireless Networks, Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions, Remarks and open problems on the minimum permanent of acyclic doubly stochastic matrices, Lower bounds to the spectral gap of Davies generators, Counting independent sets in graphs with bounded bipartite pathwidth, Dependence ordering for Markov processes on partially ordered spaces, Some results characterizing the finite time behaviour of the simulated annealing algorithm., On quantitative convergence to quasi-stationarity, Bayesian computation: a summary of the current state, and samples backwards and forwards, Generalized quasirandom properties of expanding graph sequences, Rapid mixing for lattice colourings with fewer colours, Sensitivity and convergence of uniformly ergodic Markov chains, Finite-Time Behavior of Slowly Cooled Annealing Chains, Dobrushin Conditions and Systematic Scan, Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains, On the spectral radius and stiffness of Markov jump process rate matrices, Rapid mixing of Swendsen–Wang dynamics in two dimensions, A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, The $\chi ^2$χ2-divergence and mixing times of quantum Markov processes, Computable Bounds on the Spectral Gap for Unreliable Jackson Networks
