# Annihilating random walkers

Suppose there are several walkers moving randomly on $\mathbb{Z}^2$, each taking a $(\pm 1,\pm 1)$ step at each time unit. Whenever two walkers move to the same point, they annihilate one another. This deletion always occurs in pairs, so if $3$ walkers move to the same point, $2$ are deleted and $1$ remains, whereas if $4$ move to one point, all $4$ are deleted.

At each time step, a new walker is created at the origin if it is not occupied. If it is occupied, the new walker annihilates that origin occupier, and no new walker is created at that time step.

After $n=50$ steps, $10$ walkers remain. Green: newly created. Red: pair annihilation.

Q1. If the process is run from time $0$ to time $n$, and from then on no more new walkers are created at the origin but the simulation otherwise continues, how many walkers are expected to exist as $t \to \infty$?

I believe the answer is $0$, essentially because of Polya's recurrence theorem applied to pairs of walkers.

Q2. If the process is run forever, continuing to create new walkers at the origin if unoccupied, what is the expected number of remaining walkers as $t \to \infty$? How does this number grow (or shrink) with respect to $t$?

Here I have little intuition, and would appreciate an analysis.

• On the large scale, I would expect this process to act like a nonlinear reaction-diffusion equation $$\dfrac{\partial u}{\partial t} = a \Delta u - b u^2 + c \delta(x)$$ – Robert Israel Feb 5 '18 at 18:51
• This is kind of irrelevant, but, technically, there are two separate populations, introduced on odd and even generations, respectively. – Mateusz Kwaśnicki Feb 5 '18 at 19:24
• @MateuszKwaśnicki: I guess I could add in a "no-move" choice, which would then mix the populations. – Joseph O'Rourke Feb 5 '18 at 19:58
• @JosephO'Rourke: Yes, of course. Or simply throw in a new walker every other turn. – Mateusz Kwaśnicki Feb 5 '18 at 21:00
• For Q1, since after time $n$ the parity of the number of particles remains constant, and there is positive probability of odd parity, the answer can't be $0$. I believe that the answer is either 1 or 0 precisely depending on that (random) parity. – ofer zeitouni Feb 6 '18 at 15:02

With a "physicist approach", I would write down the following equation for $f(x,t)$ that should represent the "density" of walker around $x$ at time $t$: $$\partial_t f =\Delta f -\alpha f^2 +\delta_0$$ with $\partial_t f =\Delta f+\delta_0$ is the diffusion equation with source at $0$ and $\alpha f^2$ the collisions term which is the density of two walker on the same site with an "independent hypothesis". (3 walker collisions term are neglected)
One can then try to solve the equation which is by symetrie, rotational invariant $$\partial_tf=\frac{1}{r}\partial_rf+\partial_{rr}f-\alpha f^2+\delta_0$$ On $]0,\infty]$ the stationnary solution is $$\frac{4}{\alpha r^2}$$ One can then expect that $f\rightarrow \frac{4}{\alpha r}$ for $t\rightarrow \infty$. Because $$\int_1^\infty r(\frac{4}{\alpha r^2})=\infty$$ The number of walker should grow to $\infty$. I would also suspect that the limiting solution should be invariante with $r\rightarrow \lambda r$ and $\rightarrow \lambda^2 t$. In that case the number of walker should behave like $$N\sim a*\log(\sqrt{t})$$
(Remark that one should also be able to proved this last statement by grand deviation arguments as the probability that a walker goes to $\infty$.)
• Nice that you obtain the asymptotic behavior $N \sim a \log( \sqrt{t} )$. – Joseph O'Rourke Feb 5 '18 at 22:09