# Computing Dvoretzky–Kiefer–Wolfowitz bounds in MATLAB

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

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)$$

1. 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.

• Thank you so much! This is exactly what I was trying to understand.
– r2d2
Apr 7 '15 at 23:19
• Glad I could help--and welcome to Cross Validated! Apr 8 '15 at 2:14