Dvoretzky–Kiefer–Wolfowitz inequality

In the theory of

, who in 1956 proved the inequality

\Pr {\Bigl (}\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|>\varepsilon {\Bigr )}\leq Ce^{-2n\varepsilon ^{2}}\qquad {\text{for every }}\varepsilon >0.

with an unspecified multiplicative constant C in front of the exponent on the right-hand side.[1]

In 1990, Pascal Massart proved the inequality with the sharp constant C = 2,^[2] confirming a conjecture due to Birnbaum and McCarty.^[3] In 2021, Michael Naaman proved the multivariate version of the DKW inequality and generalized Massart's tightness result to the multivariate case, which results in a sharp constant of twice the dimension k of the space in which the observations are found: C = 2k.^[4]

The DKW inequality

Given a natural number n, let X₁, X₂, …, X_n be real-valued

independent and identically distributed random variables with cumulative distribution function F(·). Let F_n denote the associated empirical distribution function

defined by

F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq x\}},\qquad x\in \mathbb {R} .

so $F(x)$ is the probability that a single random variable $X$ is smaller than $x$ , and $F_{n}(x)$ is the fraction of random variables that are smaller than $x$ .

The Dvoretzky–Kiefer–Wolfowitz inequality bounds the probability that the

random function

F_n differs from F by more than a given constant ε > 0 anywhere on the real line. More precisely, there is the one-sided estimate

\Pr {\Bigl (}\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon {\Bigr )}\leq e^{-2n\varepsilon ^{2}}\qquad {\text{for every }}\varepsilon \geq {\sqrt {{\tfrac {1}{2n}}\ln 2}},

which also implies a two-sided estimate [5]

\Pr {\Bigl (}\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|>\varepsilon {\Bigr )}\leq 2e^{-2n\varepsilon ^{2}}\qquad {\text{for every }}\varepsilon >0.

This strengthens the

uniform distribution on [0,1] ^[6]

as F_n has the same distributions as G_n(F) where G_n is the empirical distribution of U₁, U₂, …, U_n where these are independent and Uniform(0,1), and noting that

\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|\;{\stackrel {d}{=}}\;\sup _{x\in \mathbb {R} }|G_{n}(F(x))-F(x)|\leq \sup _{0\leq t\leq 1}|G_{n}(t)-t|,

with equality if and only if F is continuous.

Multivariate case

In the multivariate case, X₁, X₂, …, X_n is an i.i.d. sequence of k-dimensional vectors. If F_n is the multivariate empirical cdf, then

\Pr {\Bigl (}\sup _{t\in \mathbb {R} ^{k}}|F_{n}(t)-F(t)|>\varepsilon {\Bigr )}\leq (n+1)ke^{-2n\varepsilon ^{2}}

for every ε, n, k > 0. The (n + 1) term can be replaced with a 2 for any sufficiently large n.[4]

Kaplan–Meier estimator

The Dvoretzky–Kiefer–Wolfowitz inequality is obtained for the Kaplan–Meier estimator which is a right-censored data analog of the empirical distribution function

\Pr {\Bigl (}{\sqrt {n}}\sup _{t\in [0,\infty )}|(1-G(t))(F_{n}(t)-F(t))|>\varepsilon {\Bigr )}\leq 2.5e^{-2\varepsilon ^{2}+C\varepsilon }

for every $\varepsilon >0$ and for some constant $C<\infty$ , where $F_{n}$ is the Kaplan–Meier estimator, and $G$ is the censoring distribution function.^[7]

Building CDF bands

The Dvoretzky–Kiefer–Wolfowitz inequality is one method for generating CDF-based confidence bounds and producing a confidence band, which is sometimes called the Kolmogorov–Smirnov confidence band. The purpose of this confidence interval is to contain the entire CDF at the specified confidence level, while alternative approaches attempt to only achieve the confidence level on each individual point, which can allow for a tighter bound. The DKW bounds runs parallel to, and is equally above and below, the empirical CDF. The equally spaced confidence interval around the empirical CDF allows for different rates of violations across the support of the distribution. In particular, it is more common for a CDF to be outside of the CDF bound estimated using the DKW inequality near the median of the distribution than near the endpoints of the distribution.

The interval that contains the true CDF, $F(x)$ , with probability $1-\alpha$ is often specified as

F_{n}(x)-\varepsilon \leq F(x)\leq F_{n}(x)+\varepsilon \;{\text{ where }}\varepsilon ={\sqrt {\frac {\ln {\frac {2}{\alpha }}}{2n}}}

which is also a special case of the asymptotic procedure for the multivariate case,^[4] whereby one uses the following critical value

{\frac {d(\alpha ,k)}{\sqrt {n}}}={\sqrt {\frac {\ln {\frac {2k}{\alpha }}}{2n}}}

for the multivariate test; one may replace 2k with k(n + 1) for a test that holds for all n; moreover, the multivariate test described by Naaman can be generalized to account for heterogeneity and dependence.

References

MR 0083864

MR 1062069

Zbl 0087.34002
.

^
S2CID 233844405
.

ISBN 9780387749778

^
ISBN 0-471-86725-X

^ Bitouze, D.; Laurent, B.; Massart, P. (1999), "A Dvoretzky–Kiefer–Wolfowitz type inequality for the Kaplan–Meier estimator", Annales de l'Institut Henri Poincaré B, 35 (6),
doi:10.1016/S0246-0203(99)00112-0

Retrieved from "https://en.wikipedia.org/w/index.php?title=Dvoretzky–Kiefer–Wolfowitz_inequality&oldid=1195057681"

[Dvoretzky-1] MR 0083864

[Massart-2] MR 1062069

[3] Zbl 0087.34002
.

[:0-4] 
S2CID 233844405
.

[Kosorok-5] ISBN 9780387749778

[Shorack-6] 
ISBN 0-471-86725-X

[Bitouze-7] Bitouze, D.; Laurent, B.; Massart, P. (1999), "A Dvoretzky–Kiefer–Wolfowitz type inequality for the Kaplan–Meier estimator", Annales de l'Institut Henri Poincaré B, 35 (6),
doi:10.1016/S0246-0203(99)00112-0

[2]

[3]

[4]

[6]

[7]

The DKW inequality

Multivariate case

Kaplan–Meier estimator

Building CDF bands

See also

References