# What is the two-sample CDF of of $D^{+}$ and $D^{-}$ from the one-sided Kolmogorov-Smirnov Test?

I am trying to understand how to obtain $p$-values for the one-sided Kolmogorov-Smirnov test, and am struggling to find CDFs for $D^{+}_{n_{1},n_{2}}$ and $D^{-}_{n_{1},n_{2}}$ in the two-sample case. The below is cited in a few places as the CDF for $D^{+}_{n}$ in a one-sample case:

$$p^{+}_{n}\left(x\right) = \text{P}\left(D^{+}_{n} \ge x | \text{H}_{0}\right) = x\sum_{j=0}^{\lfloor n\left(1-x\right)\rfloor}{ \binom{n}{j} \left(\frac{j}{n}+x\right)^{j-1}\left(1 - x - \frac{j}{n}\right)^{n-j}}$$

Also, whuber sez there's a slightly different formulation of this one-sample CDF (I am substituting $x$ for $t$ in his quote for consistency with my notation here):

Using the probability integral transform, Donald Knuth derives their (common) distribution on p. 57 and exercise 17 of TAoCP Volume 2. I quote:

$$\left(D^{+}_{n}\le \frac{x}{\sqrt{n}}\right)=\frac{x}{n^{n}}\sum_{c\le k\le x}\binom{n}{k}\left(k-x\right)^{k}\left(x+n-k\right)^{n-k-1}$$

This would apply to one-sided hypotheses in the one-sample case, such as: H$_{0}\text{: }F(x)-F_{0} \le 0$, where $F(x)$ is the empirical CDF of $x$, and $F_{0}$ is some CDF.

I think the $x$ in this case is the value of $D^{+}_{n}$ in one's sample, and that $\lfloor n\left(1-x\right)\rfloor$ is the largest integer in $n-nx$. (Is that right?)

But what is the CDF for $D^{+}_{n_{1},n_{2}}$ (or $D^{-}_{n_{1},n_{2}}$) when one has two samples? For example, when H$_{0}\text{: }F_{A}(x)-F_{B}(x) \le 0$ for the empirical CDFs of $A$ and $B$? How to obtain $p^{+}_{n_{1},n_{2}}$?

• Just as a pointer for anyone looking at answering this question - my answer to Alexis' previous question (which is linked in the above question) has links to several references with some discussion of the history, each with a number of relevant references. You may like to check those documents and their list of references. Jul 15 '14 at 23:10
• @Glen_b Thank you! I really appreciate your excellent answer to my other question, and did follow the cited resources, but I got no traction on the CDF for $D^{+}$ there, and rather than bog down the comments I thought I would just open a new query. Additional references welcome, if you know any that will work for this. Jul 15 '14 at 23:15
• Alexis: no criticism was intended by my comment; your choice to open a new question was exactly right (in my opinion). I just wanted to save people a little legwork in tracking down some of the relevant references - I figured it might not necessarily occur to everyone to follow your link to the other question, and it might not occur to the people who did that links in my answer had some references they might want to know of. Jul 15 '14 at 23:17

Ok, I am going to have a stab at this. Critical insights welcome.

On page 192 Gibbons and Chakraborti (1992), citing Hodges, 1958, start with a small-sample (exact?) CDF for the two-sided test (I am swapping their $$m,n$$ and $$d$$ notation for $$n_{1},n_{2}$$ and $$x$$, respectively):

$$\text{P}{\left(D_{n_{1},n_{2}}\ge x\right)} = 1 - \text{P}\left(D_{n_{1},n_{2}} \leq x\right)=1-\frac{A\left(n_{1},n_{2}\right)}{\binom{n_{1}+n_{2}}{n_{1}}}$$

Where $$A\left(n_{1},n_{2}\right)$$ is produced through an enumeration of paths (increasing monotonically in $$n_{1}$$ and $$n_{2}$$) from the origin to the point $$\left(n_{1},n_{2}\right)$$ through a graph with—substituting $$S_{m}(x)$$ for $$F_{n_{1}}(x)$$—the values of the x-axis and y-axis are $$n_{1}F_{1}\left(x\right)$$ and $$n_{2}F_{2}\left(x\right)$$. The paths must furthermore obey the constraint of staying inside the boundaries (where $$x$$ is the value of the Kolmogorov-Smirnov test statistic):

$$\frac{n_{2}}{n_{1}} \pm \frac{\left(n_{1}+n_{2}\right)x}{\binom{n_{1}+n_{2}}{n_{1}}}$$

Below is their image Figure 3.2 providing an example for $$A(3,4)$$, with 12 such paths:

Gibbons and Chakaborti go on to say that the one-sided $$p$$-value is obtained using this same graphical method, but with only the lower bound for $$D^{+}_{n_{1},n_{2}}$$, and only the upper for $$D^{-}_{n_{1},n_{2}}$$.

These small sample approaches entail path enumeration algorithms and/or recurrence relations, which undoubtedly make asymptotic calculations desirable. Gibbons and Chakraborti also note the limiting CDFs as $$n_{1}$$ and $$n_{2}$$ approach infinity, of $$D_{n_{1},n_{2}}$$:

$$\lim_{n_{1},n_{2}\to \infty}\text{P}\left(\sqrt{\frac{n_{1}n_{2}}{n_{1}+n_{2}}}D_{n_{1},n_{2}} \le x\right) = 1 - 2\sum_{i=1}^{\infty}{\left(-1\right)^{i-1}e^{-2i^{2}x^{2}}}$$

And they give the limiting CDF of $$D^{+}_{n_{1},n_{2}}$$ (or $$D^{-}_{n_{1},n_{2}}$$) as:

$$\lim_{n_{1},n_{2}\to \infty}\text{P}\left(\sqrt{\frac{n_{1}n_{2}}{n_{1}+n_{2}}}D^{+}_{n_{1},n_{2}} \le x\right) = 1 - e^{-2x^{2}}$$

Because $$D^{+}$$ and $$D^{-}$$ are strictly non-negative, the CDF can only take non-zero values over $$[0,\infty)$$:

$D^{+}$ (or $$D^{-}$$)" />

**References**
Gibbons, J. D. and Chakraborti, S. (1992). *Nonparametric Statistical Inference*. Marcel Decker, Inc., 3rd edition, revised and expanded edition.

Hodges, J. L. (1958). The significance probability of the Smirnov two-sample test. Arkiv för matematik. 3(5):469–486.

• The actual cdf exists everywhere, but for $(-\infty,0)$ the cdf will be zero; the functional form you gave only applies for $x\geq 0$ (this is amenable to simple reasoning; what's $P(D^+<0)$? Jul 19 '14 at 9:46