Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 210 / 1

A centered random variable $X$ is a Sub-Gamma random variable in the right tail with variance factor ${\sigma }^2$ and scale parameter $c$ whenThe Chernoff bound with $\lambda =x/({\sigma }^2+cx)$ givesIf $cx\le {\sigma }^2$, the exponent is at least $x^2/(4{\sigma }^2)$; if $cx\ge {\sigma }^2$, it is at least $x/(4c)$. Hence

Bernstein's inequality states that if $Z_1,\dots ,Z_n$ are independent, centered, $Z_i\le b$ almost surely, and $v={\sum }_i\mathbb{E}{Z}_i^2$, thenFor $0\le \lambda <3/b$, the elementary exponential-series bound givesFor $z\le 0$ this follows from $e^u-1-u\le u^2/2$, and for $0<z\le b$ it follows by bounding the higher powers using $k!\ge 23^{k-2}$. Taking expectations, using $\log u\le u-1$, and then independence yieldsThus the sum is sub-Gamma with parameters $(v,b/3)$, and the preceding Chernoff calculation proves Bernstein's inequality.

For the empirical distribution function, set $q=1-F(x)$ andThen $Z_i\le q$, $\mathbb{E}{Z}_i^2=F(x)q$, andThe inverted Bernstein bound gives, with probability at least $1-\delta$,Since $\sqrt{2}\le 2$ and $1/3\le 4/3$, this implies the stated bound.