file.pdf (380 kB)

Download file# 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 log n , d>1.

We prove that whp the value π_{v} of the stationary distribution at 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 asymptotically uniform whp.

Using this result we prove that, for d>1, whp the cover time of D_{n,p} is asymptotic to d log(d/(d − 1))n log n . If d=d(n)→∞ with *n *, then the cover time is asymptotic to n log n