Paperlane

no. 3 · Tuesday 27 October 2026

Mixing time under monotone censoring

Yiming Chen and Yuval Peres

math.PR · v3 · 23 pp

Abstract

We prove the conjecture of Ding and Mossel~\cite{DM}: the lazy random walk on the discrete cube, censored to any increasing set of fixed positive density, mixes in time $O(n\log n)$. More precisely, for every nonempty increasing set $A\subseteq\{0,1\}^n$, with $a=μ(A)$ and $μ$ uniform on the cube, we prove $$ t_{\mathrm{mix}}(P)\le C_a n\log(en), $$ where $C_a$ depends only on $a$. The proof uses hypercontractivity on the ambient cube to strengthen the Poincaré inequality on coordinate sections. An optimal stopping time occupation inequality for increasing sets converts the resulting local bound into a uniform bound on hitting times of large sets. An appendix by Y.~Peres improves the density dependence to $C_a=13a^{-1}\log(e/a)$, within a logarithmic factor of the conjectured $a^{-1}$ dependence.

comments
23 pages
fields
Probability
pdf ↗ page arXiv:2609.16515 ↗