The concept of a "proliferating random walk" on a lattice is that at any time $t \in \Bbb N \cup 0$, there is some set consisting of at least one particle, each of which is on its own lattice point. When taking a time step, each particle also randomly decides whether to split into two particles, each of which moves to a different lattice point. If two particles would reach the same lattice point at some step, they coalesce back into one particle.

To be precise for the problem of interest, define for any real constant $0 \leq \rho \leq 1$ a $\rho$-proliferating walk in $d$ dimensions as a Markov process evolving in discrete integer time steps, with the following properties:

  • The state $S_t$ at any time $t$ is described by a finite subset of $\Bbb Z^d$.

  • The "evolution component" attributed to any point $x \in \Bbb Z^d$ is the set $$ e_{t+1}(x) = \left\{ \begin{array}{cl} \emptyset & x \not\in S_t \\ \left\{\begin{array}{l} r_2(x) \mbox{ with probability }\rho \\r_1(x) \mbox{ with probability }1-\rho \end{array}\right.& x \in S_t \end{array}\right. $$ where $r_1(x)$ is set containing a single point one lattice step from $x$ with all such sets chosen with equal probability, and $r_2(x)$ is set containing two points each one lattice step from $x$ with all such sets chosen with equal probability.

  • The state evolves as $$S_{t+1} = \bigcup_{x\in \Bbb R^d} e_{t+1}(x) = \bigcup_{x\in S_t} e_{t+1}(x) $$

  • The initial state is $S_0 = \{ 0^d \}$, that is, one particle at the origin.

Further, for some $d$ and $\rho$, define the probability $RV(d,\rho)$ of revisiting the origin as the probability that at some time $t>0$ the origin will be an element of $S_t$. I don't use the term "return to origin" because that ought to be reserved to mean that $S_t = S_0$. The walk can revisit the origin even if $S_t$ has many elements. If the $d$-dimensional random walk with proliferation $\rho$ revists the origin a.s, we say that $RV(d,\rho) = 1$.

For $\rho = 0$, the proliferating random walk is an ordinary symmetrical random walk, and will return to the origin with probability of Polya's random walk constant, roughly 34%. But for $\rho > 0$ the number of particles in $S_t$ tends to increase with $t$ (and this increase is rapid for $d>2$), so it is plausible that for sufficiently large $\rho$ the Markov process for $S_t$ revisits the origin almost surely, at least in $3$ dimensions.

It is easy to prove that $RV(d,\rho) \geq RV(d,0)$, and not much harder to show that if $\xi > \rho$ then $RV(d,\xi) \geq RV(d,\rho)$. I strongly suspect that $RV(3,1) = 1$, that is, the 3-D random walk with particle doubling at every time step revisits the origin a.s. -- but I can't prove that.

The generic question that arises is to characterise, for any given $d$, the range of $\rho$ such that $RV(d,\rho) < 1$. In particular:

Is $RV(3,1) = 1$, and if so, what can be said about the minimum value of $\rho$ such that $RV(3,\rho) = 1$?


1 Answer 1


Yes. The proliferating random walk will visit the origin infinitely often in any dimension for any $\rho>0$. In fact something stronger is true: rather than proliferating, suppose the random walk goes to the one of the two vertices that is closer to the origin in Euclidean distance. Then even this random walk visits the origin infinitely often.

To see this, consider the evolution of $D_n=\|X_n\|_2$, the square Euclidean distance of the position of this "selective random walk" from the origin after the $n$th step.

A calculation (averaging over the $\binom{2d}2$ possible combinations of pairs of neighbours of $X_n$) shows $\mathbb E(D_{n+1}|X_n)\le D_n+1-\rho \|X_n\|_1/d\le D_n+1-\rho \sqrt{D_n}/d$. In particular, once $D_n\ge d^2/\rho^2$, $\mathbb E D_{n+1}<D_n$. It follows that $\mathbb ED_n\le d^2/\rho^2$ for all $n$. It follows that the selective random walk returns to the origin infinitely often.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.