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

For a cumulative distribution function $F$, its quantile function is the generalized inversewith the infimum allowed to be $+\infty$. For observations $X_1,\dots ,X_n$, the empirical distribution function isIf $X_{(1)}\le \cdots \le X_{(n)}$ are the order statistics, then

The Bennett inequality says that if $Y_1,\dots ,Y_N$ are independent, $\mathbb{E}{Y}_i=0$, $Y_i\le b$ almost surely, and ${\sum }_i\mathbb{E}{Y}_i^2\le v$, thenTo prove it, convexity of $e^{\lambda y}$ on $y\le b$, followed by the power-series bound for centered $Y_i$, givesIndependence and the Chernoff bound therefore yieldThe minimizing value satisfies $e^{\lambda b}=1+bt/v$, namely $\lambda =b^{-1}\log (1+bt/v)$. Substitution gives the stated exponent.

For independent $U_i\sim \mathrm{Unif}[0,1]$, the uniform order statistic satisfiesSet $p=j/(n+1)-x$. The event $U_{(j)}\le p$ means that at least $j$ sample points lie in $[0,p]$. If this occurs, some $j$-element subset consists entirely of such points. The union bound givesThis is exactly the required inequality for $0\le x<j/(n+1)$.