Sensitivity of mixing times in Eulerian digraphs. (English) Zbl 1390.05219
Summary: 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 \(\mathbb{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.
MSC:
| 05C81 | Random walks on graphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C45 | Eulerian and Hamiltonian graphs |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
References:
| [1] | D. Aldous and J. Fill, {\it Reversible Markov Chains and Random Walks on Graphs}, Unfinished monograph, recompiled 2014, (2002). |
| [2] | O. Angel, Y. Peres, and D. B. Wilson, {\it Card shuffling and Diophantine approximation}, Ann. Appl. Probab., 18 (2008), pp. 1215-1231. · Zbl 1142.60046 |
| [3] | G. Barnes and U. Feige, {\it Short random walks on graphs}, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 728-737. · Zbl 1310.05188 |
| [4] | P. G. Doyle and J. Steiner, {\it Commute Time Geometry of Ergodic Markov Chains}, , 2011. |
| [5] | E. Giné, G. R. Grimmett, and L. Saloff-Coste, {\it Lectures on Probability Theory and Statistics}, Lecture Notes in Math., P. Bernard, ed., 1665 Springer-Verlag, Berlin, 1997. |
| [6] | S. Goel, R. Montenegro, and P. Tetali, {\it Mixing time bounds via the spectral profile}, Electron. J. Probab., 11 (2006), pp. 1-26. · Zbl 1109.60061 |
| [7] | J. D. Kahn, N. Linial, N. Nisan, and M. E. Saks, {\it On the cover time of random walks on graphs}, J. Theoret. Probab., 2 (1989), pp. 121-128. · Zbl 0681.60064 |
| [8] | L. Kuipers and H. Niederreiter, {\it Uniform Distribution of Sequences}, Pure and Appl. Math., Wiley, New York, 1974. · Zbl 0281.10001 |
| [9] | G. F. Lawler and V. Limic, {\it Random Walk: A Modern Introduction}, Cambridge Stud. Adv. Math. 123, Cambridge University Press, Cambridge, UK, 2010. · Zbl 1210.60002 |
| [10] | D. A. Levin, Y. Peres, and E. L. Wilmer, {\it Markov Chains and Mixing Times}, AMS, Providence, RI, 2009. · Zbl 1160.60001 |
| [11] | R. Lyons and S. Oveis Gharan, {\it Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding}, , 2012. · Zbl 1419.05132 |
| [12] | R. Montenegro and P. Tetali, {\it Mathematical aspects of mixing times in Markov chains}, Found. Trends Theor. Comput. Sci., 1 (2006). · Zbl 1193.68138 |
| [13] | Y. Peres and P. Sousi, {\it Mixing times are hitting times of large sets}, J. Theoret. Probab., 28 (2015), pp. 488-519. · Zbl 1323.60094 |
| [14] | V. V. Petrov, {\it Sums of Independent Random Variables}, Ergeb. Math. Grenzgeb. 82, Springer, Berlin, 1975. · Zbl 0322.60042 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
