Limit profiles for reversible Markov chains. (English) Zbl 1487.60010
Summary: In a recent breakthrough, [L. Teyssier, Ann. Probab. 48, No. 5, 2323–2343 (2020; Zbl 1468.60091)] introduced a new method for approximating the distance from equilibrium of a random walk on a group. He used it to study the limit profile for the random transpositions card shuffle. His techniques were restricted to conjugacy-invariant random walks on groups; we derive similar approximation lemmas for random walks on homogeneous spaces and for general reversible Markov chains. We illustrate applications of these lemmas to some famous problems: the \(k\)-cycle shuffle, sharpening results of B. Hough [Probab. Theory Relat. Fields 165, No. 1–2, 447–482 (2016; Zbl 1339.60048)] and N. Berestycki et al. [Ann. Probab. 39, No. 5, 1815–1843 (2011; Zbl 1245.60006)], the Ehrenfest urn diffusion with many urns, sharpening results of T. Ceccherini-Silberstein et al. [J. Math. Sci., New York 141, No. 2, 1182–1229 (2007; Zbl 1173.43001); translation from Sovrem. Mat. Prilozh. 27, 95–140 (2005)], a Gibbs sampler, which is a fundamental tool in statistical physics, with Binomial prior and hypergeometric posterior, sharpening results of P. Diaconis et al. [Stat. Sci. 23, No. 2, 151–178 (2008; Zbl 1327.62058)].
MSC:
| 60B15 | Probability measures on groups or semigroups, Fourier transforms, factorization |
| 43A30 | Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups, etc. |
| 43A65 | Representations of groups, semigroups, etc. (aspects of abstract harmonic analysis) |
| 43A90 | Harmonic analysis and spherical functions |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |
| 62D05 | Sampling theory, sample surveys |
Keywords:
cutoff; limit profiles; random walk on groups; symmetric group; representation theory; Fourier transform; characters; Gelfand pairs; homogeneous spaces; spherical functions; eigenvalues and eigenfunctions of Markov chains; spectral representationsReferences:
| [1] | Aldous, D.: Random walks on finite groups and rapidly mixing Markov chains. In: Azéma J., Yor M. (eds.) Seminar on Probability, XVII, Lecture Notes in Math. vol. 986, pp. 243-297. Springer, Berlin (1983). doi:10.1007/BFb0068322 · Zbl 0514.60067 |
| [2] | Ben-Hamou, A.; Salez, J., Cutoff for nonbacktracking random walks on sparse random graphs, Ann. Probab., 45, 3, 1752-1770 (2017) · Zbl 1372.60101 · doi:10.1214/16-AOP1100 |
| [3] | Berestycki, N.; Schramm, O.; Zeitouni, O., Mixing times for random k-cycles and Coalescence-Fragmentation chains, Ann. Probab., 39, 5, 1815-1843 (2011) · Zbl 1245.60006 · doi:10.1214/10-AOP634 |
| [4] | Berestycki, N.; Sengül, B., Cutoff for conjugacy-invariant random walks on the permutation group, Probab. Theory Relat. Fields., 173, 3-4, 1197-1241 (2019) · Zbl 1411.60012 · doi:10.1007/s00440-018-0844-y |
| [5] | Ceccherini-Silberstein, T.; Scarabotti, F.; Tolli, F., Finite Gel’fand pairs and their applications to probability and statistics, J. Math. Sci., 141, 2, 1182-1229 (2007) · Zbl 1173.43001 · doi:10.1007/s10958-007-0041-5 |
| [6] | Ceccherini-Silberstein, T., Scarabotti, F., Tolli, F.: Harmonic analysis on finite groups. vol. 108, Cambridge University Press, Cambridge (2008). doi:10.1017/CBO9780511619823 · Zbl 1149.43001 |
| [7] | Diaconis, P.: Group representations in probability and statistics. Institute of Mathematical Statistics, vol. 11, Hayward, CA (1988) · Zbl 0695.60012 |
| [8] | Diaconis, P.; Graham, RL; Morrison, JA, Asymptotic analysis of a random walk on a hypercube with many dimensions, Random Struct. Algorithms, 1, 1, 51-72 (1990) · Zbl 0723.60085 · doi:10.1002/rsa.3240010105 |
| [9] | Diaconis, P.; Khare, K.; Saloff-Coste, L., Gibbs sampling exponential families and orthogonal polynomials, Stat. Sci., 23, 2, 151-178 (2008) · Zbl 1327.62058 · doi:10.1214/07-STS252 |
| [10] | Diaconis, P.; Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete., 57, 2, 159-179 (1981) · Zbl 0485.60006 · doi:10.1007/BF00535487 |
| [11] | Diaconis, P.; Shahshahani, M., Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal., 18, 1, 208-218 (1987) · Zbl 0617.60009 · doi:10.1137/0518016 |
| [12] | Ehrenfest, T.; Ehrenfest, P., Über Zwei Bekannte Einwäande Gegen das Boltzmannsche H-theorem, Physikalische Zeitschrift, 8, 311-314 (1907) · JFM 38.0931.01 |
| [13] | Hermon, J., Olesker-Taylor, S.: Cutoff for almost all random walks on Abelian groups (2021). arXiv:2102.02809 |
| [14] | Hough, R., The random k cycle walk on the symmetric group, Probab. Theory Relat. Fields., 165, 1-2, 447-482 (2016) · Zbl 1339.60048 · doi:10.1007/s00440-015-0636-6 |
| [15] | Koekoek, R., Swarttouw, R.F.: The Askey-Scheme of hypergeometric orthogonal polynomials and its q-analogue. Delft University of Technology, Delft (1998). Available at http://homepage.tudelft.nl/11r49/askey/ |
| [16] | Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. 2nd ed., American Mathematical Society, Providence (2017). doi:10.1090/mbk/107 · Zbl 1390.60001 |
| [17] | Lubetzky, E.; Peres, Y., Cutoff on all Ramanujan graphs, Geom. Funct. Anal., 26, 4, 1190-1216 (2016) · Zbl 1351.05208 · doi:10.1007/s00039-016-0382-7 |
| [18] | Nestoridi, E., Olesker-Taylor, S.: Limit profiles for reversible Markov chains (2020). arXiv: 2005.13437 |
| [19] | Salez, J.: Temps de Mélange des Chaînes de Markov (in French). Online Lecture Notes (2018). Available at www.ceremade.dauphine.fr/ salez/mixing.pdf |
| [20] | Teyssier, L., Limit profile for random transpositions, Ann. Probab., 48, 5, 2323-2343 (2020) · Zbl 1468.60091 · doi:10.1214/20-AOP1424 |
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.
