Monotonicity of draw probabilities under random vertex deletion
Fix an integer $d \ge 2$ and $p \in [0,1]$, and delete each vertex of the nearest-neighbour graph on $\mathbb{Z}^d$ independently with probability $p$. On the resulting graph, known to both players, they play Trap: a token starts at the origin, and the players alternately move it along an edge to an undeleted vertex that has not been visited before; a player with no legal move loses. If the origin is deleted, the first player is declared the winner. The board is a draw if neither player has a strategy that forces a win against every strategy of the opponent, and $D_d(p)$ is the probability of a draw, not conditioned on the origin surviving or lying in an infinite cluster. Trap on $\mathbb{Z}^d$ itself is a draw, so $D_d(0) = 1$, while $D_d(1) = 0$, and $D_d(p) = 0$ whenever $1 - p$ is below the critical probability for site percolation. When the two parity classes of a bipartite lattice are deleted with different probabilities, the probability that a given player wins is monotone in each of them; Basu, Holroyd, Martin and Wästlund remark that there is apparently no obvious monotonicity argument for the probability of a draw.
Problem. Is $D_d(p_2) \le D_d(p_1)$ for every $d \ge 2$ and all $0 \le p_1 \le p_2 \le 1$?
Source: Basu, Holroyd, Martin and Wästlund (2016), final list of open problems, item (ii), whether the probability of a draw is monotone in p; stated as nonincreasing by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, combinatorial games, site percolation
References
@article{basu2016,
author = {Basu, Riddhipratim and Holroyd, Alexander E. and Martin, James B. and W{\"a}stlund, Johan},
title = {Trapping games on random boards},
journal = {Ann. Appl. Probab.},
volume = {26},
number = {6},
year = {2016},
pages = {3727--3753},
doi = {10.1214/16-AAP1190},
eprint = {1505.07485},
archivePrefix = {arXiv},
}
@misc{aim-trap-draw-probability-monotonicity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Monotonicity of draw probabilities under random vertex deletion}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/575-trap-draw-probability-monotonicity.md},
note = {Entry 575 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00310, "Monotonicity of draw probabilities under random vertex deletion", clopen.solutions.