Return to Answer

added 26 characters in body

Source Link

edited Sep 14, 2023 at 14:42

5.2k
11
33

Thank you for your question. It motivated me to go through that paper. While I don't have a direct answer, I broke the paper down. The difficult details are non-omitable.. you have to find them in the paper.

Dvoretzky-Kiefer-Wolfowitz inequality is really about bounding the $\infty$-norm (sup-norm) of the Kolmogorov distribution $D_{n} := sup_{x\in R} |\hat{F}_{n}(x) - F(x)|$, where $F$ is the cdf and $\hat{F}_{n}$ is the empirical distribution function) of a single variate distribution.

To my surprise, Kolmogorov distribution is distribution-free, meaning that it does not depend on the underlying cdf! And this is actually not difficult to see - Hints:

Any random variable $X$ with continuous cdf $F$ satisfies that $F(X)$ is a $Unif_{[0,1]}$!
Replace $x$ with $F^{-1}(t)$ and $x \in \mathbb{R}$ with $t \in [0,1]$ in the definition $D_{n}$. (This argument should also work for other $L_{p}$-norms (up to a Jacobian of $F$), but I still can't find a version of DKL inequality for them.)

Therefore, in this paper, the author first assumed that $F$ is the cdf of the uniform disribution on [0,1]. Then the bounding problem becomes very explicit. And that's why it is about the Kolmogorov-Smirnoff distribution. It is very natural to inspect this due to the reduction above.

Main Steps

We follow the notations in the paper. $D_{n}$ is easily transformed to $D_{n}^{-}$, which the paper will focus. The main theorem (DKW with sharp bound) is

Theorem 1: $P(D_{n}^{-} > \lambda) \leq exp(-2 \lambda^{2})$, under some very mild conditions.

The key idea is to compare $D_{n}^{-}$ with some quantities $f_{\lambda}(s)$ derived from Brownian bridge.

More precisely, we have

(2.3) $P(D_{n}^{-} > \lambda) = \sum_{0 \leq j \leq n - \lambda \sqrt{n}} p_{\lambda,n}(j)$
(2.4) $exp(-2\lambda^{2}) = \int_{0}^{1} f_{\lambda}(s) ds$
(Prop. 1) compares $p_{\lambda,n}(j) and f_{\lambda}(s)$

Finally, in the last 5 pages, the author broke things down to two cases and proved them separately by hard estimation.

$n \geq 39$ and $\lambda \leq \sqrt(n)/2$
$n \leq 38$ or $\lambda > \sqrt(n)/2$

To my surprise, Kolmogorov distribution is distribution-free, meaning that it does not depend on the underlying cdf! And this is actually not difficult to see - Hints:

Any random variable $X$ with continuous cdf $F$ satisfies that $F(X)$ is a $Unif_{[0,1]}$!
Replace $x$ with $F^{-1}(t)$ and $x \in \mathbb{R}$ with $t \in [0,1]$ in the definition $D_{n}$. (This argument should also work for other $L_{p}$-norms, but I still can't find a version of DKL inequality for them.)

Main Steps

We follow the notations in the paper. $D_{n}$ is easily transformed to $D_{n}^{-}$, which the paper will focus. The main theorem (DKW with sharp bound) is

Theorem 1: $P(D_{n}^{-} > \lambda) \leq exp(-2 \lambda^{2})$, under some very mild conditions.

The key idea is to compare $D_{n}^{-}$ with some quantities $f_{\lambda}(s)$ derived from Brownian bridge.

More precisely, we have

(2.3) $P(D_{n}^{-} > \lambda) = \sum_{0 \leq j \leq n - \lambda \sqrt{n}} p_{\lambda,n}(j)$
(2.4) $exp(-2\lambda^{2}) = \int_{0}^{1} f_{\lambda}(s) ds$
(Prop. 1) compares $p_{\lambda,n}(j) and f_{\lambda}(s)$

Finally, in the last 5 pages, the author broke things down to two cases and proved them separately by hard estimation.

$n \geq 39$ and $\lambda \leq \sqrt(n)/2$
$n \leq 38$ or $\lambda > \sqrt(n)/2$

To my surprise, Kolmogorov distribution is distribution-free, meaning that it does not depend on the underlying cdf! And this is actually not difficult to see - Hints:

Any random variable $X$ with continuous cdf $F$ satisfies that $F(X)$ is a $Unif_{[0,1]}$!
Replace $x$ with $F^{-1}(t)$ and $x \in \mathbb{R}$ with $t \in [0,1]$ in the definition $D_{n}$. (This argument should also work for other $L_{p}$-norms (up to a Jacobian of $F$), but I still can't find a version of DKL inequality for them.)

Main Steps

We follow the notations in the paper. $D_{n}$ is easily transformed to $D_{n}^{-}$, which the paper will focus. The main theorem (DKW with sharp bound) is

Theorem 1: $P(D_{n}^{-} > \lambda) \leq exp(-2 \lambda^{2})$, under some very mild conditions.

The key idea is to compare $D_{n}^{-}$ with some quantities $f_{\lambda}(s)$ derived from Brownian bridge.

More precisely, we have

(2.3) $P(D_{n}^{-} > \lambda) = \sum_{0 \leq j \leq n - \lambda \sqrt{n}} p_{\lambda,n}(j)$
(2.4) $exp(-2\lambda^{2}) = \int_{0}^{1} f_{\lambda}(s) ds$
(Prop. 1) compares $p_{\lambda,n}(j) and f_{\lambda}(s)$

Finally, in the last 5 pages, the author broke things down to two cases and proved them separately by hard estimation.

$n \geq 39$ and $\lambda \leq \sqrt(n)/2$
$n \leq 38$ or $\lambda > \sqrt(n)/2$

Source Link

created Sep 14, 2023 at 0:45

Student

5.2k
11
33

To my surprise, Kolmogorov distribution is distribution-free, meaning that it does not depend on the underlying cdf! And this is actually not difficult to see - Hints:

Any random variable $X$ with continuous cdf $F$ satisfies that $F(X)$ is a $Unif_{[0,1]}$!
Replace $x$ with $F^{-1}(t)$ and $x \in \mathbb{R}$ with $t \in [0,1]$ in the definition $D_{n}$. (This argument should also work for other $L_{p}$-norms, but I still can't find a version of DKL inequality for them.)

Main Steps

We follow the notations in the paper. $D_{n}$ is easily transformed to $D_{n}^{-}$, which the paper will focus. The main theorem (DKW with sharp bound) is

Theorem 1: $P(D_{n}^{-} > \lambda) \leq exp(-2 \lambda^{2})$, under some very mild conditions.

The key idea is to compare $D_{n}^{-}$ with some quantities $f_{\lambda}(s)$ derived from Brownian bridge.

More precisely, we have

(2.3) $P(D_{n}^{-} > \lambda) = \sum_{0 \leq j \leq n - \lambda \sqrt{n}} p_{\lambda,n}(j)$
(2.4) $exp(-2\lambda^{2}) = \int_{0}^{1} f_{\lambda}(s) ds$
(Prop. 1) compares $p_{\lambda,n}(j) and f_{\lambda}(s)$

Finally, in the last 5 pages, the author broke things down to two cases and proved them separately by hard estimation.

$n \geq 39$ and $\lambda \leq \sqrt(n)/2$
$n \leq 38$ or $\lambda > \sqrt(n)/2$