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

A symmetric function $k:{\mathcal{X}}^2\to \mathbb{R}$ is a positive-definite kernel when ${\sum }_{i,j}{a}_i{a}_{j}k(x_i,x_j)\ge 0$ for every finite set of points and real coefficients. A Reproducing-kernel Hilbert space $\mathcal{H}$ is a Hilbert space of functions whose evaluation maps are continuous. Its reproducing kernel satisfies $k(x,\cdot )\in \mathcal{H}$ and $f(x)=⟨f,k(x,\cdot ){⟩}_{\mathcal{H}}$.

Let $U$ be uniform on $[0,2\pi ]$, and independently let $W$ have densityThe supplied Fourier transform identity, after the change of Fourier convention, givesAlso ${\mathbb{E}}_U[\cos (a+U)\cos (b+U)]=\frac{1}{2}\cos (a-b)$. Thereforeso one may take $c=1$.

For any $x_1,\dots ,x_N$ and $a_1,\dots ,a_N$, part (b) and linearity of expectation giveSymmetry is immediate, so $k$ is a positive-definite kernel.

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