8
$\begingroup$

The Dvoretzky–Kiefer–Wolfowitz inequality is the following:

$Pr(\text{sup}|\hat{F}_n(x)-F(x)|>\epsilon)\leq 2\exp(-2n\epsilon^2)$,

and it predicts how close an empirically determined distribution function will be to the distribution function from which the empirical samples are drawn. Using this inequality we are able to draw confidence intervals (CI's) around $\hat{F}_n(x)$ (ECDF). But these CI's will be equal in distance around every point of the ECDF .

What I wonder, is there another way to construct a CI around the ECDF?

Reading about ordered statistics we find that the asymptotic distribution of the ordered statistic is the following:

formula from hyperlink

Now, first off, what does the $np$-index with those symbols mean?

Main question: are we able to use this result, together with the delta method (see below), to provide CI's for the ECDF. I mean, the ECDF is a function of the ordered statistic, right? But at the same time the ECDF is a non-parametric function, so is this a dead end?

We know that $E(\hat{F}_n(x))=F(x)$ and $\text{Var}(\hat{F}_n(x))=\frac{F(x)(1-F(x))}{n}$

I hope I'm clear as to what I'm getting at here, and appreciate any help.

EDIT:

Delta method: If you have a sequence of random variables $X_n$ satisfying

enter image description here,

and $\theta$ and $\sigma^2$ are finite, then the following is satisfied:

enter image description here,

for any function g satisfying the property that $g′(\theta)$ exists, is non-zero valued, and is polynomially bounded with the random variable (quote wikipedia)

$\endgroup$
6
  • 1
    $\begingroup$ $\lceil np\rceil$ means $np$ rounded up to the next integer. $X_{(i)}$ would be the $i$-th largest observation (the $i$-th order statistic); putting those two bits of notation together (let $i=np$) gives you $X_{(\lceil np\rceil)}$. $\endgroup$ – Glen_b Nov 14 '15 at 11:10
  • $\begingroup$ Ok! And p is just equal to $\hat{F}_n(x)$, such that np equals i? $\endgroup$ – Erosennin Nov 14 '15 at 11:38
  • 1
    $\begingroup$ See inside-r.org/packages/cran/sfsmisc/docs/ecdf.ksCI for a solution in R. $\endgroup$ – kjetil b halvorsen Nov 14 '15 at 12:29
  • $\begingroup$ So your way of calculating the CI's are based on the Kolmogorov-Smirnov statistic, if I understand things correctly? I can look into that as well! Thanks! $\endgroup$ – Erosennin Nov 14 '15 at 13:09
  • 1
    $\begingroup$ If I remember correctly, using the KS statistic would give you the Dvoretzky–Kiefer–Wolfowitz.band. The statement you have doesn't say that you choose $p$ to make $np=i$. If you take some $p$ you have an asymptotic result that you quoted; this will involve the limit of a sequence of $n$-values, and you don't need $np$ to be integer for any of them. $\endgroup$ – Glen_b Nov 14 '15 at 15:47
5
$\begingroup$

I see no way of using the delta method, but...

Reading about the convergence of the empirical distribution function we read that the central limit theorem gives us:

$\sqrt{n}(\hat{F}_n(x)-F(x)) \rightarrow \mathcal{N}(0,F(x)(1-F(x)))$

We can use this to create varying CI's around each $\hat{F}_n(x)$:

$\hat{F}_n(x) \pm 1.96\frac{\hat{F}_n(x)(1-\hat{F}_n(x))}{n}$,

since $E(\hat{F}_n(x))=F(x)$, $\hat{F}_n(x)$ is our best estimate of $F(x)$.

Using the following R-code:

#confidenc ebands calculation:
sim_norm<-rnorm(100)
plot(sim_norm)
hist(sim_norm)
sim_norm_sort<-sort(sim_norm)
n = sum(!is.na(sim_norm_sort))
plot(sim_norm_sort, (1:n)/n, type = 's', ylim = c(0, 1), 
     xlab = 'sample', ylab = '', main = 'Empirical Cumluative Distribution')

# Dvoretzky–Kiefer–Wolfowitz inequality:
# P ( sup|F_n - F| > epsilon  ) leq 2*exp(-2n*epsilon^2)
# set alpha to 0.05 and alpha=2*exp(-2n*epsilon^2):
# --> epsilon_n = sqrt(-log(0.5*0.05)/(2*n))
#
#lower and upper bands:
L<-1:n
U<-1:n


  epsilon_i = sqrt(log(2/0.05)/(2*n))

  L=pmax(1:n/n-epsilon_i, 0)
  U=pmin(1:n/n+epsilon_i, 1)
  lines(sim_norm_sort, U, col="blue")
  lines(sim_norm_sort, L, col="blue")

#using clt:
U2=(1:n/n)+1.96*sqrt( (1:n/n)*(1-1:n/n)/n )
L2=(1:n/n)-1.96*sqrt( (1:n/n)*(1-1:n/n)/n )
lines(sim_norm_sort, L2, col="red")
lines(sim_norm_sort, U2, col="red")

We get:

Blue = KWD bands, Red = CLT bands

We see that the red bands (from the CLT method) gives us more narrow confidence bands.

EDIT: As @Kjetil B Halvorsen pointed out - these two types of bands are different types. I had @Glen_b explain exactly what he meant:

Very different kinds of confidence bands. With a pointwise confidence band you'd expect a number of points outside the band even if it was the distribution from which the data were drawn. With simultaneous bands you wouldn't. If you have a 95% pointwise band, on average 5% of the points for the correct distribution would be outside the bands. With simultaneous bands, there's a 5% chance that the point with the biggest deviation is outside.

Many thanks to both!

$\endgroup$
8
  • $\begingroup$ Why is this way not preferred over using the DKW inequality - or the KS statistic? I've never see anybody construct the confidence bands in this way before... $\endgroup$ – Erosennin Nov 18 '15 at 14:18
  • 1
    $\begingroup$ It only gives confidence bands individually, for each $x$, not simultaneously $\endgroup$ – kjetil b halvorsen Nov 18 '15 at 16:00
  • $\begingroup$ By "it" I assume you mean the "CLT way". And for example DKW does not really give anything simultaneously either, it just states the "maximum" distance $\epsilon$ and use this as confidence band for every point x. And similarly for KS. $\endgroup$ – Erosennin Nov 18 '15 at 16:04
  • $\begingroup$ Yes, and by using a maximum in this way they obtain a confidence band valid simultaneously. $\endgroup$ – kjetil b halvorsen Nov 18 '15 at 16:06
  • 2
    $\begingroup$ Interesting discussion here. I added the pointwise CDF intervals to Wikipedia and some discussion around the differences between these methods. I also updated the DKW page to discuss intervals more specifically. Take a look and feel free to update the pages or PM me on either site en.wikipedia.org/wiki/… en.wikipedia.org/wiki/… $\endgroup$ – Bscan Apr 15 '18 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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