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

Question

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}}$?

Answer 1

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.