vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2023-59-1-51-61vestifm-702Research ArticleМАТЕМАТИКАMATHEMATICSАналог теоремы Альдуса о времени перемешивания для групп комплексных отраженийAn analogue of Aldous’s theorem on mixing times of a random walk for complex reflection groupsЗадорожнюкА. О.ZadarazhniukH. A.

Задорожнюк Анна Олеговна – аспирант, ассистент кафедры высшей математики

пр. Независимости, 4, 220030, Минск

Hanna A. Zadarazhniuk – Postgraduate Student, As- sistant of the Department of Higher Mathematics

4, Nezavisimosti Ave., 220030, Minsk

a_zadorozhnuyk@mail.ruБелорусский государственный университетBelarusian State University2023030420235915161Copyright © Задорожнюк А.О., 20232023Задорожнюк А.О.Zadarazhniuk H.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/702

Исследуется время перемешивания случайных блужданий на минимальных графах Кэли групп комплексных отражений G(m,1,n). Ключевую роль при этом играет адаптация метода склеивания распределений, применявшегося ранее для симметрической группы. Сложность адаптации заключается в том, что с обобщением в случайном блуждании появляются две компоненты, к которым нужно применять склеивание, и эти компоненты влияют на обоюдное поведение. Для решения этой проблемы случайные блуждания разбиваются на несколько бло- ков, для каждого из которых даются отдельные оценки времени, необходимого для совпадения состояний. Доказаны оценки сверху и снизу на время перемешивания случайных блужданий на группах комплексных отражений, аналогичные оценкам Альдуса для симметрической группы.

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.

случайные блужданияграфы Кэлигруппы комплексных отраженийrandom walksCayley graphscomplex reflection groupsReferencesAldous, D. J. Random walks on finite groups and rapidly mixing Markov chains / D. J. Aldous // Séminaire de Probabilités XVII 1981/82. Lecture Notes in Mathematics / eds. J. Azéma, M. Yor. – Berlin, Heidelberg: Springer, 1983. – Vol. 986. – P. 243–297. https://doi.org/10.1007/BFb0068322Aldous 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/BFb0068322Levin, D. A. Markov Chains and Mixing Times / D. A. Levin, Y. Peres, E. L. Wilmer. – American Mathematical Society, 2009. – 371 p. https://doi.org/10.1090/mbk/058Levin D. A., Peres Y., Wilmer E. L. Markov Chains and Mixing Times. American Mathematical Society, 2009. 371 p. https://doi.org/10.1090/mbk/058Wilson, D. B. Mixing times of Lozenge tiling and card shuffling Markov chains / D. B. Wilson // Ann. Appl. Probability. – 2004. – Vol. 14, № 1. – P. 274–325. https://doi.org/10.1214/aoap/1075828054Wilson 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/1075828054Durret, R. Shuffling chromosomes / R. Durret // J. Theor. Probability – 2003. – Vol. 16, № 3. – P. 725–750. https://doi.org/10.1023/a:1025676617383Durret R. Shuffling chromosomes. Journal of Theoretical Probability, 2003, vol. 16, no. 3, pp. 725–750. https://doi.org/10.1023/a:1025676617383Jao, D. Expander graphs based on GRH with an application to elliptic curve cryptography / D. Jao, S. D. Miller, R. Venkatesan // J. Number Theory. – 2009. – Vol. 129, № 6. – P. 1491–1504. https://doi.org/10.1016/j.jnt.2008.11.006Jao 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.006Vaskouski, M. Resistance Distances in Cayley Graphs on Symmetric Groups / M. Vaskouski, A. Zadorozhnyuk // Discrete Appl. Math. – 2017. – Vol. 227. – P. 121–135. https://doi.org/10.1016/j.dam.2017.04.044Vaskouski 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Васьковский, М. М. Асимптотическое поведение резисторных расстояний в графах Кэли / М. М. Васьковский, А. О. Задорожнюк // Докл. Нац. акад. наук Беларуси. – 2018. – Т. 62, № 2. – С. 140–146. https://doi.org/10.29235/1561-8323-2018-62-2-140-146.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-146Sauerwald, T. Randomized Protocols for Information Dissemination / T. Sauerwald. – University of Padeborn, 2008. – 160 p.Sauerwald T. Randomized Protocols for Information Dissemination. University of Padeborn, 2008. 160 p.Васьковский, М. М. О случайных блужданиях на графах Кэли групп комплексных отражений / М. М. Васьковский // Журн. Белорус. гос. ун-та. Математика. Информатика. – 2021. – № 3. – C. 51–56. https://doi.org/10.33581/2520-6508-2021-3-51-56Vaskouski 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Кемени, Дж. Конечные цепи Маркова / Дж. Кемени, Дж. Снелл; пер. с англ. С. А. Молчанова, Н. Б. Левиной, Я. А. Когана; под ред. А. А. Юшкевича. – М.: Наука, 1970. – 272 с.Kemeny J. G., Snell J. L. Finite Markov Chains. New York, Van Nostrand Comp. Int., 1960.Broué, M., Introduction to Complex Reflection Groups and Their Braid Groups / M. Broué. – Springer, 2010. – 144 p. https://doi.org/10.1007/978-3-642-11175-4Broué M. Introduction to Complex Reflection Groups and Their Braid Groups. Springer, 2010. 144 p. https://doi.org/10.1007/978-3-642-11175-4

The authors declare that there are no conflicts of interest present.