Monotonicity of random walks’ states on finite grids
Keywords:
random walks, resistance distance, gridsAbstract
In this paper two ways to order the nodes of a graph with respect to an arbitrary node are considered, both connected to random walks on the graph. The first one is the order according to probabilities of states of a random walk of fixed length started in that arbitrary node. The walks considered here are lazy walks – instead of making a step they are allowed to stay in the same node. A class of graphs, where such order the corresponds to the weak order by geodesic distances, was found. Square and toric n-dimensional grids are shown to be instances of this class. The second way of ordering is resistance distance to a fixed node. For another class of graphs, a pair of vertices with maximal resistance distance between them is established. Grids are again shown to be an example of graphs belonging to this class.
References
- 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.
Downloads
Additional Files
Published
Issue
Section
License
The authors who are published in this journal agree to the following:
- The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
- The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)
