An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913351058063360 |
|---|---|
| author | Kumamoto, Shuma Kijima, Shuji Shirai, Tomoyuki |
| author_facet | Kumamoto, Shuma Kijima, Shuji Shirai, Tomoyuki |
| contents | It is a celebrated fact that a simple random walk on an infinite $k$-ary tree for $k \geq 2$ returns to the initial vertex at most finitely many times during infinitely many transitions; it is called transient. This work points out the fact that a simple random walk on an infinitely growing $k$-ary tree can return to the initial vertex infinitely many times, it is called recurrent, depending on the growing speed of the tree. Precisely, this paper is concerned with a simple specific model of a random walk on a growing graph (RWoGG), and shows a phase transition between the recurrence and transience of the random walk regarding the growing speed of the graph. To prove the phase transition, we develop a coupling argument, introducing the notion of less homesick as graph growing (LHaGG). We also show some other examples, including a random walk on $\{0,1\}^n$ with infinitely growing $n$, of the phase transition between the recurrence and transience. We remark that some graphs concerned in this paper have infinitely growing degrees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09102 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes Kumamoto, Shuma Kijima, Shuji Shirai, Tomoyuki Probability It is a celebrated fact that a simple random walk on an infinite $k$-ary tree for $k \geq 2$ returns to the initial vertex at most finitely many times during infinitely many transitions; it is called transient. This work points out the fact that a simple random walk on an infinitely growing $k$-ary tree can return to the initial vertex infinitely many times, it is called recurrent, depending on the growing speed of the tree. Precisely, this paper is concerned with a simple specific model of a random walk on a growing graph (RWoGG), and shows a phase transition between the recurrence and transience of the random walk regarding the growing speed of the graph. To prove the phase transition, we develop a coupling argument, introducing the notion of less homesick as graph growing (LHaGG). We also show some other examples, including a random walk on $\{0,1\}^n$ with infinitely growing $n$, of the phase transition between the recurrence and transience. We remark that some graphs concerned in this paper have infinitely growing degrees. |
| title | An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes |
| topic | Probability |
| url | https://arxiv.org/abs/2405.09102 |