Аналог теоремы Альдуса о времени перемешивания для групп комплексных отражений
https://doi.org/10.29235/1561-2430-2023-59-1-51-61
Аннотация
Исследуется время перемешивания случайных блужданий на минимальных графах Кэли групп комплексных отражений G(m,1,n). Ключевую роль при этом играет адаптация метода склеивания распределений, применявшегося ранее для симметрической группы. Сложность адаптации заключается в том, что с обобщением в случайном блуждании появляются две компоненты, к которым нужно применять склеивание, и эти компоненты влияют на обоюдное поведение. Для решения этой проблемы случайные блуждания разбиваются на несколько бло- ков, для каждого из которых даются отдельные оценки времени, необходимого для совпадения состояний. Доказаны оценки сверху и снизу на время перемешивания случайных блужданий на группах комплексных отражений, аналогичные оценкам Альдуса для симметрической группы.
Об авторе
А. О. Задорожнюк
Белорусский государственный университет
Беларусь
Беларусь
Задорожнюк Анна Олеговна – аспирант, ассистент кафедры высшей математики
пр. Независимости, 4, 220030, Минск
Список литературы
1. Aldous, 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/BFb0068322
2. Levin, 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/058
3. Wilson, 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/1075828054
4. Durret, R. Shuffling chromosomes / R. Durret // J. Theor. Probability – 2003. – Vol. 16, № 3. – P. 725–750. https://doi.org/10.1023/a:1025676617383
5. Jao, 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.006
6. Vaskouski, 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.044
7. Васьковский, М. М. Асимптотическое поведение резисторных расстояний в графах Кэли / М. М. Васьковский, А. О. Задорожнюк // Докл. Нац. акад. наук Беларуси. – 2018. – Т. 62, № 2. – С. 140–146. https://doi.org/10.29235/1561-8323-2018-62-2-140-146.
8. Sauerwald, T. Randomized Protocols for Information Dissemination / T. Sauerwald. – University of Padeborn, 2008. – 160 p.
9. Васьковский, М. М. О случайных блужданиях на графах Кэли групп комплексных отражений / М. М. Васьковский // Журн. Белорус. гос. ун-та. Математика. Информатика. – 2021. – № 3. – C. 51–56. https://doi.org/10.33581/2520-6508-2021-3-51-56
10. Кемени, Дж. Конечные цепи Маркова / Дж. Кемени, Дж. Снелл; пер. с англ. С. А. Молчанова, Н. Б. Левиной, Я. А. Когана; под ред. А. А. Юшкевича. – М.: Наука, 1970. – 272 с.
11. 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-4
Рецензия
Просмотров: 311
Послать статью по эл. почте 