Monotonicity of random walks’ states on finite grids
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 he...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Belarusian |
| Published: |
Belarusian State University
2022-04-01
|
| Series: | Журнал Белорусского государственного университета: Математика, информатика |
| Subjects: | |
| Online Access: | https://journals.bsu.by/index.php/mathematics/article/view/4506 |
| _version_ | 1818546890520657920 |
|---|---|
| author | Anna O. Zadorozhnuyk |
| author_facet | Anna O. Zadorozhnuyk |
| author_sort | Anna O. Zadorozhnuyk |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T07:59:17Z |
| format | Article |
| id | doaj.art-51603093ef67405fad09ec0522e3a34a |
| institution | Directory Open Access Journal |
| issn | 2520-6508 2617-3956 |
| language | Belarusian |
| last_indexed | 2024-12-12T07:59:17Z |
| publishDate | 2022-04-01 |
| publisher | Belarusian State University |
| record_format | Article |
| series | Журнал Белорусского государственного университета: Математика, информатика |
| spelling | doaj.art-51603093ef67405fad09ec0522e3a34a2022-12-22T00:32:12ZbelBelarusian State UniversityЖурнал Белорусского государственного университета: Математика, информатика2520-65082617-39562022-04-011384510.33581/2520-6508-2022-1-38-454506Monotonicity of random walks’ states on finite gridsAnna O. Zadorozhnuyk0EPAM Systems, 1 Akademika Kupreviča Street, 1 building, Minsk 220141, BelarusIn 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.https://journals.bsu.by/index.php/mathematics/article/view/4506random walksresistance distancegrids |
| spellingShingle | Anna O. Zadorozhnuyk Monotonicity of random walks’ states on finite grids Журнал Белорусского государственного университета: Математика, информатика random walks resistance distance grids |
| title | Monotonicity of random walks’ states on finite grids |
| title_full | Monotonicity of random walks’ states on finite grids |
| title_fullStr | Monotonicity of random walks’ states on finite grids |
| title_full_unstemmed | Monotonicity of random walks’ states on finite grids |
| title_short | Monotonicity of random walks’ states on finite grids |
| title_sort | monotonicity of random walks states on finite grids |
| topic | random walks resistance distance grids |
| url | https://journals.bsu.by/index.php/mathematics/article/view/4506 |
| work_keys_str_mv | AT annaozadorozhnuyk monotonicityofrandomwalksstatesonfinitegrids |