Name
Abstract | ||
|---|---|---|
We study properties of a simple random walk on the random digraph D"n","p when np=dlogn, d1. We prove that whp the value @p"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 d1, whp the cover time of D"n","p is asymptotic to dlog(d/(d-1))nlogn. If d=d(n)-~ with n, then the cover time is asymptotic to nlogn. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jctb.2011.11.001 | Journal of Combinatorial Theory |
Keywords | DocType | Volume |
simple random walk,expected number,random digraph,stationary distribution,cover time,asymptotically uniform whp,vertex v,random walk,discrete mathematics | Journal | 102 |
Issue | ISSN | Citations |
2 | 0095-8956 | 7 |
PageRank | References | Authors |
0.56 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 857 | 91.88 |
| Alan M. Frieze | 2 | 4837 | 787.00 |