Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 205 / 3 / d / Solution

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