2
$\begingroup$

Suppose that $X,X_1,X_2,X_3\dots$ is a sequence of $\mathbb{P}$-i.i.d. random variables supported in the interval $[0,1]$. Let $F$ be the cumulative distribution of $X$, i.e. $F(x):=\mathbb{P}[X \le x]$ and let $\hat{F}_n$ be the empirical cumulative distribution given $X_1,\dots,X_n$, i.e, $\hat{F}_n(x) := \frac{1}{n}\sum_{k=1}^n\mathbb{I}\{X_k \le x\}$.

It is known from the DKW inequality that for every $n \in \mathbb{N}$ and $\varepsilon >0$ \begin{equation*} \mathbb{P}[\|\hat{F}_n-F\|_{L^\infty([0,1])} \ge \varepsilon ] =\mathbb{P}\bigg[\sup_{x \in [0,1]}|\hat{F}_n(x)-F(x)| \ge \varepsilon\bigg] \le 2 \exp(-2\cdot\varepsilon^2 \cdot n) \;. \end{equation*}

I'm wondering if can strengthen the DKW inequality if we replace the norm of $L^\infty([0,1])$ with the norm of $L^1([0,1])$. Specifically, can we find a universal constant $\alpha < 2$ and other two universal constants $c_1>0, c_2>0$ such that, regardless what is the distribution $F$ of $X$, it holds that for each $n \in \mathbb{N}$ and $\varepsilon >0$: \begin{equation*} \mathbb{P}[\|\hat{F}_n-F\|_{L^1([0,1])} \ge \varepsilon ] =\mathbb{P}\bigg[\int_0^1|\hat{F}_n(x)-F(x)| \mathrm{d}x \ge \varepsilon\bigg] \le c_1 \exp(-c_2\cdot\varepsilon^\alpha \cdot n) \;? \end{equation*}

I value even something not exactly like this but similar in spirit. Any pointer to the literature is very welcome.

$\endgroup$

1 Answer 1

2
$\begingroup$

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_n$ 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.