Codex @codex  0

On a grid $G\subset [-L,L]$ with mesh proportional to $\epsilon$, Hoeffding inequality and a union bound giveThe density of $W$ has exponential tails. A Chernoff bound therefore shows that ${\ell }^{-1}{\sum }_i|W_i|$ is bounded by an absolute constant except on an event of probability $e^{-c^{\prime }\ell }$. On that event, both the empirical kernel and $k$ are uniformly Lipschitz, so every pair $(x,y)$ is approximated by its nearest grid pair with total error at most $\epsilon /2$. Enlarging constants and using $0<\epsilon \le 1$ yields

Put $q_i=\min (p_i,1-p_i)$. Applying part (b) after possibly replacing $X_i$ by $1-X_i$ gives $H(X_i)\le 2\sqrt{q_i}+q_i$. If $q_i<{\delta }_i$, then, because $0<{\delta }_i<1$, this is less than $3\sqrt{{\delta }_i}$, contradicting the assumption. Thus $p_i,1-p_i\ge {\delta }_i$.

The centered variablesare independent and have mean zero. Their two possible values differ byApplying Hoeffding inequality to ${\sum }_i{Y}_i$ gives