—
tick 0
pursuer (random walk)
evader (random walk)
collision flash
The paper studies two independent simple random walks on an infinite unimodular random rooted graph and asks a simple question: how often do they meet at the same vertex? It proves a sharp dichotomy, extending earlier work of Hutchcroft & Peres (2015):
They apply this to graphs with genuinely unbounded degree: the Gilbert graph (connect random points within radius r — a.k.a. the random geometric graph), the Delaunay graph, the Gabriel graph, and the long-range percolation model. They then use these collision properties to characterize the stationary measures of the voter model on such graphs — recurrent collisions push a finite voter model toward consensus-like behavior, while transience opens the door to non-trivial (non-degenerate) stationary measures.
Honesty note on this demo. The paper's dichotomy is a statement about infinite graphs. Any finite connected graph is a finite-state Markov chain, so two independent walkers on it are technically guaranteed to collide again eventually — "collide only finitely often" isn't literally reproducible on a fixed finite board. This demo approximates the two regimes instead: Gilbert / Delaunay / Gabriel graphs here are drawn from bounded, moderate-degree geometric constructions (matching the paper's recurrent, lattice-like intuition) and stay a fixed size, so the pursuer and evader keep re-crossing paths — frequent, real collisions. "Heavy-tailed" mode runs a live, still-growing preferential-attachment graph (new nodes keep attaching to high-degree hubs, à la Barabási–Albert), which is a stand-in — not literally the paper's long-range percolation model — for the unbounded-degree regime: as it keeps growing, hubs keep opening fresh territory and the gap between collisions tends to keep growing, so in practice the pursuer can go a very long time — often the rest of the run — without ever finding the evader again, echoing the "finitely often" picture without claiming to prove it on a finite graph.
Nodes are sized and shaded by degree (bigger / brighter = more connections). In heavy-tailed mode you'll see a handful of huge hub nodes emerge — that's the heavy tail. In Gilbert / Delaunay / Gabriel mode, degrees stay in a narrow, bounded band.
Pursuer (red) and evader (blue) each independently take one step per tick to a uniformly random neighbor — a real simple random walk, simulated live, not scripted. A yellow ring flashes every time they land on the same node at the same tick, and the collision counter and the gap-chart update in real time.
Voter model mode colors every node with one of several opinions. Each tick a small random sample of nodes copies a neighbor's opinion (classic voter-model dynamics), and — as a nod to the collision↔coalescence duality the paper leans on for its voter-model application — a pursuer/evader collision forces the pursuer's node to instantly adopt the evader's opinion. Watch consensus (the "Consensus" stat, % of nodes on the majority color) race to ~100% on the bounded-degree graphs, while the growing heavy-tailed graph keeps injecting fresh random opinions on new nodes and resists ever fully converging.
Everything here — point placement, triangulation, preferential attachment, force layout, and the walk itself — is computed live in your browser on every load; nothing is pre-recorded.