×

Cutoff for random lifts of weighted graphs. (English) Zbl 1486.05284

The way random walks converge to equilibrium on a graph is closely related to essential geometrical properties of the latter (such as the typical distance between vertices, its diameter, its expansion, the presence of traps or bottlenecks, etc.), giving an important motivation for studying mixing times.
A class of graphs where random walks mix fast and where cutoff is expected are the expander graphs.
A natural way of combining the “product of a base space” and the “expanding sparse graph” perspectives for cutoff is to consider random walks on random \(n\)-lifts of a fixed graph \(G\).
Here, the author establishes the cutoff phenomenon for the random walk on random \(n\)-lifts of finite weighted graphs, even when the random walk on the base graph \(G\) of the lift is not reversible. The mixing time is w.h.p. \(t_{\mathrm{mix}} = h^{-1}\log n \), where \(h\) is a constant associated to \(G\), namely the entropy of its universal cover. Moreover, this mixing time is the smallest possible among all \(n\)-lifts of \(G\). In the particular case where the base graph is a vertex with \( d/2\) loops, \(d\) even, the author finds a cutoff for a \(d\)-regular random graph, as did E. Lubetzky and A. Sly [Duke Math. J. 153, No. 3, 475–510 (2010; Zbl 1202.60012)] (with a slightly different distribution on \(d\)-regular graphs, but the mixing time is the same).
The paper contains useful materials of interdisciplinary nature. Special focus on researchers working on random walks.

MSC:

05C81 Random walks on graphs
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
05C05 Trees
05C22 Signed and weighted graphs
05C48 Expander graphs

Citations:

