PreprintarXiv licencearXiv
Mixing time under monotone censoring
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(nlog n). More precisely, for every nonempty increasing set A⊆{0,1}n, with a=μ(A) and μ uniform on the cube, we prove tmix(P)≤ Ca nlog(en), where Ca 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 Ca=13a−1log(e/a), within a logarithmic factor of the conjectured a−1 dependence.
Related
- Monotone Mixing and Distribution Dynamics
- When are time-to-event models a waste of time? Bridging mixture cure models and positive-unlabeled learning for binary classification under right-censoring
- Direct Learning of Treatment-Benefit Rankings for Restricted Mean Survival Time in Randomized Trials with Censoring
- A Time-Varying Coefficient-Based Fixed-Time Neurodynamic Approach for Generalized Monotone Inclusion Problems and Its Applications
- Long-time and large-population limits of displacement monotone linear-quadratic Nash systems
BibTeX
@misc{chen2026mixing,
title = {{Mixing time under monotone censoring}},
author = {Yiming Chen and Yuval Peres},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.16515},
eprint = {2609.16515},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16515},
}
RIS
TY - UNPB
TI - Mixing time under monotone censoring
AU - Yiming Chen
AU - Yuval Peres
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2609.16515
UR - https://arxiv.org/abs/2609.16515
AB - 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(nlog n). More precisely, for every nonempty increasing set A⊆{0,1}^n, with a=μ(A) and μ uniform on the cube, we prove t_mix(P)≤ C_a nlog(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^−1log(e/a), within a logarithmic factor of the conjectured a^−1 dependence.
ER -