# 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. Commented Feb 19, 2011 at 5:42

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.