Zbl 1202.60012
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] ADDARIO-BERRY, L. and GRIFFITHS, S. (2010). The spectrum of random lifts. arXiv eprints. Available at arXiv:1012.4097.
[2] ALDOUS, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. In Seminar on Probability, XVII. Lecture Notes in Math. 986 243-297. Springer, Berlin. · Zbl 0514.60067 · doi:10.1007/BFb0068322
[3] ALDOUS, D. and DIACONIS, P. (1986). Shuffling cards and stopping times. Amer. Math. Monthly 93 333-348. · Zbl 0603.60006 · doi:10.2307/2323590
[4] ALON, N. and MILMAN, V. D. (1984). Eigenvalues, expanders and superconcentrators. · Zbl 0641.68102
[5] AMIT, A. and LINIAL, N. (2006). Random lifts of graphs: Edge expansion. Combin. Probab. Comput. 15 317-332. · Zbl 1095.05034 · doi:10.1017/S0963548305007273
[6] AMIT, A., LINIAL, N. and MATOUŠEK, J. (2002). Random lifts of graphs: Independence and chromatic number. Random Structures Algorithms 20 1-22. · Zbl 0993.05071 · doi:10.1002/rsa.10003
[7] AMIT, A., LINIAL, N., MATOUŠEK, J. and ROZENMAN, E. (2001). Random lifts of graphs. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001) 883-894. SIAM, Philadelphia, PA. · Zbl 0986.05090
[8] AVENA, L., GÜLDAŞ, H., VAN DER HOFSTAD, R. and DEN HOLLANDER, F. (2019). Random walks on dynamic configuration models: A trichotomy. Stochastic Process. Appl. 129 3360-3375. · Zbl 1422.60162 · doi:10.1016/j.spa.2018.09.010
[9] BEN-HAMOU, A., LUBETZKY, E. and PERES, Y. (2018). Comparing mixing times on sparse random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms 1734-1740. SIAM, Philadelphia, PA. · Zbl 1403.05133 · doi:10.1137/1.9781611975031.113
[10] BEN-HAMOU, A. and SALEZ, J. (2017). Cutoff for nonbacktracking random walks on sparse random graphs. Ann. Probab. 45 1752-1770. · Zbl 1372.60101 · doi:10.1214/16-AOP1100
[11] BERESTYCKI, N., LUBETZKY, E., PERES, Y. and SLY, A. (2018). Random walks on the random graph. Ann. Probab. 46 456-490. · Zbl 1393.60077 · doi:10.1214/17-AOP1189
[12] BORDENAVE, C. (2020). A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Ann. Sci. Éc. Norm. Supér. (4) 53 1393-1439. · doi:10.24033/asens.245
[13] BORDENAVE, C. and COLLINS, B. (2019). Eigenvalues of random lifts and polynomials of random permutation matrices. Ann. of Math. (2) 190 811-875. · Zbl 1446.60004 · doi:10.4007/annals.2019.190.3.3
[14] BORDENAVE, C. and LACOIN, H. (1999). Cutoff at the entropic time for random walks on covered expander graphs. arXiv e-prints. Available at arXiv:1812.06769.
[15] CAPUTO, P. and QUATTROPANI, M. (2019). Mixing time of PageRank surfers on sparse random digraphs. arXiv E-prints. Available at arXiv:1905.04993.
[16] CHUNG, K. L. (1960). Markov Chains with Stationary Transition Probabilities. Die Grundlehren der Mathematischen Wissenschaften, Band 104. Springer, Berlin-Göttingen-Heidelberg. · Zbl 0092.34304
[17] Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159-179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[18] DRIER, Y. and LINIAL, N. (2006). Minors in lifts of graphs. Random Structures Algorithms 29 208-225. · Zbl 1226.05235 · doi:10.1002/rsa.20100
[19] FRIEDMAN, J. (2003). Relative expanders or weakly relatively Ramanujan graphs. Duke Math. J. 118 19-35. · Zbl 1035.05058 · doi:10.1215/S0012-7094-03-11812-8
[20] GAUDILLIÈRE, A. and LANDIM, C. (2014). A Dirichlet principle for non reversible Markov chains and some recurrence theorems. Probab. Theory Related Fields 158 55-89. · Zbl 1295.60087 · doi:10.1007/s00440-012-0477-5
[21] GILCH, L. A. (2008). Rate of escape of random walks on regular languages and free products by amalgamation of finite groups. In Fifth Colloquium on Mathematics and Computer Science. Discrete Math. Theor. Comput. Sci. Proc., AI 405-420. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1355.68156
[22] GILCH, L. A. (2016). Asymptotic entropy of random walks on regular languages over a finite alphabet. Electron. J. Probab. 21 Paper No. 8, 42. · Zbl 1338.60124 · doi:10.1214/16-EJP4180
[23] HERMON, J. and THOMAS, S. (2018). Cutoff for mixing times on random Abelian Cayley graphs. arXiv e-prints. Available at arXiv:1810.05130.
[24] Hoory, S., Linial, N. and Wigderson, A. (2006). Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43 439-561. · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8
[25] LALLEY, S. P. (2001). Random walks on regular languages and algebraic systems of generating functions. In Algebraic Methods in Statistics and Probability (Notre Dame, IN, 2000). Contemp. Math. 287 201-230. Amer. Math. Soc., Providence, RI. · Zbl 1016.60050 · doi:10.1090/conm/287/04787
[26] LINIAL, N. and ROZENMAN, E. (2005). Random lifts of graphs: Perfect matchings. Combinatorica 25 407-424. · Zbl 1091.05063 · doi:10.1007/s00493-005-0024-8
[27] LUBETZKY, E. and PERES, Y. (2016). Cutoff on all Ramanujan graphs. Geom. Funct. Anal. 26 1190-1216. · Zbl 1351.05208 · doi:10.1007/s00039-016-0382-7
[28] LUBETZKY, E. and SLY, A. (2010). Cutoff phenomena for random walks on random regular graphs. Duke Math. J. 153 475-510. · Zbl 1202.60012 · doi:10.1215/00127094-2010-029
[29] LUBETZKY, E., SUDAKOV, B. and VU, V. (2011). Spectra of lifted Ramanujan graphs. Adv. Math. 227 1612-1645. · Zbl 1222.05168 · doi:10.1016/j.aim.2011.03.016
[30] LYONS, R. (1990). Random walks and percolation on trees. Ann. Probab. 18 931-958. · Zbl 0714.60089
[31] LYONS, T. (1983). A simple criterion for transience of a reversible Markov chain. Ann. Probab. 11 393-402. · Zbl 0509.60067
[32] Montenegro, R. and Tetali, P. (2006). Mathematical aspects of mixing times in Markov chains. Found. Trends Theor. Comput. Sci. 1 x+121. · Zbl 1193.68138 · doi:10.1561/0400000003
[33] NAGNIBEDA, T. (1999). Green functions on trees with finitely many cone types. Stockholm Sweeden, and A M S-t.
[34] NAGNIBEDA, T. and WOESS, W. (2002). Random walks on trees with finitely many cone types. J. Theoret. Probab. 15 383-422. · Zbl 1008.60061 · doi:10.1023/A:1014810827031
[35] SAWYER, S. and STEGER, T. (1987). The rate of escape for anisotropic random walks in a tree. Probab. Theory Related Fields 76 207-230. · Zbl 0608.60064 · doi:10.1007/BF00319984
[36] SOUSI, P. and THOMAS, S. (2020). Cutoff for random walk on dynamical Erdős-Rényi graph. Ann. Inst. Henri Poincaré Probab. Stat. 56 2745-2773. · Zbl 1465.05168 · doi:10.1214/20-AIHP1057
[37] TAKACS, C. (1997). Random walk on periodic trees. Electron. J. Probab. 2 1-16. · Zbl 0888.60060 · doi:10.1214/EJP.v2-15
[38] WOESS, W. (1985). Random walks and periodic continued fractions. Adv. in Appl. Probab. 17 67-84 · Zbl 0554.60069 · doi:10.2307/1427053
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.