Монотонность вероятностей состояний случайного блуждания на конечных решетках

  • Анна Олеговна Задорожнюк ЭПАМ Системз, ул. Академика Купревича, 1, корп. 1, 220141, г. Минск, Беларусь

Аннотация

Рассматриваются два способа упорядочить вершины графа относительно некоторой его фиксированной вершины, связанных со случайными блужданиями на нем. Первый способ – порядок вершин в соответствии с вероятностью того, что случайное блуждание фиксированной длины закончится в каждой из них. Исследуемое в этой части блуждание является «ленивым», т. е. вместо очередного шага может оставаться на месте. Выделен класс графов, для которых такой порядок совпадает со слабым порядком по геодезическим расстояниям до соответствующих вершин. Приведены примеры представителей данного класса – n-мерные решетки. Второй способ упорядочивания – резисторные расстояния до выбранной вершины. Для класса графов установлена пара вершин, между которыми достигается максимальное по всему графу резисторное расстояние. Приведены примеры представителей этого класса, включая n-мерные решетки.

Биография автора

Анна Олеговна Задорожнюк, ЭПАМ Системз, ул. Академика Купревича, 1, корп. 1, 220141, г. Минск, Беларусь

системный аналитик

Литература

  1. 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.
  2. Sauerwald T. Randomized protocols for information dissemination [dissertation]. Padeborn: University of Padeborn; 2008. 146 p.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
Опубликован
2022-04-01
Ключевые слова: случайные блуждания, резисторное расстояние, решетки
Поддерживающие организации Автор выражает благодарность заведующему кафедрой высшей математики БГУ М. М. Васьковскому за постановку задачи и участие в обсуждении, а также рецензенту за выявление существенных недостатков статьи.
Как цитировать
Задорожнюк, А. О. (2022). Монотонность вероятностей состояний случайного блуждания на конечных решетках. Журнал Белорусского государственного университета. Математика. Информатика, 1, 38-45. https://doi.org/10.33581/2520-6508-2022-1-38-45
Раздел
Теория вероятностей и математическая статистика