Монотонность вероятностей состояний случайного блуждания на конечных решетках
Аннотация
Рассматриваются два способа упорядочить вершины графа относительно некоторой его фиксированной вершины, связанных со случайными блужданиями на нем. Первый способ – порядок вершин в соответствии с вероятностью того, что случайное блуждание фиксированной длины закончится в каждой из них. Исследуемое в этой части блуждание является «ленивым», т. е. вместо очередного шага может оставаться на месте. Выделен класс графов, для которых такой порядок совпадает со слабым порядком по геодезическим расстояниям до соответствующих вершин. Приведены примеры представителей данного класса – n-мерные решетки. Второй способ упорядочивания – резисторные расстояния до выбранной вершины. Для класса графов установлена пара вершин, между которыми достигается максимальное по всему графу резисторное расстояние. Приведены примеры представителей этого класса, включая n-мерные решетки.
Литература
- von Luxburg U, Radl A, Hein M. Hitting and commute times in large random neighborhood graphs. Journal of Machine Learning Research. 2014;15(1):1751–1798.
- Sauerwald T. Randomized protocols for information dissemination [dissertation]. Padeborn: University of Padeborn; 2008. 146 p.
- Vaskouski MM, Zadorozhnyuk AO. Asymptotic behavior of resistance distances in Cayley graphs. Doklady of the National Academy of Sciences of Belarus. 2018;62(2):140–146. Russian. DOI: 10.29235/1561-8323-2018-62-2-140-146.
- Vaskouski M, Zadorozhnyuk A. Resistance distances in Cayley graphs on symmetric groups. Discrete Applied Mathematics. 2017;227:121–135. DOI: 10.1016/j.dam.2017.04.044.
- Bernstein M. Likelihood orders for some random walks on the symmetric group. arXiv:1306.5008v2 [Preprint]. 2014 [cited 2021 December 20]: [34 p.]. Available from: https://arxiv.org/abs/1306.5008v2.
- White G. The weak Bruhat order for random walks on Coxeter groups. arXiv:1611.04098v1 [Preprint]. 2016 [cited 2021 December 20]: [9 p.]. Available from: https://arxiv.org/abs/1611.04098v1.
- Bapat RB, Gutman I, Xiao W. A simple method for computing resistance distance. Zeitschrift für Naturforschung A. 2003;58(9–10):494–498. DOI: 10.1515/zna-2003-9-1003.
- Li Q, Li S, Zhang L. Two-point resistances in the generalized phenylenes. Journal of Mathematical Chemistry. 2020;58(9):1846–1873. DOI: 10.1007/s10910-020-01152-z.
- Sardar MS, Pan X-F, Xu S-A. Computation of resistance distance and Kirchhoff index of the two classes of silicate networks. Applied Mathematics and Computation. 2020;381:125283. DOI: 10.1016/j.amc.2020.125283.
- Bollobás B, Brightwell G. Random walks and electrical resistances in products of graphs. Discrete Applied Mathematics. 1997;73(1):69–79. DOI: 10.1016/S0166-218X(96)00002-9.
Copyright (c) 2022 Журнал Белорусского государственного университета. Математика. Информатика
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Авторы, публикующиеся в данном журнале, соглашаются со следующим:
- Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).