Stationary distribution and cover time of random walks on random digraphs

DOI10.1016/J.JCTB.2011.11.001zbMATH Open1239.05167arXiv1103.4317OpenAlexW2158978530WikidataQ57401445 ScholiaQ57401445MaRDI QIDQ412164FDOQ412164

Authors: Colin Cooper, Alan Frieze 

Publication date: 4 May 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We study properties of a simple random walk on the random digraph D_{n,p} when np={dlog n},; d>1. We prove that whp the stationary probability pi_v of a vertex v is asymptotic to deg^-(v)/m where deg^-(v) is the in-degree of v and m=n(n-1)p is the expected number of edges of D_{n,p}. If d=d(n) tends to infinity with n, the stationary distribution is asymptotically uniform whp. Using this result we prove that, for d>1, whp the cover time of D_{n,p} is asymptotic to dlog (d/(d-1))nlog n. If d=d(n) tends to infinity with n, then the cover time is asymptotic to nlog n.

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

Recommendations

• The Cover Time of Random Digraphs
• Stationary distribution and cover time of sparse directed configuration models
• Diameter and stationary distribution of random \(r\)-out digraphs
• The cover time of sparse random graphs
• Cover time of a random graph with given degree sequence

zbMATH Keywords

random walkcover timerandom digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• Concentration of multivariate polynomials and its applications
• The cover time of the giant component of a random graph
• The Cover Time of Random Regular Graphs
• The cover time of random geometric graphs
• The cover time of sparse random graphs
• Corrigendum: The cover time of the giant component of a random graph, Random Structures and Algorithms 32 (2008), 401-439
• An algorithm for finding hamilton cycles in random directed graphs
• The cover time of the preferential attachment graph

Cited In (18)

• On the cover time of dense graphs
• Random walks on some basic classes of digraphs
• Rankings in directed configuration models with heavy tailed in-degrees
• Discrepancy inequalities for directed graphs
• Spectrum of Markov generators on sparse random graphs
• Extreme values of the stationary distribution of random walks on directed graphs
• Random walk on sparse random digraphs
• Stationary distribution and cover time of sparse directed configuration models
• On the cover time of the emerging giant
• Testing uniformity of stationary distribution
• The Cover Time of Random Digraphs
• Cover and hitting times of hyperbolic random graphs
• Diameter and stationary distribution of random \(r\)-out digraphs
• On the Last New Vertex Visited by a Random Walk in a Directed Graph
• Component structure of the vacant set induced by a random walk on a random graph
• Cover time of a random graph with a degree sequence. II: Allowing vertices of degree two.
• The largest strongly connected component in the cyclical pedigree model of Wakeley et al.
• A probabilistic proof of Cooper \& Frieze's ``First Visit Time Lemma

This page was built for publication: Stationary distribution and cover time of random walks on random digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412164)