Speeding up random walk mixing by starting from a uniform vertex
From MaRDI portal
Publication:6126961
DOI10.1214/24-ejp1091arXiv2208.07462MaRDI QIDQ6126961
Patrick Morris, Oriol Serra, Guillem Perarnau, Alberto Espuny Díaz
Publication date: 10 April 2024
Published in: Electronic Journal of Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2208.07462
Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Diffusion processes (60J60) Random walks on graphs (05C81)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Faster mixing and small bottlenecks
- Cutoff phenomena for random walks on random regular graphs
- Largest random component of a k-cube
- Renormalization group analysis of the small-world network model
- Random walks on the random graph
- Cutoff for nonbacktracking random walks on sparse random graphs
- Universality of cutoff for graphs with an added random matching
- Random walk on sparse random digraphs
- Anatomy of the giant component: the strictly supercritical regime
- Improved bounds for sampling colorings
- Smoothed Analysis on Connected Graphs
- The small-world phenomenon
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- The evolution of the mixing rate of a simple random walk on the giant component of a random graph
- Smoothed analysis of algorithms
- A random polynomial-time algorithm for approximating the volume of convex bodies
- The emergence of a giant component in random subgraphs of pseudo-random graphs
- How many random edges make a dense graph hamiltonian?
- Random Walks on Small World Networks
- EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
- Learning and Smoothed Analysis
- Universality for bounded degree spanning trees in randomly perturbed graphs
- The Mixing Time of the Newman-Watts Small-World Model
- Smoothed analysis of tensor decompositions
- The Cover Time of Random Regular Graphs
- Smoothed Analysis of the k-Means Method
- The diameter of sparse random graphs
- Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
