2026-07-25T22:07:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19895 2024-05-31T08:33:44Z ddc:004 open_access

An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes Kumamoto, Shuma Kijima, Shuji Shirai, Tomoyuki Random walk dynamic graph recurrent transient It is a celebrated fact that a simple random walk on an infinite k-ary tree for k ≥ 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}ⁿ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuma Kumamoto and Shuji Kijima and Tomoyuki Shirai 2024 Is Part Of LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2024.17 urn:nbn:de:0030-drops-198955 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.17 eng https://creativecommons.org/licenses/by/4.0/legalcode