An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes

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.