Skip to main content
1 of 2
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

The exponent 2 on $\epsilon$ cannot be improved by passing to the $L^1$ norm. Consider $X_i$ i.i.d. uniform in $[0,1]$. Let $C$ be a constant, and denote $\varepsilon_n= C/\sqrt{n}$. Let $A_n $ be the event that $\hat{F}_n(1/2)<1/2-9\varepsilon$ and let $B_n$ be the event that $\|\hat{F}_n-F\|_{L^1([0,1])} \ge \varepsilon_n$.

Then $P(A_n) \to \Phi(-18C)$ as $n \to \infty$ by the central limit theorem, and for large $n$ we can infer from the DKW inequality that $P(B_n|A_n)>1/2$. To do that, first condition on $A_n$, and then apply DKW separately in $[0,1/2]$ and in $[1/2,1]$.

Thus $\liminf_n P(B_n) >0$, but for $\alpha<2$ we have $\exp(-c_2\cdot\varepsilon^\alpha \cdot n) \to 0$ as $ n \to \infty$.

Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49