Name
Abstract | ||
|---|---|---|
Let X be a lazy random walk on a graph G. If G is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle Z(n) shows. However, we establish that for Eulerian digraphs, the mixing time is O(mn), where m is the number of edges and n is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/16M1073376 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
random walk,mixing time,Eulerian digraph | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Random walk,Eulerian path,Hitting time,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
32 | 1 | 0895-4801 |
Citations | PageRank | References |
2 | 0.38 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucas Boczkowski | 1 | 2 | 0.38 |
| Yuval Peres | 2 | 523 | 53.68 |
| Perla Sousi | 3 | 33 | 2.44 |