Characterizing limits and opportunities in speeding up Markov chain mixing

DOI10.1016/j.spa.2021.03.006zbMath1469.60224OpenAlexW3138179454MaRDI QIDQ2029783

Alain Sarlette, Simon Apers, Francesco Ticozzi

Publication date: 4 June 2021

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/30800

zbMATH Keywords

Markov chainsmixing timealgorithm design and analysisnetwork theory (graphs)

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items (1)

Approximate lumpability for Markovian agent-based models using local symmetries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Improving the convergence of reversible samplers
• Non-reversible Metropolis-Hastings
• Some things we've learned (about Markov chain Monte Carlo)
• Irreversible Monte Carlo algorithms for efficient sampling
• Markov chain mixing time on cycles
• Geometric bounds for eigenvalues of Markov chains
• First- and second-order diffusive methods for rapid, coarse, distributed load balancing
• Bounding the convergence time of local probabilistic evolution
• Improved mixing rates of directed cycles by added connection
• Bounds on lifting continuous-state Markov chains to speed up mixing
• Analysis of a nonreversible Markov chain sampler.
• Non-backtracking random walk
• A piecewise deterministic scaling limit of lifted Metropolis-Hastings in the Curie-Weiss model
• Analysis of accelerated gossip algorithms
• On the spectral analysis of second-order Markov chains
• Graph diameter, eigenvalues, and minimum-time consensus
• Lifting Markov chains to speed up mixing
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
• Adding a Single State Memory Optimally Accelerates Symmetric Linear Maps
• Finite-Time Consensus Using Stochastic Matrices With Positive Diagonals
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Fastest Mixing Markov Chain on Graphs with Symmetries
• Liftings of Tree-Structured Markov Chains
• The Calculation of Posterior Distributions by Data Augmentation
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Accelerating Consensus by Spectral Clustering and Polynomial Filters
• Optimization and Analysis of Distributed Averaging With Short Node Memory
• Polynomial Filtering for Fast Convergence in Distributed Consensus
• Chebyshev Polynomials in Distributed Consensus Applications
• Linear Time Average Consensus and Distributed Optimization on Fixed Graphs
• Fastest Mixing Markov Chain on a Graph
• Distributed Averaging Via Lifted Markov Chains
• Equation of State Calculations by Fast Computing Machines
• Positive contraction mappings for classical and quantum Schrödinger systems
• Discrete-time classical and quantum Markovian evolutions: Maximum entropy problems on path space
• Location-Aided Fast Distributed Consensus in Wireless Networks
• Order-Optimal Consensus Through Randomized Path Averaging
• The computational complexity of linear optics
• Monte Carlo sampling methods using Markov chains and their applications

This page was built for publication: Characterizing limits and opportunities in speeding up Markov chain mixing