Stationary distribution and cover time of random walks on random digraphs

Details Stationary distribution and cover time of random walks on random digraphs Stationary distribution and cover time of random walks on random digraphs

2011-03-22

arxiv.org/abs/1103.4317v1

Mathematics

Combinatorics

Scientific paper

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 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 d\log (d/(d-1))n\log n. If d=d(n) tends to infinity with n, then the cover time is asymptotic to n\log n.

Affiliated with

Also associated with

No associations

Rating

Stationary distribution and cover time of random walks on random digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stationary distribution and cover time of random walks on random digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stationary distribution and cover time of random walks on random digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-49420