Random walk on sparse random digraphs

DOI10.1007/s00440-017-0796-7zbMath1383.05294arXiv1508.06600OpenAlexW2963061394MaRDI QIDQ2413249

Charles Bordenave, Justin Salez, Pietro Caputo

Publication date: 10 April 2018

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.06600

zbMATH Keywords

cutoff phenomenon

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Density (toughness, etc.) (05C42)

Related Items (23)

Universality of cutoff for graphs with an added random matching ⋮ Mixing times of random walks on dynamic configuration models ⋮ New ways of solving large Markov chains ⋮ A threshold for cutoff in two-community random graphs ⋮ CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS ⋮ Mixing time of PageRank surfers on sparse random digraphs ⋮ The cutoff phenomenon for the stochastic heat and wave equation subject to small Lévy noise ⋮ Speeding up random walk mixing by starting from a uniform vertex ⋮ Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022 ⋮ On the meeting of random walks on random DFA ⋮ Cutoff for permuted Markov chains ⋮ The diameter of the directed configuration model ⋮ Rankings in directed configuration models with heavy tailed in-degrees ⋮ A random walk on the Rado graph ⋮ Spectrum of large random Markov chains: Heavy-tailed weights on the oriented complete graph ⋮ The degree-wise effect of a second step for a random walk on a graph ⋮ Stationary distribution and cover time of sparse directed configuration models ⋮ Cutoff at the ``entropic time for sparse Markov chains ⋮ Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018 ⋮ The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise ⋮ Mixing time trichotomy in regenerating dynamic digraphs ⋮ The spectral gap of sparse random digraphs ⋮ Linking the mixing times of random walks on static and dynamic random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The cutoff profile for the simple exclusion process on the circle
• Cutoff on all Ramanujan graphs
• Stationary distribution and cover time of random walks on random digraphs
• Mixing time of near-critical random graphs
• Diameter and stationary distribution of random \(r\)-out digraphs
• The cover time of the preferential attachment graph
• Critical random graphs: Diameter and mixing time
• Cutoff phenomena for random walks on random regular graphs
• The cutoff phenomenon for ergodic Markov processes
• A fixed point theorem for distributions
• On tail probabilities for martingales
• Moments, continuity, and multifractal analysis of Mandelbrot martingales
• On generalized multiplicative cascades
• Random walks on the random graph
• Asymptotic properties and absolute continuity of laws stable by random weighted mean.
• Cutoff for nonbacktracking random walks on sparse random graphs
• Stein's method for concentration inequalities
• The mixing time of the giant component of a random graph
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• The cover time of sparse random graphs
• The cover time of the giant component of a random graph
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• Sur Une Équation Fonctionnelle Et SES Applications: Une Extension Du Théorème De Kesten-Stigum Concernant Des Processus De Branchement
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The cutoff phenomenon in finite Markov chains.
• Mandelbrot Cascades and Related Topics
• The Cover Time of Random Regular Graphs
• Generalized PageRank on directed configuration networks
• Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk
• Optimal Transport

This page was built for publication: Random walk on sparse random digraphs