Comparing limit profiles of reversible Markov chains. (English) Zbl 07854746
Summary: We introduce a technique for comparing the limit profile behavior of two reversible, commuting Markov chains on the same space, that share the same stationary distribution. We apply this technique to prove that the limit profile of star transpositions at time \(t=n\log n+cn\) is equal to \(d_{\mathrm{T.V.}}(\mathrm{Poiss}(1+e^{-c}), \mathrm{Poiss}(1))\) by comparing to the limit profile of random transpositions, as studied in [29]. We also provide examples of important commuting Markov chains, whose limit profile behavior is unknown, which could give new directions for research.
MSC:
| 60C05 | Combinatorial probability |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
References:
| [1] | Dave Bayer and Persi Diaconis. Trailing the dovetail shuffle to its lair. Ann. Appl. Probab., 2(2):294-313, 1992. MathSciNet: MR1161056 · Zbl 0757.60003 |
| [2] | Megan Bernstein and Evita Nestoridi. Cutoff for random to random card shuffle. Ann. Probab., 47(5):3303-3320, 2019. MathSciNet: MR4021252 · Zbl 1448.60154 |
| [3] | Alexey Bufetov and Peter Nejjar. Cutoff profile of ASEP on a segment. Probab. Theory Related Fields, 183(1-2):229-253, 2022. MathSciNet: MR4421174 · Zbl 1490.60263 |
| [4] | Persi Diaconis. Applications of noncommutative Fourier analysis to probability problems. In École d’Été de Probabilités de Saint-Flour XV-XVII, 1985-87, volume 1362 of Lecture Notes in Math., pages 51-100. Springer, Berlin, 1988. MathSciNet: MR0983372 · Zbl 0662.60013 |
| [5] | Persi Diaconis. Group representations in probability and statistics, volume 11 of Institute of Mathematical Statistics Lecture Notes—Monograph Series. Institute of Mathematical Statistics, Hayward, CA, 1988. MathSciNet: MR0964069 · Zbl 0695.60012 |
| [6] | Persi Diaconis. Mathematical developments from the analysis of riffle shuffling. In Groups, combinatorics & geometry (Durham, 2001), pages 73-97. World Sci. Publ., River Edge, NJ, 2003. MathSciNet: MR1994961 · Zbl 1026.60005 |
| [7] | Persi Diaconis and Laurent Saloff-Coste. Comparison techniques for random walk on finite groups. Ann. Probab., 21(4):2131-2156, 1993. MathSciNet: MR1245303 · Zbl 0790.60011 |
| [8] | Persi Diaconis and Laurent Saloff-Coste. Comparison theorems for reversible Markov chains. Ann. Appl. Probab., 3(3):696-730, 1993. MathSciNet: MR1233621 · Zbl 0799.60058 |
| [9] | Persi Diaconis and Laurent Saloff-Coste. Walks on generating sets of abelian groups. Probab. Theory Related Fields, 105(3):393-421, 1996. MathSciNet: MR1425868 · Zbl 0847.60081 |
| [10] | Persi Diaconis and Laurent Saloff-Coste. Bounds for Kac’s master equation. Comm. Math. Phys., 209(3):729-755, 2000. MathSciNet: MR1743614 · Zbl 0953.60098 |
| [11] | Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete, 57(2):159-179, 1981. zbMATH: 0485.60006 MathSciNet: MR0626813 · Zbl 0485.60006 |
| [12] | Persi Diaconis and Mehrdad Shahshahani. Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Anal., 18(1):208-218, 1987. MathSciNet: MR0871832 · Zbl 0617.60009 |
| [13] | Alexandros Eskenazis and Evita Nestoridi. Cutoff for the Bernoulli-Laplace urn model with \(o(n)\) swaps. Ann. Inst. Henri Poincaré Probab. Stat., 56(4):2621-2639, 2020. MathSciNet: MR4164850 · Zbl 1478.60202 |
| [14] | Leopold Flatto, Andrew M. Odlyzko, and David B. Wales. Random shuffles and group representations. Ann. Probab., 13(1):154-178, 1985. MathSciNet: MR0770635 · Zbl 0564.60007 |
| [15] | Martin Hildebrand. Generating random elements in \(\operatorname{SL}_n( \mathbf{F}_q)\) by random transvections. J. Algebraic Combin., 1(2):133-150, 1992. MathSciNet: MR1226348 · Zbl 0766.60089 |
| [16] | Bob Hough and Yunjiang Jiang. Cut-off phenomenon in the uniform plane Kac walk. Ann. Probab., 45(4):2248-2308, 2017. MathSciNet: MR3693962 · Zbl 1401.60134 |
| [17] | Martin Kassabov. Kazhdan constants for \(\operatorname{SL}_n(\mathbb{Z})\). Internat. J. Algebra Comput., 15(5-6):971-995, 2005. MathSciNet: MR2197816 · Zbl 1097.22007 |
| [18] | Hubert Lacoin. The cutoff profile for the simple exclusion process on the circle. Ann. Probab., 44(5):3399-3430, 2016. MathSciNet: MR3551201 · Zbl 1410.37008 |
| [19] | David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. MathSciNet: MR2466937 · Zbl 1160.60001 |
| [20] | Eyal Lubetzky and Yuval Peres. Cutoff on all Ramanujan graphs. Geom. Funct. Anal., 26(4):1190-1216, 2016. MathSciNet: MR3558308 · Zbl 1351.05208 |
| [21] | Peter Matthews. A strong uniform time for random transpositions. J. Theoret. Probab., 1(4):411-423, 1988. MathSciNet: MR0958246 · Zbl 0716.60074 |
| [22] | Evita Nestoridi and Sam Olesker-Taylor. Limit profiles for reversible Markov chains. Probab. Theory Related Fields, 182(1-2):157-188, 2022. MathSciNet: MR4367947 · Zbl 1487.60010 |
| [23] | Natesh S. Pillai and Aaron Smith. On the mixing time of Kac’s walk and other high-dimensional Gibbs samplers with constraints. Ann. Probab., 46(4):2345-2399, 2018. MathSciNet: MR3813994 · Zbl 1430.60061 |
| [24] | Chuan Qin and Ben Morris. Improved bounds for the mixing time of the random-to-random shuffle. Electron. Commun. Probab., 22:Paper No. 22, 7, 2017. MathSciNet: MR3635695 · Zbl 1361.60061 |
| [25] | Jeffrey S. Rosenthal. Random rotations: characters and random walks on \(\operatorname{SO}(N)\). Ann. Probab., 22(1):398-423, 1994. MathSciNet: MR1258882 · Zbl 0799.60007 |
| [26] | Justin Salez. Cutoff for non-negatively curved Markov chains. Journal of the European Mathematical Society, to appear. |
| [27] | Laurent Saloff-Coste and Jessica Zúñiga. Refined estimates for some basic random walks on the symmetric and alternating groups. ALEA Lat. Am. J. Probab. Math. Stat., 4:359-392, 2008. MathSciNet: MR2461789 · Zbl 1171.60008 |
| [28] | Eliran Subag. A lower bound for the mixing time of the random-to-random insertions shuffle. Electron. J. Probab., 18:no. 20, 20, 2013. MathSciNet: MR3035748 · Zbl 1410.60072 |
| [29] | Lucas Teyssier. Limit profile for random transpositions. Ann. Probab., 48(5):2323-2343, 2020. MathSciNet: MR4152644 · Zbl 1468.60091 |
| [30] | Jay-Calvin Uyemura-Reyes. Random walks, semi-direct products and card shuffling. ProQuest LLC, Ann Arbor, MI, 2002, Thesis (Ph.D.)-Stanford University. MR-2703300. |
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.
