Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow

DOI10.1017/S0963548300000390zbMath0801.90039OpenAlexW2033281046MaRDI QIDQ4291194

Publication date: 1 December 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300000390

zbMATH Keywords

finite Markov chains multicommodity flow

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields, Large cycles in generalized Johnson graphs, Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs, Expansion of random 0/1 polytopes, Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes, Scale-free percolation mixing time, Unnamed Item, Approximate sampling of graphs with near-\(P\)-stable degree intervals, Geometric bounds on the fastest mixing Markov chain, Grid spanners with low forwarding index for energy efficient networks, Uniform multicommodity flows in the hypercube with random edge‐capacities, Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk, Counting independent sets in graphs with bounded bipartite pathwidth, Efficient Simulation of High Dimensional Gaussian Vectors, Sensitivity and convergence of uniformly ergodic Markov chains, Sampling binary contingency tables with a greedy start, Dobrushin Conditions and Systematic Scan, Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains, A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix, Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region, Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\)., On approximating weighted sums with exponentially many terms, A modified conditional Metropolis-Hastings sampler, A Spectral Independence View on Hard Spheres via Block Dynamics, Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation, On the cover time and mixing time of random geometric graphs, On mixing and edge expansion properties in randomized broadcasting, Sampling Edge Covers in 3-Regular Graphs, Randomly coloring planar graphs with fewer colors than the maximum degree, 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, Spectral gap for the zero range process with constant rate, Derandomized constructions of \(k\)-wise (almost) independent permutations, On the two-dimensional dynamical Ising model in the phase coexistence region, Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure, Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains, Poisson approximation for non-backtracking random walks, Geometric ergodicity of a more efficient conditional Metropolis-Hastings algorithm, The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions, Markov chain convergence: From finite to infinite, Mixing time of the switch Markov chain and stable degree sequences, Asymptotic exponential law for the transition time to equilibrium of the metastable kinetic Ising model with vanishing magnetic field, Heat-bath random walks with Markov bases, Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions, Geometric bounds for convergence rates of averaging algorithms, The cover times of random walks on random uniform hypergraphs, A new criterion and method for amino acid classification, Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion, NON-BACKTRACKING RANDOM WALKS MIX FASTER, On the rate of convergence of the Gibbs sampler for the 1-D Ising model by geometric bound, Simple permutations mix even better, Unnamed Item, The Quantum Complexity of Markov Chain Monte Carlo, A one-dimensional coagulation-fragmentation process with a dynamical phase transition, On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes, Mixing of the square plaquette model on a critical length scale, Conductance and noncommutative dynamical systems, Unnamed Item, Unnamed Item, Pattern hit-and-run for sampling efficiently on polytopes, The switch Markov chain for sampling irregular graphs and digraphs, Some Problems on Approximate Counting in Graphs and Matroids, Convergence rate of Markov chain methods for genomic motif discovery, Approximating the number of double cut-and-join scenarios, Pattern discrete and mixed hit-and-run for global optimization, Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs, Minimising MCMC variance via diffusion limits, with an application to simulated tempering, Cover time of a random graph with given degree sequence, Stochastic modelling of the eukaryotic heat shock response, The flip Markov chain for connected regular graphs, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Structure and eigenvalues of heat-bath Markov chains, Function-specific mixing times and concentration away from equilibrium, The cover time of random geometric graphs, The mixing time of switch Markov chains: a unified approach, Configuring Random Graph Models with Fixed Degree Sequences, Improved bounds for sampling colorings, Self-testing algorithms for self-avoiding walks, 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, New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling, Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions, Cutoff for the square plaquette model on a critical length scale, A semidefinite bound for mixing rates of Markov chains, A randomized algorithm for the joining protocol in dynamic distributed networks, Thermalization time bounds for Pauli stabilizer Hamiltonians, Clustering and community detection in directed networks: a survey, Tight estimates for convergence of some non-stationary consensus algorithms, Testing Expansion in Bounded-Degree Graphs, Convergence of Conditional Metropolis-Hastings Samplers, Tight bounds for the cover time of multiple random walks, Markov-chain monte carlo: Some practical implications of theoretical results, Systematic scan for sampling colorings, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Unnamed Item, The mixing time of Glauber dynamics for coloring regular trees, Uniform Sampling of Digraphs with a Fixed Degree Sequence, Comparing with octopi, Random walks on the vertices of transportation polytopes with constant number of sources, Half-graphs, other non-stable degree sequences, and the switch Markov chain, A dynamic programming approach to efficient sampling from Boltzmann distributions, Counting and sampling SCJ small parsimony solutions, The Glauber dynamics for edge‐colorings of trees, An Almost m-wise Independent Random Permutation of the Cube, Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice, Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions, Approximability of the eight-vertex model, What do we know about the Metropolis algorithm?, Communities, Random Walks, and Social Sybil Defense, Logarithmic Sobolev inequalities for finite Markov chains, A new genetic algorithm, Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?, The spectral gap of the REM under Metropolis dynamics, Linking and cutting spanning trees, Approximating the number of monomer-dimer coverings of a lattice., Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate, Unnamed Item, Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices

Cites Work