Geodesic
Monotonicity of random walks' states on finite grids
Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2022), pp. 38-45 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: random walks; resistance distance; grids. 
@article{BGUMI_2022_1_a4,
     author = {A. O. Zadorozhnuyk},
     title = {Monotonicity of random walks' states on finite grids},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {38--45},
     year = {2022},
     volume = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2022_1_a4/}
}
TY  - JOUR
AU  - A. O. Zadorozhnuyk
TI  - Monotonicity of random walks' states on finite grids
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2022
SP  - 38
EP  - 45
VL  - 1
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2022_1_a4/
LA  - ru
ID  - BGUMI_2022_1_a4
ER  - 
%0 Journal Article
%A A. O. Zadorozhnuyk
%T Monotonicity of random walks' states on finite grids
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2022
%P 38-45
%V 1
%U http://geodesic.mathdoc.fr/item/BGUMI_2022_1_a4/
%G ru
%F BGUMI_2022_1_a4
A. O. Zadorozhnuyk. Monotonicity of random walks' states on finite grids. Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2022), pp. 38-45. http://geodesic.mathdoc.fr/item/BGUMI_2022_1_a4/

[1] U. von-Luxburg, A. Radl, M. Hein, “Hitting and commute times in large random neighborhood graphs”, Journal of Machine Learning Research, 15:1 (2014), 1751–1798 | MR | Zbl

[2] T. Sauerwald, Randomized protocols for information dissemination, dissertation, University of Padeborn, Padeborn, 2008, 146 pp.

[3] M. M. Vaskovskii, A. O. Zadorozhnyuk, “Asimptoticheskoe povedenie rezistornykh rasstoyanii v grafakh Keli”, Doklady Natsionalnoi akademii nauk Belarusi, 62:2 (2018), 140–146 | DOI | MR

[4] M. Vaskouski, A. Zadorozhnyuk, “Resistance distances in Cayley graphs on symmetric groups”, Discrete Applied Mathematics, 227 (2017), 121–135 | DOI | MR | Zbl

[5] M. Bernstein, Likelihood orders for some random walks on the symmetric group, 2014, 34 pp., arXiv: 1306.5008v2 | MR | Zbl

[6] G. White, The weak Bruhat order for random walks on Coxeter groups, 2016, 9 pp., arXiv: 1611.04098v1

[7] R. B. Bapat, I. Gutman, W. Xiao, “A simple method for computing resistance distance”, Zeitschrift fur Naturforschung A, 58:9–10 (2003), 494–498 | DOI

[8] Q. Li, S. Li, L. Zhang, “Two-point resistances in the generalized phenylenes”, Journal of Mathematical Chemistry, 58:9 (2020), 1846–1873 | DOI | MR | Zbl

[9] M. S. Sardar, X-F. Pan, S-A. Xu, “Computation of resistance distance and Kirchhoff index of the two classes of silicate networks”, Applied Mathematics and Computation, 381 (2020), 125283 | DOI | MR | Zbl

[10] B. Bollobás, G. Brightwell, “Random walks and electrical resistances in products of graphs”, Discrete Applied Mathematics, 73:1 (1997), 69–79 | DOI | MR | Zbl