The Kolmogorov-Smirnov Statistic Revisited
Elvis Han Cui, Yihao Li, Zhuang Liu · 2025
Read The Kolmogorov-Smirnov Statistic Revisited by Elvis Han Cui, Yihao Li, Zhuang Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11673.txt.
Introduction
Elvis Han Cui, Yihao Li, and Zhuang Liu revisit a classic test for whether data fit a claimed pattern, in work from 2025. The test looks at the largest gap between observed and claimed spread, but its small sample behavior turns on where a path first crosses a border.
The trio recast an old one sample formula as a first crossing law and build a steady tool for tail chances. For two samples, they give exact counting rules for any sample sizes. Their lens also explains a famed bound as a squeezed form of exact counts. Small checks end with a warning about fit when the claimed pattern itself was fit from the data.
Catalog record
| CREATOR | Elvis Han Cui, Yihao Li, Zhuang Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-11673
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Kolmogorov-Smirnov Statistic Revisited Elvis Han Cui, Yihao Li, Zhuang Liu Abstract , , ?? Department of Biostatistics, University of California, Los Angeles, ?? ?? Department of Biostatistics, University of California, Los Angeles, ?? ?? College of Environmental and Resource Sciences, Zhejiang University, ?? 1 Introduction The Kolmogorov-Smirnov (KS) statistic is a classical nonparametric test statistic widely used for comparing an empirical distribution function with a reference distribution or for comparing two empirical distributions [ 2 ] . Since its inception, the KS statistic has played a crucial role in fields ranging from statistical hypothesis testing to model validation, particularly due to its simplicity and robustness under minimal assumptions about the underlying data distributions. The two primary forms of the KS test, the one-sample and two-sample versions, offer versatile tools for evaluating goodness-of-fit and detecting differences between distributions, respectively. The one-sample KS statistic evaluates the supremum of the absolute differences between an empirical cumulative distribution function (CDF) and a theoretical CDF. It provides a nonparametric method to assess whether a sample follows a specific distribution. The two-sample KS statistic, on the other hand, compares the empirical CDFs of two independent samples, allowing for the detection of distributional differences without requiring parametric assumptions. The statistic’s distribution under the null hypothesis is pivotal for deriving p-values and making statistical inferences. While the KS statistic and its limiting distributions are well-established, there remain opportunities to refine its practical applicability and understanding, particularly under finite sample conditions. Existing results, such as the Smirnov-Birnbaum-Tingey theorem and the Gnedenko-Rvateva-Feller theorem, provide exact distributions for the one-sided KS statistics under specific conditions. However, these results are not as widely known or utilized, despite their potential utility in modern statistical analysis. In this paper, we revisit the KS statistic with a focus on both one-sample and two-sample cases, considering both one-sided and two-sided variants. We derive exact probabilities for the supremum of the empirical process and provide a unified treatment of the KS statistic under various settings. Additionally, we explore the discrete nature of the hitting times of the normalized empirical process, offering insights into the practical computation of KS test p-values. Our work also includes a discussion of the Dvoretzky–Kiefer–Wolfowitz-Massart (DKWM) inequality and its implications for constructing confidence bands for distribution functions [ 6 , 10 ] . Finally, empirical process theory is used to show the limit distribution of KS statistic when the true distribution has unknown parameters. 2 One-sided One Sample Kolmogorov-Smirnov Statistic Let X_{1},\cdots,X_{n} be a random sample with continuous distribution function F and let F_{n} be its empirical counterpart, i.e., F_{n}(t)=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}(X_{i}\leq t). Let Z_{n}(t)=\sqrt{n}\left(F_{n}-F\right)(t) be the normalized empirical process and D_{n}^{+},D_{n}^{-} be the one-sided Kolmogorov-Smirnov statistic, i.e., D_{n}^{+}=\sup_{t}\frac{Z_{n}(t)}{\sqrt{n}}=\sup_{t}(F_{n}(t)-F(t)), D_{n}^{-}=\sup_{t}\frac{-Z_{n}(t)}{\sqrt{n}}=\sup_{t}(F(t)-F_{n}(t)). The following result seems to be very useful but not well-known. Theorem 2.1 (Smirnov-Birnbaum-Tingey). Let \lambda\in[0,\sqrt{n}] and \epsilon=\frac{\lambda}{\sqrt{n}} . Set \tau_{n}(\lambda)=\inf_{t}\{t:Z_{n}(t)\leq-\lambda\} to be the first time that Z_{n}(t) hits -\lambda . We have \displaystyle\mathbb{P}\left(D_{n}^{-}>\epsilon\right) \displaystyle=(1-\epsilon)^{n}+\epsilon\sum_{j=1}^{\lfloor n(1-\epsilon)\rfloor}\binom{n}{j}\left(\epsilon+\frac{j}{n}\right)^{j-1}\left(1-\epsilon-\frac{j}{n}\right)^{n-j}. (1) If we further assume that F(t)=t , i.e., X is uniform on [0,1] , then \displaystyle\mathbb{P}\left(\tau_{n}(\lambda)=\epsilon+\frac{j}{n}\right) \displaystyle=\epsilon\binom{n}{j}\left(\epsilon+\frac{j}{n}\right)^{j-1}\left(1-\epsilon-\frac{j}{n}\right)^{n-j} (2) for all j=0,1,\cdots,\lfloor n-\lambda\sqrt{n}\rfloor. Remark 1 : The assumption that F(t)=t can always be true in practice since the distributions of Z_{n}(t) and D_{n}^{+} do not depend on F . If we do not wish to make such an assumption, then we simply make an inverse transformation, i.e., set \tau_{n}(\lambda)=F^{-1}\left(\epsilon+\frac{j}{n}\right) . Remark 2 : It is worth noting that \tau_{n}(\lambda) is discrete despite of a positive probability that \tau_{n}(\lambda)=+\infty . The process Z_{n}(t) is always decreasing if t is not a jump point (Figure 1 ). At t=X_{i} , it has jump size \frac{1}{\sqrt{n}} . Hence, if Z_{n}(t) does not cross below -\lambda at X_{(i)} , the i -th order statistic, then it has to wait another \frac{1}{n} time to see whether it is below -\lambda or not. But the first possible hitting time is \epsilon=\frac{\lambda}{\sqrt{n}} given that no X_{i} is less than \epsilon . In other words, the equation F_{n}(t)-t=-\epsilon has at most only finite number of solutions and they are of form \epsilon+\frac{j}{n} . Fig 1: Normalized Empirical Process Z_{n} with \lambda=0.8 By simple observations, the event \{\tau_{n}(\lambda)=\epsilon+\frac{j}{n}\} can happen only if there are n-j X_{i} ’s are greater or equal to \epsilon+\frac{j}{n} . The rest of j X_{i} ’s need to be placed carefully since at time \epsilon+\frac{k}{n},k\leq j we must have at least k X_{i} ’s being observed, otherwise the process Z_{n}(t) will reach -\lambda at some point. After some simple algebra, the problem of finding the distribution of \tau_{n}(\lambda) boils down to compute the following integral: \displaystyle\int_{0}^{\epsilon}\int_{X_{1}}^{\epsilon+\frac{1}{n}}\cdots\int_{X_{j-1}}^{\epsilon+\frac{j-1}{n}}\int_{\epsilon+\frac{j}{n}}^{1}\int_{X_{j+1}}^{1}\cdots\int_{X_{n-1}}^{1}dX_{n}\cdots dX_{j+2}dX_{j+1}dX_{j}\cdots dX_{2}dX_{1}. The multiple integral can be written as a product of two parts: \left(\int_{0}^{\epsilon}\int_{X_{1}}^{\epsilon+\frac{1}{n}}\cdots\int_{X_{j-1}}^{\epsilon+\frac{j-1}{n}}dX_{j}\cdots dX_{2}dX_{1}\right)\left(\int_{\epsilon+\frac{j}{n}}^{1}\int_{X_{j+1}}^{1}\cdots\int_{X_{n-1}}^{1}dX_{n}\cdots dX_{j+2}dX_{j+1}\right). The second part, by direct calculation, is \frac{(1-\epsilon-\frac{j}{n})^{n-j}}{(n-j)!} while the first part is more complicated. We need the following formula due to Birnbaum and Tingey 1951 . \int_{0}^{\epsilon}\int_{X_{1}}^{\epsilon+\frac{1}{n}}\cdots\int_{X_{j-1}}^{\epsilon+\frac{j-1}{n}}dX_{j}\cdots dX_{2}dX_{1}=\epsilon\frac{(\epsilon+\frac{j}{n})^{j-1}}{j!}. Hence, the integral is equal to \frac{\epsilon\left(\epsilon+\frac{j}{n}\right)^{j-1}\left(1-\epsilon-\frac{j}{n}\right)^{n-j}}{j!(n-j)!}. But for each random sample of size n , there are n! equally-likely orderings, so we multiple the integral by n! and this is the probability that \tau_{n}(\lambda)=\epsilon+\frac{j}{n} : \epsilon\binom{n}{j}\left(\epsilon+\frac{j}{n}\right)^{j-1}\left(1-\epsilon-\frac{j}{n}\right)^{n-j}. Finally, the event \{D_{n}^{-}>\epsilon\} is the union of \bigcup_{j=0}^{\lfloor n(1-\epsilon)\rfloor}\{\tau_{n}(\lambda)=\epsilon+\frac{j}{n}\} so that \mathbb{P}(D_{n}^{-}>\epsilon)=\epsilon\sum_{j=0}^{\lfloor n(1-\epsilon)\rfloor}\binom{n}{j}\left(\epsilon+\frac{j}{n}\right)^{j-1}\left(1-\epsilon-\frac{j}{n}\right)^{n-j}. ∎ 3 One-sided Two Sample Kolmogorov-Smirnov Statistic Let X_{1},X_{2},\cdots,X_{n} be a random sample with continuous distribution function F and Y_{1},\cdots,Y_{m},m\leq n be another random sample with continuous distribution function G . Let F_{n} and G_{m} be the empirical counterparts of F and G , i.e., F_{n}(t)=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}(X_{i}\leq t),\ G_{n}(t)=\frac{1}{n}\sum_{j=1}^{m}\mathbb{I}(Y_{j}\leq t). Theorem 3.1 (Gnedenko-Rvateva-Feller). Let D_{n,m}^{+} be the one-sided Kolmogorov-Smirnov statistic, i.e., D_{n,m}^{+}=\sup_{t}\left(F_{n}(t)-G_{m}(t)\right). If F=G , i.e., X and Y have the identical distribution, then the distribution of D_{n,m}^{+} is \displaystyle\mathbb{P}\left(D_{n,m}^{+}\geq\delta\right)=\frac{\binom{n+m}{n-k+l}}{\binom{n+m}{n}} (3) where \delta is of form \frac{k}{n}-\frac{l}{m}>0 for any k=1,\cdots,n,\ l=0,1,\cdots,m . Consider a symmetric random walk starting at 0 that takes n+m steps, where each step is either +1 or -1 with equal probability. After n+m steps, the walk arrives at position n-m , as there are n steps in the positive direction and m steps in the negative direction. The total number of such paths is \binom{n+m}{n}. The event \{D_{n,m}^{+}\geq\delta\} is equivalent to the event where the path hits or exceeds the level k-l at some step, where \delta=\frac{k}{n}-\frac{l}{m}>0 for integers k=1,\ldots,n and l=0,1,\ldots,m . By the Reflection Principle [ 7 ] , for each path that hits or exceeds the level k-l and then returns to the final position n-m , there exists a corresponding reflected path that instead arrives at position 2(k-l)+m-n. This reflection is achieved by reflecting the path at the first point where it hits the level k-l . The number of such reflected paths, which end at 2(k-l)+m-n , is given by \binom{n+m}{n-k+l}. Since each path is equally likely, the probability of the event \{D_{n,m}^{+}\geq\delta\} is the ratio of the favorable paths to the total number of paths: \mathbb{P}(D_{n,m}^{+}\geq\delta)=\frac{\binom{n+m}{n-k+l}}{\binom{n+m}{n}}. This completes the proof. ∎ Corollary 1 (Feller [ 8 ] ). If n=m and r=k-l , then we have \displaystyle\mathbb{P}\left(D_{n,n}^{+}\geq\frac{r}{n}\right)=\frac{\binom{2n}{n-r}}{\binom{2n}{n}}. (4) Corollary 2 . If n=m\rightarrow\infty , we have asymptotically \displaystyle\mathbb{P}\left(D_{n,n}^{+}\geq\frac{r}{\sqrt{n}}\right)\rightarrow e^{-r^{2}}. (5) Let k=\lfloor\sqrt{n}r\rfloor and k+1=\lceil\sqrt{n}r\rceil . The probability is lower and upper bounded by \frac{n!n!}{(n-k-1)!(n+k+1)!},\ \frac{n!n!}{(n-k)!(n+k)!}, respectively. Since k\rightarrow\infty and k/n\rightarrow 0 , the limit of the second term is \lim_{n\rightarrow\infty}\frac{n!n!}{(n-k)!(n+k)!}=\lim_{n\rightarrow\infty}\prod_{i=1}^{k}\left(1+\frac{1}{\frac{n}{k}-\frac{i-1}{k}}\right)^{-1}=\lim_{n\rightarrow\infty}\left(1+\frac{r}{\sqrt{n}}\right)^{-\sqrt{n}r}=e^{-r^{2}} and the same holds for the first term. ∎ Remark 3