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=\mu(A)$ and $\mu$ 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\'e 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.
Consider $n$ independent, non-negative, mean at most one random variables, $X_1,X_2,\ldots$. We show the following bound on the probability of their sum exceeding a threshold $t$: \[ \mathbb{P}\left[\sum_{i=1}^n X_i\ge t\right] \leq 1-\left(1-\frac{1}{t}\right)^n \text{ for all } t\ge 2n+1 \,. \] To prove this, we cons...
We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|\Gamma|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(\Gamma)\le k \quad\t...
We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017),...
Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\, \mathrm{d} x$ on $\mathbb{R}^d$, where $U$ is continuously differentiable and $m$-strongly convex with a globally $L$-Lipschitz gradient, $0<m\leq L<\infty$, and $\kappa=L/m$. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds...
We prove Breiman's conjecture under the first-moment assumption. Let $Y_1,Y_2,\ldots$ be iid nonnegative random variables with $\mathbb P\{Y_1>0\}>0$, normalized by their sum. If the resulting randomly weighted sum converges to a nondegenerate law for one fixed integrable, nonconstant mark distribution, then the tail o...
Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional...
Thanh Nguyen-Cung, B. T. Nguyen· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
