Skip to main content
2 of 3
added 339 characters in body
Bob
  • 123
  • 1
  • 7

DKW inequality for $L^1$-norm

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])} > \varepsilon ] =\mathbb{P}\bigg[\sup_{x \in [0,1]}|\hat{F}_n(x)-F(x)| > \varepsilon\bigg] \le 2 \exp(-2\cdot\varepsilon^2 \cdot n) \;, \end{equation*}

that can be rewritten as, for all $n \in \mathbb{N}$ and $\delta \in (0,1)$: \begin{equation*} \mathbb{P}\Bigg[\|\hat{F}_n-F\|_{L^\infty([0,1])} > \sqrt{\frac{1}{2n} \log\Big(\frac{2}{\delta}\Big)}\Bigg] \le \delta \;. \end{equation*}

I'm wondering if can strengthen this last form of the DKW inequality by replacing the norm of $L^\infty([0,1])$ with the norm of $L^1([0,1])$. Specifically, can we find a universal constant $\alpha > 1/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 $\delta \in (0,1)$: \begin{align*} &\mathbb{P}\Bigg[\|\hat{F}_n-F\|_{L^1([0,1])} > \bigg(\frac{c_1}{n}\log\Big(\frac{c_2}{\delta}\Big) \bigg)^\alpha \Bigg] \\ &=\mathbb{P}\Bigg[\int_0^1|\hat{F}_n(x)-F(x)| \mathrm{d}x > \bigg(\frac{c_1}{n}\log\Big(\frac{c_2}{\delta}\Big) \bigg)^\alpha\Bigg] \le \delta \;? \end{align*}

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

Bob
  • 123
  • 1
  • 7