An analogue of Aldous’s theorem on mixing times of a random walk for complex reflection groups
https://doi.org/10.29235/1561-2430-2023-59-1-51-61
Abstract
The subject of this paper is the mixing time of random walks on minimal Cayley graphs of complex reflection groups G(m,1,n). The key role in estimating it is played by the coupling of distributions, which has been used before for the same task on symmetric groups. The difficulty with its adaptation for the current case is that there are now two components in a walk, which are to be coupled, and they influence each other’s behaviour. To solve this problem, random walks are split into several blocks for each of which the time needed for their states to match is estimated separately. The result is upper and lower bounds on mixing times of random walks on complex reflection groups, analogous to those obtained by Aldous for a symmetric group.
About the Author
H. A. Zadarazhniuk
Belarusian State University
Belarus
Belarus
Hanna A. Zadarazhniuk – Postgraduate Student, As- sistant of the Department of Higher Mathematics
4, Nezavisimosti Ave., 220030, Minsk
References
1. Aldous D. Random walks on finite groups and rapidly mixing markov chains. Azéma J., Yor M. (eds). Séminaire de Probabilités XVII 1981/82. Lecture Notes in Mathematics, vol 986. Springer, Berlin, Heidelberg, pp. 243–297. https://doi.org/10.1007/BFb0068322
2. Levin D. A., Peres Y., Wilmer E. L. Markov Chains and Mixing Times. American Mathematical Society, 2009. 371 p. https://doi.org/10.1090/mbk/058
3. Wilson D. B. Mixing times of Lozenge tiling and card shuffling Markov chains. Annals of Applied Probability, 2004, vol. 14, no. 1, pp. 274–32. https://doi.org/10.1214/aoap/1075828054
4. Durret R. Shuffling chromosomes. Journal of Theoretical Probability, 2003, vol. 16, no. 3, pp. 725–750. https://doi.org/10.1023/a:1025676617383
5. Jao D., Miller. S. D., Venkatesan R. Expander graphs based on GRH with an application to elliptic curve cryptography. Journal of Number Theory, 2009, vol. 129, no. 6, pp. 1491–1504. https://doi.org/10.1016/j.jnt.2008.11.006
6. Vaskouski M., Zadorozhnyuk A. Resistance Distances in Cayley Graphs on Symmetric Groups. Discrete Applied Mathematics, 2017, vol. 227, pp. 121–135. https://doi.org/10.1016/j.dam.2017.04.044
7. Vaskouski M. M., Zadorozhnyuk A. O. Asymptotic behavior of resistance distances in Cayley graphs. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2018, vol. 62, no. 2, pp. 140–146 (in Russian). https://doi.org/10.29235/1561-8323-2018-62-2-140-146
8. Sauerwald T. Randomized Protocols for Information Dissemination. University of Padeborn, 2008. 160 p.
9. Vaskouski M. Random walks on Cayley graphs of complex reflection groups. Zhurnal Belorusskogo gosudarstvennogo universiteta. Matematika. Informatika = Journal of the Belarusian State University. Mathematics and Informatics, 2021, no. 3, pp. 51–56 (in Russian). https://doi.org/10.33581/2520-6508-2021-3-51-56
10. Kemeny J. G., Snell J. L. Finite Markov Chains. New York, Van Nostrand Comp. Int., 1960.
11. Broué M. Introduction to Complex Reflection Groups and Their Braid Groups. Springer, 2010. 144 p. https://doi.org/10.1007/978-3-642-11175-4
Review
Views: 321
Email this article 