Stationary distribution and cover time of random walks on random digraphs

摘要

We study properties of a simple random walk on the random digraph D_(n,p) when np =d logn, d > 1.We prove that whp the value π_v of the stationary distributionat 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)→∞ with n, the stationary distribution is asymp totically uniform whp.Using this result we prove that, for d > 1, whp the cover timeof D_(n,p) is asymptotic to d log(d/(d-1))n logn. If d = d(n)→∞ with n, then the cover time is asymptotic to n logn.