Stationary distribution and cover time of random walks on random digraphs

DOI10.1016/J.JCTB.2011.11.001MaRDI QIDQ412164zbMATH OpenOpenAlexWikidataFDO

Authors Colin Cooper, Alan Frieze

Publication date 4 May 2012

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

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

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)

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.

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

Cites work

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

Cited in

(18)

• Random walks on some basic classes of digraphs
• Discrepancy inequalities for directed graphs
• On the cover time of dense graphs
• On the cover time of the emerging giant
• Diameter and stationary distribution of random \(r\)-out digraphs
• Cover and hitting times of hyperbolic random graphs
• Component structure of the vacant set induced by a random walk on a random graph
• A probabilistic proof of Cooper \& Frieze's ``First Visit Time Lemma
• Extreme values of the stationary distribution of random walks on directed graphs
• Testing uniformity of stationary distribution
• Rankings in directed configuration models with heavy tailed in-degrees
• The Cover Time of Random Digraphs
• On the Last New Vertex Visited by a Random Walk in a Directed 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.
• Spectrum of Markov generators on sparse random graphs
• Stationary distribution and cover time of sparse directed configuration models
• Random walk on sparse random digraphs

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)