# Kolmogorov-Smirnov and lattice paths

I have seen asserted that the problem of computing the null distribution of Kolmogorov's $D_n^+$ statistic for a finite sample size maps onto the problem of computing the number of lattice paths that stay below the diagonal, and thus can be solved by the ballot theorem. I am familiar with lattice paths and the ballot problem. I am also familiar the expression of the distribution of $D_n^+$ as a series of integrals. But I don't see how one problem maps onto the other. Can someone explain or point me to an ariticle or book that does?

I also see the claim the the null distribution of the Kolmogorov-Smirnov $D_n = \max(D_n^+,D_n^-)$ maps onto another lattice path problem that could be solved by a "two-sided ballot theorem". I don't know what a "two-sided" version of the ballot problem would be. Again, can someone explain or point me to an explanation?

Finally, is there a general framework around all of this? Can the Kuiper statistic be mapped to yet another lattice path problem? The two-sample KS test? The AD statistic?

-
I'm not sure about the two-sample problem, but as for references for the former, see: A. P. Dempster, Generalized $D_n^+$ Statistics, Ann. Math. Statist. Volume 30, Number 2 (1959), 593-597. Also, here, here and here might have some material of interest. The first and last links should be to publicly available articles. Sadly, the middle two aren't. –  cardinal Feb 19 '11 at 5:42

To add to @Cardinal 's answers in the comments, I think there is work that addresses the "claim the null distribution of the Kolmogorov-Smirnov maps onto another lattice path problem that could be solved by a "two-sided ballot theorem" and "is there a general framework around all of this? The two-sample KS test?":

This paper (preprint) is concerned with r-sample Kolmogorov-Smirnov tests and they derive the exact null distribution by counting lattice paths by using a generalization of the classical reflection principle. In Section 2, I find that they lay out nicely how lattice path counting comes into play when deriving the null hypothesis.

In the introduction the paper also features a discussion on how lattice path counting and the reflection principle tie in here by reviewing ideas started with Kiefer 1959 and David 1958. They also briefly discuss how it can be seen as an r-ballot counting problem, referring to Filaseta 1985.

They provide a lattice path counting framework for KS type tests for any number of samples. From the paper:

We consider the problem of testing whether $r ≥ 2$ samples are drawn from the same continuous distribution $F(x)$. As a test statistic we will use the circular differences $\delta_r (n) = \max [\delta_{1,2} > (n), \delta_{2,3} (n), . . . , \delta_{r−1,r} (n), \delta_{r,1} (n)],$ where $\delta_{ij} (n) = \sup_x [F_{n,i} (x) − F_{n,j} (x)]$, and $F_{n,i} (x), i = 1, 2, . . . , r$ denote the empirical distribution functions of these samples. We derive the null distribution of $\delta_r(n)$ by considering lattice paths in $r$-dimensional space with standard steps in the positive direction, i.e., steps are given by the unit vectors $e_i , i = 1, 2, . . . , r$. By a simple transformation we show that for some positive integer $k$ the number of ways the event $\{n\delta_r (n) < k\}$ can occur is just the number of paths $X$ with the property that for each point $X_m$ on the path there holds the chain of inequalities $x_{1,m} > x_{2,m} > . . . > > x_{r,m} > x_{1,m − rk}$. Indeed, the enumeration of such paths is a well studied problem in combinatorics. Again the reflection principle comes into play as we have to count paths in alcoves of affine (and therefore infinite) Weyl groups; for references on the technical background of this topic see Gessel and Zeilberger 1992, Grabiner 2002 and Krattenthaler 2007.

Hopefully this is a good starting point for further investigations into the Kuiper and AD statistics for example.

-