Mutually avoiding competing random walks

Definitions and mathematical statement

The source considers two nearest-neighbor walks $X^{(1)},X^{(2)}$ on ${\mathbb{Z}}^d$, using a common clock. Each chooses uniformly among neighboring vertices not previously visited by the other walk. In a synchronous discrete-time interpretation, if $R_n^{(i)}=\{X_k^{(i)}:0\leq k\leq n\}$, the admissible next sites for walk $i$ would be \[ A_n^{(i)}=\{y:|y-X_n^{(i)}|_1=1\}\setminus R_n^{(j)},\qquad j\ne i, \] with a uniform choice when this set is nonempty. This makes one possible timing convention explicit; the excerpt does not fully define it.

Define finite-region trapping by \[ \mathcal T_i=\{\#\{X_n^{(i)}:n\geq0\}<\infty\}. \] On ${\mathbb{Z}}^d$, this is equivalent to the range being bounded in Euclidean distance. A walk can have a finite range without ever having no legal move, so trapping must not be replaced by immediate immobilization.

The proposed dimensional dichotomy is \[ d=2:\quad\Pr(\mathcal T_1\cup\mathcal T_2)=1; \qquad d\geq3:\quad\Pr(\mathcal T_1^c\cap\mathcal T_2^c)=1. \] The first display reads "one walk" as at least one; whether exactly one is intended is not specified. No claim is supplied for $d=1$.

The initial positions, simultaneous versus sequential updates, conditional coupling of choices, treatment of an empty admissible set, and simultaneous visits to the same previously unvisited vertex are absent. These conventions determine the probability law and must be recovered before the almost-sure assertion is fully specified. A common clock does not mean that each walk avoids its own past: only the other walk's visited set is excluded.

Short English statement

Two walks avoid vertices already visited by the other. The conjecture says at least one remains in a finite region in two dimensions, while both have infinite ranges in higher dimensions. Initial conditions and update rules are incomplete.

Sources

• Local UnsolvedMath registry, permanent ID 10000074, source code catalogue entry; Itai Benjamini; proposed year 2012; updated 2026-08-06.
• Benjamini, Euclidean vs. Graph Metric, Section 7.1, two-walk problem, PDF page 9: https://www.wisdom.weizmann.ac.il/~itai/erd100.pdf#page=9. Supplied archive: https://arquivo.pt/noFrame/replay/20201231041538id_/http://www.wisdom.weizmann.ac.il/~itai/erd100.pdf. Registry access date 2026-07-29; text extraction checked against rendered PDF, as reported by provenance. Item retained after deduplication and source-side review; bounded audit found no complete resolution. Current status and release reuse terms require review.
• The supplied summary labels this a competing/avoiding-walk question without an additional exact reference or verified resolution.