Suppose that $f \colon [0, 1] \to \mathbb{R}$ is a $1$-Lipschitz function.
Define the uniform norm $\|f\|\_\infty = \sup\_{x} |f(x)|$.


Given $\{U\_j\}\_{j=1}^\infty$ independent and identically distributed uniform random variables on the unit interval $[0, 1]$, I am curious to know about the behavior of the random variable  

$$
\Delta\_n(f) := \Big|\max\_{j \leq n} |f(U\_j)| - \|f\|\_\infty\Big| 
$$
I would roughly expect that $\Delta\_n \sim \frac{1}{n}$, with high probability simply because on average one of the $n$ samples $U\_1, \dots, U\_n$ should lie within $1/n$ of the maximum, and therefore, the error should be of this order. I am also interested to what degree this can be made uniform over Lipschitz functions $f$, i.e., by studying the maximal quantity $\sup\_{f \in \mathcal{F}} \Delta\_n(f)$ where $\mathcal{F}$ is a suitable family of Lipschitz functions (say with $f(0) = 0$). Is this question studied? If so, are there any references available?



Rate of convergence of sample maximum, $\Big|\max_{j \leq n} |f(U_j)| - \|f\|_\infty\Big|$
$\newcommand\De\Delta\newcommand{\Ga}{\Gamma}\newcommand\ga{\gamma}$Let $X\_j:=g(U\_j)$, where $g:=|f|$. Then the $X\_i$'s are i.i.d. random variables and $g$ is a $1$-Lipschitz function. We have
$$M:=\max\_{[0,1]}g=g(u)$$
for some $u\in[0,1]$.


For any real $h>0$,
\begin{align\*}
P(\De\_n(f)>h)&=P(M-\max\_1^n X\_j>h) \\ 
&=P(\max\_1^n X\_j<M-h) \\
&=P(X\_1<M-h)^n \\ 
&=P(g(U\_1)<g(u)-h)^n \\ 
&=P(g(u)-g(U\_1)>h)^n \\ 
&\le P(|U\_1-u|>h)^n \tag{1}\label{1} \\ 
&\le(1-h)^n\le e^{-nh};
\end{align\*}
the $\le$ inequality in \eqref{1} holds because $g$ is $1$-Lipschitz.


So, $\De\_n(f)$ is stochastically dominated by an exponentially distributed random variable with mean $1/n$, which confirms your expectation. In particular, $E\De\_n(f)\le1/n$.




---


Consider now
\begin{equation\*}
 \De\_n(F):=\sup\_{f\in F}\De\_n(f),
\end{equation\*}
where $F$ is the set of all $1$-Lipschitz functions on $[0,1]$. Let us show that
\begin{equation\*}
 E\De\_n(F)\sim\frac{\ln n}{2n} \tag{2}\label{2}
\end{equation\*}
and
\begin{equation\*}
 \De\_n(F)\Big/\frac{\ln n}{2n}\to1 \tag{3}\label{3}
\end{equation\*}
in probability (as $n\to\infty$).


Indeed, it is easy to see that
\begin{equation\*}
 \De\_n(F)=\frac12\,\max(2G\_1,G\_2,\dots,G\_n,2G\_{n+1})
 =\frac{M\_n}2+L\_n, \tag{4}\label{4}
\end{equation\*}
where
\begin{equation\*}
 M\_n:=\max(G\_1,G\_2,\dots,G\_n,G\_{n+1}),
\end{equation\*}
\begin{equation\*}
 0\le L\_n\le\frac12\,\max(G\_1,G\_{n+1}), \tag{5}\label{5}
\end{equation\*}
\begin{equation\*}
 G\_i:=U\_{n:i}-U\_{n:i-1}
\end{equation\*}
for $i=1,\dots,n+1$; $U\_{n:1}\le\dots\le U\_{n:n}$ are the order statistics for the $U\_j$'s; $U\_{n:0}:=0$; and $U\_{n:n+1}:=1$.


A result by Fisher 1929 (see e.g. [formula (1.7)](https://arxiv.org/abs/1909.06406v1)) is that for $x\in[0,1]$ we have
\begin{equation\*}\label{eq:fisher}
 P(M\_n>x)=\sum\_{j=1}^{n+1}(-1)^{j-1}\binom{n+1}j(1-jx)\_+^n, 
\end{equation\*}
where $u\_+:=\max(0,u)$. So,
\begin{equation\*}
 EM\_n=\int\_0^1dx\,P(M\_n>x)
 =\sum\_{j=1}^{n+1}(-1)^{j-1}\binom{n+1}j\int\_0^1dx\,(1-jx)\_+^n 
 =\frac{\psi(n+2)+\ga}{n+1}\sim\frac{\ln n}n, \tag{6}\label{6}
\end{equation\*}
where $\psi:=\Ga'/\Ga$ and $\ga=0.577\dots$ is Euler's gamma; these results for $EM\_n$ were also given at the end of Section 1 of the linked paper.


Writing $EM\_n^2=\int\_0^1dx\,2x\,P(M\_n>x)$, we similarly get
\begin{equation\*}
 Var\,M\_n\sim\frac{\pi^2}{6n^2}.
\end{equation\*}
So, by \eqref{6} and Chebyshev's inequality,
\begin{equation\*}
 M\_n\Big/\frac{\ln n}n\to1 \tag{7}\label{7}
\end{equation\*}
in probability.
In view of \eqref{5}, it is easy to see that $EL\_n=O(1/n)$ and hence $L\_n/\frac{\ln n}n\to0$ in probability.


Now \eqref{2} and \eqref{3} follow from \eqref{4}, \eqref{6}, and \eqref{7}. $\quad\Box$




---


From the first equality in \eqref{4} and formula (2.2) of the linked paper, one can get an exact expression for the cdf of $\De\_n(F)$: for all real $x\ge0$,
\begin{equation\*}
 P(2\De\_n(F)\le x)\\ 
 =\sum\_{k=0}^{n-1}(-1)^k\binom{n-1}k
 [(1-kx)\_+^n-2(1-(k+\tfrac12)x)\_+^n+(1-(k+1)x)\_+^n]. 
\end{equation\*}
This yields an exact expression for $E\De\_n(F)$:
\begin{equation\*}
 E\De\_n(F)=\frac1{2(n+1)}\Big(\psi(n)+\ga+\frac{2\sqrt{\pi}\,\Ga (n)}{\Ga(n+1/2)} -\frac1n\Big),
\end{equation\*}
which, in turn, again yields \eqref{2}.


