{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:46:33Z","timestamp":1787319993668,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/16m1073376","type":"journal-article","created":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T15:44:30Z","timestamp":1521128670000},"page":"624-655","source":"Crossref","is-referenced-by-count":12,"title":["Sensitivity of Mixing Times in Eulerian Digraphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Lucas","family":"Boczkowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Peres","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Perla","family":"Sousi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,15]]},"reference":[{"key":"atypb1","unstructured":"D. Aldous and J. Fill,\n                      Reversible Markov Chains and Random Walks on Graphs\n                      , Unfinished monograph, recompiled 2014,http:\/\/www.stat.berkeley.edu\/ aldous\/RWG\/book.html(2002)."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1214\/07-AAP484"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"G. Barnes and U. Feige,\n                      Short random walks on graphs\n                      , in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 728-737.","DOI":"10.1145\/167088.167275"},{"key":"atypb4","unstructured":"P. G. Doyle and J. Steiner,\n                      Commute Time Geometry of Ergodic Markov Chains\n                      ,arXiv:1107.2612, 2011."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"E. Gine\u0301, G. R. Grimmett, and L. Saloff-Coste,\n                      Lectures on Probability Theory and Statistics\n                      , Lecture Notes in Math., P. Bernard, ed., 1665 Springer-Verlag, Berlin, 1997.","DOI":"10.1007\/BFb0092617"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v11-300"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048274"},{"key":"atypb8","unstructured":"L. Kuipers and H. Niederreiter,\n                      Uniform Distribution of Sequences\n                      , Pure and Appl. Math., Wiley, New York, 1974."},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"G. F. Lawler and V. Limic,\n                      Random Walk: A Modern Introduction\n                      , Cambridge Stud. Adv. Math. 123, Cambridge University Press, Cambridge, UK, 2010.","DOI":"10.1017\/CBO9780511750854"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"D. A. Levin, Y. Peres, and E. L. Wilmer,\n                      Markov Chains and Mixing Times\n                      , AMS, Providence, RI, 2009.","DOI":"10.1090\/mbk\/058"},{"key":"atypb11","unstructured":"R. Lyons and S. Oveis Gharan,\n                      Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding\n                      ,arXiv:1211.0589, 2012."},{"key":"atypb12","first-page":"1","author":"Montenegro R.","year":"2006","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-013-0497-9"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"V. V. Petrov,\n                      Sums of Independent Random Variables\n                      , Ergeb. Math. Grenzgeb. 82, Springer, Berlin, 1975.","DOI":"10.1515\/9783112573006"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1073376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:15Z","timestamp":1787316855000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1073376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1073376"],"URL":"https:\/\/doi.org\/10.1137\/16m1073376","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}