Computing Dvoretzky–Kiefer–Wolfowitz bounds in MATLAB

Question

When I run the Kolmogorov-Smirnov test (kstest2 function in MATLAB) on two given data vectors, I get the value of KS Statistic. How should I compute Dvoretzky–Kiefer–Wolfowitz (DKW) bound using this information? When I look at the wiki and other web pages, it looks like if I plot the ECDF, the entire ECDF would be bounded by two curves (e.g. slide 14 here: http://cseweb.ucsd.edu/classes/fa07/cse103/CDFs.pdf). However, it appears to me that the DKW bound would just be a single value and not bounded on both sides. Could someone please explain computation of this bound in MATLAB? Any help would be greatly appreciated. Thanks.

Regards, RD

Answer 1

It sounds like you want to compute a confidence band: a region that contains the whole CDF with probability $1-\alpha$. Doing this with the Dvoretzky–Kiefer–Wolfowitz inequality involves three steps:

1. Generate the CDF (i.e., sort and count your values--trivial in matlab)

2. The inequality itself says that $$ P\bigg(\sup_x \big|F(x) - \hat{F}(x)\big| \gt \epsilon\bigg) \le 2\exp(-2n\epsilon^2)$$ where $F(x)$ is the "true" population CDF, $\hat{F}(x)$ is your sample CDF, and $n$ is the number of data points. Setting the right hand side of that inequality to $\alpha$ and rearranging yields:

$$ \epsilon = \sqrt{\frac{1}{2n}\log\bigg(\frac{2}{\alpha}}\bigg)$$

3. You can now draw the confidence band. The confidence band has an upper edge $U(x)$ and a lower edge $L(x)$: $$ \begin{align*} L(x) = max\{\hat{F}(x) &- \epsilon, 0\} \\ U(x) = min\{\hat{F}(x) &+ \epsilon, 1\} \end{align*}$$

Translating this into matlab is pretty trivial:

function [low_edge, F_hat, hi_edge, x] = dkw_bounds(data, alpha) [F_hat, x] = ecdf(data); epsilon = sqrt(ln(2/alpha)/(2*length(data))); low_edge = max(F_hat - epsilon, 0); %Does the right thing here, use pmax in R hi_edge = min(F_hat + epsilon, 1); end

You can then plot the three curves, use them to form a patch, etc.