The Phase Shifting Coalescing-Branching Random Walk

Abstract

The Coalescing-Branching random (CoBra) walk is shown to exhibit a phase transition on an infinite \(n\)-ary homogenous tree, denoted \(T_n\), as the branching factor \(k\) is varied. The CoBra walk on \(T_n\) does not infect the root infinitely often for \(k = O(\sqrt{n})\). The CoBra walk on \(T_n\) has a positive probability of infecting the root infinitely often for \(k = \Omega(\sqrt{n})\). We provide leading lemmas about the \(\varepsilon\)-biased walk and inverse-degree biased walks which can help find the regions of recurrence for the CoBra walk on other infinite graphs. Further exposition on two general bounds of the 2-CoBra walk cover time of general finite graphs is provided. Miscellaneous results about the expected infections of a given CoBra particle and a few results about the branching random walk are also proven. Additionally, we provide CoBra walk simulation code on \(T_n\) and \(\mathbb{Z}^d\). We finally conjecture the 2-CoBra walk on the integer lattice \(\mathbb{Z}^d\) is recurrent for any dimension \(d\).