This article is cited in 2 papers

Theory of probability and Mathematical statistics

Monotonicity of random walks' states on finite grids

A. O. Zadorozhnuyk

EPAM Systems, 1 Akademika Kuprevica Street, 1 building, Minsk 220141, Belarus

Abstract: 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.

UDC: 519.217.2

Received: 12.01.2022
Revised: 13.01.2022
Accepted: 14.02.2022

DOI: 10.33581/2520-6508-2022-1-38-45

Bibliographic databases:

•