In the theory of probability and statistics, the DvoretzkyâKieferâWolfowitzâMassart inequality (DKW inequality) provides a bound on the worst case distance of an empirically determined distribution function from its associated population distribution function. It is named after Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz, who in 1956 proved the inequality
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]
Given a natural number n, let X1, X2, âŠ, Xn be real-valued independent and identically distributed random variables with cumulative distribution function F(·). Let Fn denote the associated empirical distribution function defined by
so is the probability that a single random variable is smaller than , and is the fraction of random variables that are smaller than .
The DvoretzkyâKieferâWolfowitz inequality bounds the probability that the random function Fn differs from F by more than a given constant Δ > 0 anywhere on the real line. More precisely, there is the one-sided estimate
which also implies a two-sided estimate [5]
This strengthens the GlivenkoâCantelli theorem by quantifying the rate of convergence as n tends to infinity. It also estimates the tail probability of the KolmogorovâSmirnov statistic. The inequalities above follow from the case where F corresponds to be the uniform distribution on [0,1] [6] as Fn has the same distributions as Gn(F) where Gn is the empirical distribution of U1, U2, âŠ, Un where these are independent and Uniform(0,1), and noting that
with equality if and only if F is continuous.
In the multivariate case, X1, X2, âŠ, Xn is an i.i.d. sequence of k-dimensional vectors. If Fn is the multivariate empirical cdf, then
for every Δ, n, k > 0. The (n + 1) term can be replaced with a 2 for any sufficiently large n. [4]
The DvoretzkyâKieferâWolfowitz inequality is obtained for the KaplanâMeier estimator which is a right-censored data analog of the empirical distribution function
for every and for some constant , where is the KaplanâMeier estimator, and is the censoring distribution function. [7]
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, , with probability is often specified as
which is also a special case of the asymptotic procedure for the multivariate case, [4] whereby one uses the following critical value
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.
In the theory of probability and statistics, the DvoretzkyâKieferâWolfowitzâMassart inequality (DKW inequality) provides a bound on the worst case distance of an empirically determined distribution function from its associated population distribution function. It is named after Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz, who in 1956 proved the inequality
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]
Given a natural number n, let X1, X2, âŠ, Xn be real-valued independent and identically distributed random variables with cumulative distribution function F(·). Let Fn denote the associated empirical distribution function defined by
so is the probability that a single random variable is smaller than , and is the fraction of random variables that are smaller than .
The DvoretzkyâKieferâWolfowitz inequality bounds the probability that the random function Fn differs from F by more than a given constant Δ > 0 anywhere on the real line. More precisely, there is the one-sided estimate
which also implies a two-sided estimate [5]
This strengthens the GlivenkoâCantelli theorem by quantifying the rate of convergence as n tends to infinity. It also estimates the tail probability of the KolmogorovâSmirnov statistic. The inequalities above follow from the case where F corresponds to be the uniform distribution on [0,1] [6] as Fn has the same distributions as Gn(F) where Gn is the empirical distribution of U1, U2, âŠ, Un where these are independent and Uniform(0,1), and noting that
with equality if and only if F is continuous.
In the multivariate case, X1, X2, âŠ, Xn is an i.i.d. sequence of k-dimensional vectors. If Fn is the multivariate empirical cdf, then
for every Δ, n, k > 0. The (n + 1) term can be replaced with a 2 for any sufficiently large n. [4]
The DvoretzkyâKieferâWolfowitz inequality is obtained for the KaplanâMeier estimator which is a right-censored data analog of the empirical distribution function
for every and for some constant , where is the KaplanâMeier estimator, and is the censoring distribution function. [7]
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, , with probability is often specified as
which is also a special case of the asymptotic procedure for the multivariate case, [4] whereby one uses the following critical value
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.