×

zbMATH — the first resource for mathematics

Cutoff for lamplighter chains on fractals. (English) Zbl 1410.60070
Summary: We show that the total-variation mixing time of the lamplighter random walk on fractal graphs exhibit sharp cutoff when the underlying graph is transient (namely of spectral dimension greater than two). In contrast, we show that such cutoff can not occur for strongly recurrent underlying graphs (i.e. of spectral dimension less than two).

MSC:
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J35 Transition functions, generators and resolvents
28A80 Fractals
35K08 Heat kernel
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] M. T. Barlow, Random walks and heat kernels on graphs. London Mathematical Society Lecture Note Series, 438. Cambridge University Press, Cambridge, 2017. · Zbl 1365.05002
[2] M. T. Barlow and R. F. Bass, Random walks on graphical Sierpinski carpets. Random walks and discrete potential theory (Cortona, 1997), 26–55, Sympos. Math., XXXIX, Cambridge Univ. Press, Cambridge, 1999. · Zbl 0958.60045
[3] M. T. Barlow and R. F. Bass, Brownian motion and harmonic analysis on Sierpinski carpets. Canad. J. Math. 51 (1999), no. 4, 673–744. · Zbl 0945.60071
[4] M. T. Barlow and R. F. Bass, Stability of parabolic Harnack inequalities. Trans. Amer. Math. Soc. 356 (2003), no. 4, 1501–1533. · Zbl 1034.60070
[5] M. T. Barlow, T. Coulhon and T. Kumagai, Characterization of sub-Gaussian heat kernel estimates on strongly recurrent graphs. Comm. Pure Appl. Math. 58 (2005), no. 12, 1642–1677. · Zbl 1083.60060
[6] M. T. Barlow, A. Grigor’yan and T. Kumagai, On the equivalence of parabolic Harnack inequalities and heat kernel estimates. J. Math. Soc. Japan 64 (2012), no. 4, 1091–1146. · Zbl 1281.58016
[7] M. T. Barlow and M. Murugan, Stability of the elliptic Harnack inequality. Ann. Math. 187 (2018), no. 3, 777–823. · Zbl 1450.35131
[8] T. Coulhon and A. Grigor’yan, A. Random walks on graphs with regular volume growth. Geom. Funct. Anal. 8 (1998), no. 4, 656–701. · Zbl 0918.60053
[9] D. A. Croydon, Moduli of continuity of local times of random walks on graphs in terms of the resistance metric. Trans. London Math. Soc. 2 (2015), no. 1, 57–79. · Zbl 1327.05307
[10] A. Dembo, J. Ding, J. Miller and Y. Peres, Cut-off for lamplighter chains on tori: Dimension interpolation and phase transition. Preprint, available at arXiv:1312.4522. · Zbl 07030879
[11] S. Goel, R. Montenegro and P. Tetali, Mixing time bounds via the spectral profile. Electron. J. Probab. 11 (2006), no. 1, 1–26. · Zbl 1109.60061
[12] A. Grigor’yan and A. Telcs, Sub-Gaussian estimates of heat kernels on infinite graphs. Duke Math. J. 109 (2001), no. 3, 451–510. · Zbl 1010.35016
[13] A. Grigor’yan and A. Telcs, Harnack inequalities and sub-Gaussian estimates for random walks. Math. Ann. 324 (2002), no. 3, 521–556. · Zbl 1011.60021
[14] B. M. Hambly and T. Kumagai, Heat kernel estimates for symmetric random walks on a class of fractal graphs and stability under rough isometries. Proc. of Symposia in Pure Math. 72, Part 2, pp. 233–260, Amer. Math. Soc. 2004. · Zbl 1065.60041
[15] J. Kigami, Analysis on fractals. Cambridge Tracts in Mathematics, 143. Cambridge University Press, Cambridge, 2001. · Zbl 0998.28004
[16] T. Kumagai and C. Nakamura, Lamplighter random walks on fractals. J. Theor. Probab. 31 (2018), no. 1, 68–92. · Zbl 1395.60080
[17] D. A. Levin, Y. Peres and E. L. Wilmer, Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009. · Zbl 1160.60001
[18] J. Miller and Y. Peres, Uniformity of the uncovered set of random walk and cutoff for lamplighter chains. Ann. Probab. 40 (2012), no. 2, 535–577. · Zbl 1251.60058
[19] J. Miller and P. Sousi, Uniformity of the late points of random walk on \(Z^d_n\) for d \(\ge \)3. Probab. Theory Related Fields 167 (2017), no. 3-4, 1001–1056. · Zbl 1372.60066
[20] A. Nachmias and Y. Peres, Critical random graphs: diameter and mixing time. Ann. Probab. 36 (2008), no. 4, 1267–1286. · Zbl 1160.05053
[21] Y. Peres and D. Revelle, Mixing times for random walks on finite lamplighter groups. Electron. J. Probab. 9 (2004), no. 26, 825–845. · Zbl 1064.60095
[22] L. Saloff-Coste, Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996), 301-413, Lecture Notes in Math., 1665, Springer, Berlin, 1997. · Zbl 0885.60061
[23] A. Telcs, The art of random walks. Lecture Notes in Mathematics, 1885. · Zbl 1104.60003
[24] A. Telcs, The art of random walks. Lecture Notes in Mathematics, 1885. · Zbl 0885.60061
[25] A. Telcs, The art of random walks. Lecture Notes in Mathematics, 1885. · Zbl 1104.60003
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.