Continuous Kolmogorov smirnov Test Statistic Proof Step Function

Abstract

In this review article, we revisit derivation of the cumulative density function (CDF) of the test statistic of the one-sample Kolmogorov-Smirnov test. Even though several such proofs already exist, they often leave out essential details necessary for proper understanding of the individual steps. Our goal is filling in these gaps, to make our presentation accessible to advanced undergraduates. We also propose a simple formula capable of approximating the exact distribution to a sufficient accuracy for any practical sample size.

Share and Cite:

Vrbik, J. (2020) Deriving CDF of Kolmogorov-Smirnov Test Statistic. Applied Mathematics, 11, 227-246. doi: 10.4236/am.2020.113018.

1. Introduction

The article's goal is to present a comprehensive summary of deriving the distribution of the usual Kolmogorov-Smirnov test statistic, both in its exact and approximate form. We concentrate on practical aspects of this exercise, meaning that

• reaching a modest (three significant digit) accuracy is usually considered quite adequate,

• computing critical and P-values of the test is the primary objective, implying that it is the upper tail of the distribution which is most important,

• methods capable of producing practically instantaneous results are preferable to those taking several seconds, minutes, or more,

• simple, easy to understand (and to code) techniques have a great conceptual advantage over complex, black-box type algorithms.

This is the reason why our review excludes some existing results (however deep and mathematically interesting they may be); we concentrate only on the most relevant techniques (this is also the reason why our bibliography is deliberately far from complete).

1.1. Test Statistic

The Kolmogorov-Smirnov one-sample test works like this: the null hypothesis states that a random independent sample of size n has been drawn from a specific (including the value of each of its parameters, if any) continuous distribution. The test statistics (denoted $D_{n}$ ) is the largest (in the limit-superior sense) absolute-value difference between the corresponding empirical cumulative density function (CDF) and the theoretical CDF, denoted $F (x)$ , of the hypothesized distribution; the former is defined by

(1)

where $X_{1}, X_{2}, \dots, X_{n}$ are the individual sample values and $I_{X_{i} < x}$ is the usual indicator function (equal to 1 when $X_{i}$ is smaller than x, equal to 0 otherwise). Note that $F_{e} (x)$ is a step function which starts at 0 and increases, by $\frac{1}{n}$ at each $X_{i}$ , until it reaches the value of 1.

To complete the test, we need to know the CDF of $D_{n}$ under the assumption that the null hypothesis is correct. Deriving this CDF is a difficult task; there are several exact techniques for doing that; in this article, we expound only the major ones. We then derive the $n \to \infty$ limit of the resulting distribution, to serve as an approximation when n is relatively large. Since the accuracy of this limit is not very impressive (unless n is extremely large), we show how to remove the $\frac{1}{\sqrt{n}}$ -proportional, $\frac{1}{n}$ -proportional, etc. error of this approximation, making it sufficiently accurate for samples of practically any size.

1.2. Transforming to $U (0, 1)$

The first thing we do is to define

$U_{i} \overset{def}{=} F (X_{i})$ (2)

where $F (x)$ is the CDF of the hypothesized distribution; the $U_{1}, U_{2}, \dots, U_{n}$ then constitute (under the null hypothesis) a random independent sample from the uniform distribution over the $(0,1)$ interval, the new theoretical CDF is then simply $F (u) = u$ . It is important to realize that doing this does not change the vertical distances between the empirical and theoretical CDFs; it transforms only the corresponding horizontal scale as Figure 1 and Figure 2 demonstrate (the original sample is from Exponential distribution).

This implies that the resulting value of $D_{n}$ (and consequently, its distribution) remains the same. We can then conveniently assume (from now on) that our sample has been drawn from $U (0, 1)$ ; yet the results apply to any hypothesized distribution.

1.3. Discretization

In this article, we aim to find the CDF of $D_{n}$ , namely

$P r (D_{n} \leq d)$ (3)

only for a discrete set of n values of d, namely for $d = \frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}$ , even though $D_{n}$ is a continuous random variable whose support is the $(\frac{1}{2 n},1)$ interval. This proves to be sufficient for any (but extremely small) n, since our discrete results can be easily extended to all values of d by a sensible interpolation.

There are technique capable of yielding exact results for any value of d (see [1] or [2]), but they have some of the disadvantages mentioned above and will not be discussed here in any detail; nevertheless, for completeness, we present a Mathematica code of Durbin's algorithm in the Appendix.

2. Linear-Algebra Solution

This, and the next two section, are all based mainly on [3], later summarized by [4].

We start by defining $n + 1$ integer-valued random variables

$T_{i} \overset{def}{=} n \cdot (F_{e} (d_{i}) - d_{i})$ (4)

where $d_{i} = \frac{i}{n}$ , $i = 0,1,2, \dots, n$ ; note that $n \cdot F_{e} (d_{i})$ equals the number of the $U_{i}$ observations which are smaller than $d_{i}$ , also note that $T_{0}$ and $T_{n}$ are always identically equal to 0. We can then show that

Claim 1. $D_{n} > d_{j}$ if and only if at least one of the $T_{i}$ values is equal to j or –j.

Proof. When $T_{i} = j$ , then there is a value of d to the left of $d_{i}$ such that $F_{e} (d) - d > j$ , implying that $D_{n} > \frac{j}{n}$ ; similarly, when $T_{i} = - j$ then there is a value of d to the right of $d_{i}$ such that $F_{e} (d) - d < - j$ , implying the same.

To prove the reverse, we must first realize that no one-step decrease in the $T_{0}, T_{1}, \dots, T_{n}$ sequence can be bigger than 1 (this happens when there are no observations between the corresponding $d_{i}$ and $d_{i + 1}$ ); this implies that the T sequence must always pass through all integers between the smallest and the largest value ever reached by T.

Since $n \cdot D_{n} > j$ implies that either $n \cdot (F_{e} (d) - d)$ has exceeded the value of j at some d, or it has reached a value smaller than −j, it then follows that at least one $T_{i}$ has to be equal to either j or −j respectively. ■

2.1. Total-Probability Formula

Now, consider the sample space of all possible (integer) values of $T_{1}, T_{2}, \dots, T_{n - 1}$ , and a fixed integer J between 1 and $n - 1$ inclusive (we use the capital font to emphasize J's special role in all subsequent formulas). If $T_{i}$ is the first of the $T_{1}, T_{2}, \dots, T_{n - 1}$ random variables to reach the value of either J or –J, we denote the corresponding event $A_{i}$ and $B_{i}$ respectively ( $C$ means that none of the T_is have ever reached either J or −J); $A_{1}, A_{2}, \dots, A_{n - 1}, B_{1}, B_{2}, \dots, B_{n - 1}, C$ then constitute a partition of this sample space.

By a routine application of the formula of total probability, we can write, for any k between 1 and $n - J$ ( $T_{k} = J$ cannot happen for any other T)

$\begin{matrix} P r (T_{k} = J) = \sum_{i = 1}^{n - 1} P r (A_{i}) \cdot P r (T_{k} = J | A_{i}) + \sum_{i = 1}^{n - 1} P r (B_{i}) \cdot P r (T_{k} = J | B_{i}) \\ + P r (C) \cdot P r (T_{k} = J | C) \end{matrix}$ (5)

We know that, given $C$ , $T_{k} = J$ could not have happened. Similarly, given $A_{i}$ (given $B_{i}$ ), $T_{k} = J$ cannot happen any earlier than at $k \geq i$ ( $k > i$ ). And finally, $P r (B_{i})$ is equal to 0 when $i < J$ (we need at least J steps to reach $T_{i} = - J$ from $T_{0} = 0$ ). We can thus simplify (5) to read

$P r (T_{k} = J) = \sum_{i = 1}^{k} P r (A_{i}) \cdot P r (T_{k} = J | A_{i}) + \sum_{i = J}^{k - 1} P r (B_{i}) \cdot P r (T_{k} = J | B_{i})$ (6)

where $1 \leq k \leq n - J$ , with the understanding that an empty sum (lower limit exceeding the upper limit) equals to 0.

From (4) it is obvious that $T_{k} = J$ is equivalent to having (exactly to be understood from now on) $k + J$ observations smaller than $\frac{k}{n}$ .The corresponding probability is the same as that of getting $k + J$ successes in a binomial-type experiment with n trials and a single-success probability of $\frac{k}{n}$ ; we will denote it $B_{k + J}^{n} (\frac{k}{n})$ .

Similarly, $T_{k} = J | A_{i}$ has the same probability as $T_{k} = J | T_{i} = J$ (earlier values of T becoming irrelevant), which means that, out of the remaining $n - i - J$ observations, $k - i$ must be in the $(d_{i}, d_{k})$ interval; this probability is equal to $B_{k - i}^{n - i - J} (\frac{k - i}{n - i})$ .

Finally, $P r (T_{k} = J | B_{i}) = P r (T_{k} = J | T_{i} = - J)$ , which means that, out of the remaining $n - i + J$ observations, $k - i + 2 J$ must be in the $(d_{i}, d_{k})$ interval; this probability equals to $B_{i - J}^{n - i + J} (\frac{k - i}{n - i})$ .

2.2. Resulting Equations

We can thus simplify (6) to

$B_{k + J}^{n} (\frac{k}{n}) = \sum_{i = 1}^{k} P r (A_{i}) \cdot B_{k - i}^{n - i - J} (\frac{k - i}{n - i}) + \sum_{i = J}^{k - 1} P r (B_{i}) \cdot B_{k - i + 2 J}^{n - i + J} (\frac{k - i}{n - i})$ (7)

(with $1 \leq k \leq n - J$ ), where the $B$ coefficients are readily computable. This constitutes $n - J$ linear equations for the unknown values of $P r (A_{1}), P r (A_{2}), \dots, P r (A_{n - J})$ , $P r (B_{J}), P r (B_{J + 1}), \dots, P r (B_{n - 1})$ .

By the same kind of reasoning we can show that, for any k between J and $n - 1$

$P r (T_{k} = - J) = \sum_{i = 1}^{k - 2 J} P r (A_{i}) \cdot P r (T_{k} = - J | A_{i}) + \sum_{i = J}^{k} P r (B_{i}) \cdot P r (T_{k} = - J | B_{i})$ (8)

(note that the T sequence needs at least 2J steps to reach -J at $T_{k}$ from J at $T_{i}$ ), leading to

$B_{k - J}^{n} (\frac{k}{n}) = \sum_{i = 1}^{k - 2 J} P r (A_{i}) \cdot B_{k - i - 2 J}^{n - i - J} (\frac{k - i}{n - i}) + \sum_{i = J}^{k} P r (B_{i}) \cdot B_{k - i}^{n - i + J} (\frac{k - i}{n - i})$ (9)

when $J \leq k \leq n$ .

Combining (7) and (9), we end up with the total of $2 (n - J)$ linear equations for the same number of unknowns. Furthermore, these equations have a "doubly triangular" form, meaning that proceeding in the right order, i.e. $P r (A_{1}), P r (B_{J}), P r (A_{2}), P r (B_{J + 1}), \dots$ , we are always solving only for a single unknown (this is made obvious by the next Mathematica code).

Having found the solution, we can then compute (based on Claim 1)

$P r (D_{n} > d_{J}) = \sum_{i = 1}^{n - J} P r (A_{i}) + \sum_{i = J}^{n - 1} P r (B_{i})$ (10)

which yields a single value of the desired CDF (or rather, of its complement) of $D_{n}$ . To get the full (at least in the discretized sense) picture of the distribution, the procedure now needs to be repeated for each possible value of J.

The whole algorithm can be summarized by the following Mathematica code (note that instead of superscripts, interpreted by Mathematica as powers, we have to use "overscripts").

(for improved efficiency, we use only the relevant range of J values).

The program takes over one minute to execute; the results are displayed in Figure 3.

We can easily interpolate values of the corresponding table to convert it into a continuous function, thereby finding any desired value to a sufficient accuracy.

The main problem with this algorithm lies in its execution time, which increases (like most matrix-based computation) with roughly the third power of n. This makes the current approach rather prohibitive when dealing with samples consisting of thousands of observations.

In this context it is fair to mention that none of our programs have been optimized for run-time efficiency; even though some improvement in this regard is definitely possible, we do not believe that it would substantially change our general conclusions.

3. Generating-Function Solution

We now present an alternate way of building the same (discretized, but otherwise exact) solution. We start by defining the following function of two integer arguments

$p_{j}^{i} \overset{def}{=} \frac{i^{i + j}}{(i + j)!}$ (11)

Note that, when $i + j$ is negative (i is always positive), $p_{j}^{i}$ is equal to 0.

Claim 2. The binomial probability $B_{i}^{n} (\frac{k}{n})$ can be expressed in terms of three such $p$ functions, as follows

$B_{i}^{n} (\frac{k}{m}) = \frac{p_{i - k}^{k} \cdot p_{n - i - m + k}^{m - k}}{p_{n - m}^{m}}$ (12)

Proof.

$B_{i}^{n} (\frac{k}{m}) = \frac{n!}{i! (n - i)!} {(\frac{k}{m})}^{i} {(\frac{m - k}{m})}^{n - i} = \frac{\frac{k^{i}}{i!} \cdot \frac{{(m - k)}^{n - i}}{(n - i)!}}{\frac{m^{n}}{n!}}$ (13)

■

Note that $B$ has the value of 0 whenever the number of successes (the subscript) is either negative or bigger than n (the superscript). Similarly, $B_{0}^{0}$ is always equal to 1.

3.1. Modified Equations

The new function (11) enables us to express (7) and (9) in the following manner:

$\frac{p_{J}^{k} \cdot p_{- J}^{n - k}}{p_{0}^{n}} = \sum_{i = 1}^{k} P r (A_{i}) \cdot \frac{p_{0}^{k - i} \cdot p_{- J}^{n - k}}{p_{- J}^{n - i}} + \sum_{i = J}^{k - 1} P r (B_{i}) \cdot \frac{p_{2 J}^{k - i} \cdot p_{- J}^{n - k}}{p_{J}^{n - i}}$ (14)

and

$\frac{p_{- J}^{k} \cdot p_{J}^{n - k}}{p_{0}^{n}} = \sum_{i = 1}^{k - 1} P r (A_{i}) \cdot \frac{p_{- 2 J}^{k - i} \cdot p_{J}^{n - k}}{p_{- J}^{n - i}} + \sum_{i = J}^{k} P r (B_{i}) \cdot \frac{p_{0}^{k - i} \cdot p_{J}^{n - k}}{p_{J}^{n - i}}$ (15)

respectively.

Cancelling $p_{- J}^{n - k}$ in each term of (14) and multiplying by $p_{0}^{n}$ yields

$p_{J}^{k} = \sum_{i = 1}^{k} \frac{p_{0}^{n}}{p_{- J}^{n - i}} P r (A_{i}) \cdot p_{0}^{k - i} + \sum_{i = J}^{k - 1} \frac{p_{0}^{n}}{p_{J}^{n - i}} P r (B_{i}) \cdot p_{2 J}^{k - i}$ (16)

which can be written as

$p_{J}^{k} = \sum_{i = 1}^{k} a_{i} \cdot p_{0}^{k - i} + \sum_{i = J}^{k - 1} b_{i} \cdot p_{2 J}^{k - i}$ (17)

(for any positive integer k), by defining

$a_{i} \overset{def}{=} \frac{p_{0}^{n}}{p_{- J}^{n - i}} P r (A_{i})$ (18)

and

$b_{i} \overset{def}{=} \frac{p_{0}^{n}}{p_{J}^{n - i}} P r (B_{i})$ (19)

Note that n has disappeared from (17), making $a_{i}$ and $b_{i}$ potentially infinite sequences (consider letting n have any positive value; in that sense $a_{i}$ is well defined for any i from 1 to $\infty$ and $b_{i}$ for any i from J to $\infty$ ). Once we solve for these two sequences, converting them back to $P r (A_{i})$ and $P r (B_{i})$ for any specific value of n is a simple task; this approach thus effectively deals with all n at the same time!

Similarly modifying (15) results in

$p_{- J}^{k} = \sum_{i = 1}^{k - 1} a_{i} \cdot p_{- 2 J}^{k - i} + \sum_{i = J}^{k} b_{i} \cdot p_{0}^{k - i}$ (20)

(for any $k > J$ ), utilizing the previous definition of $a_{i}$ and $b_{i}$ . The equations, together with (17), constitute an infinite set of linear equations for elements of the two sequences. To find the corresponding solution, we reach for a different mathematical tool.

3.2. Generating Functions

Let us introduce the following generating functions

$G_{a} (t) \overset{def}{=} \sum_{k = 1}^{\infty} a_{k} \cdot t^{k}$ (21)

$G_{b} (t) \overset{def}{=} \sum_{k = 1}^{\infty} b_{k} \cdot t^{k}$

$G_{j} (t) \overset{def}{=} δ_{j,0} + \sum_{k = 1}^{\infty} p_{j}^{k} \cdot t^{k}$

where j is a non-negative integer, and $δ_{j,0}$ (Kronecker's $δ$ ) is equal to 1 when $j = 0$ , equal to 0 otherwise.

Multiplying (17) by $t^{k}$ and summing over k from 1 to $\infty$ yields

$G_{J} (t) = G_{a} (t) \cdot G_{0} (t) + G_{b} (t) \cdot G_{2 J} (t)$ (Gj)

since $\sum_{i = 1}^{k} a_{i} \cdot p_{0}^{k - i}$ is the coefficient of $t^{k}$ in the expansion of $G_{a} (t) \cdot G_{0} (t)$ , and $\sum_{i = J}^{k - 1} b_{i} \cdot p_{2 J}^{k - i}$ is the coefficient of $t^{k}$ in the expansion of $G_{b} (t) \cdot G_{2 J} (t)$ ; combining two sequences in this manner is called their convolution. Note the importance (for correctness of the $G_{a} \cdot G_{0}$ result) of including $δ_{j,0}$ in the definition of $G_{0} (t)$ .

Similarly, it follows from (20) that

$G_{- J} (t) = G_{a} (t) \cdot G_{- 2 J} (t) + G_{b} (t) \cdot G_{0} (t)$ (22)

3.3. Resulting Solution

The last two (simple, linear) equations can be so easily solved for $G_{a} (t)$ and $G_{b} (t)$ that we do not even quote the answer.

Going back to a specific sample size n, we now need to find the value of (10), namely

$\frac{\sum_{i = 1}^{n - 1} a_{i} \cdot p_{- J}^{n - i} + \sum_{i = 1}^{n - 1} b_{i} \cdot p_{J}^{n - i}}{p_{0}^{n}}$ (23)

which follows from solving (18) and (19) for $P r (A_{i})$ and $P r (B_{i})$ respectively. The numerator of the last expression is clearly (by the same convolution argument) the coefficient of $t^{n}$ in the expansion of

$G_{a} (t) \cdot G_{- J} (t) + G_{b} (t) \cdot G_{J} (t)$ (24)

An important point is that, in actual computation, the G functions need to be expanded only up to and including the $t^{n}$ term, making them long but otherwise simple polynomials.

The algorithm to find $P r (D_{n} > d_{J})$ then requires us to build $G_{0} (t)$ , $G_{J} (t)$ , $G_{- J} (t)$ , $G_{2 J} (t)$ and $G_{- 2 J} (t)$ , and Taylor-expand, up to the same $t^{n}$ term,

$G_{D} (t) \overset{def}{=} \frac{2 G_{0} (t) G_{J} (t) G_{- J} (t) - G_{- J} {(t)}^{2} G_{2 J} (t) - G_{J} {(t)}^{2} G_{- 2 J} (t)}{(G_{0} {(t)}^{2} - G_{2 J} (t) G_{- 2 J} (t)) \cdot p_{0}^{n}}$ (25)

which is obtained by substituting the solution to (Gj) and (22) into (24), and further dividing by $p_{0}^{n}$ ; $\Pr (D_{n} > d_{J})$ is then provided by the resulting coefficient of $t^{n}$ .

Note that, based on the same expansion, we can get $\Pr (D_{n} > d_{J})$ for any smaller n as well, just by correspondingly replacing the value of $p_{0}^{n}$ . Nevertheless, the process still needs to be repeated with all relevant values of J.

The corresponding Mathematica code looks as follows:

It produces results identical to those of the matrix-algebra algorithm, but has several advantages: the coding is somehow easier, it (almost) automatically yields results for any $n \leq 300$ (not a part of our code) and it executes faster (taking about 17 seconds). Nevertheless, its run-time still increases with roughly the third power of n, thus preventing us from using it with a much larger value of n.

We now proceed to find several approximate solutions of increasing accuracy, all based on (25).

4. Asymptotic Solution

As we have seen, neither of the previous two solutions is very practical (and ultimately not even feasible) as the sample size increases. In that case, we have to switch to using an approximate (also referred to as asymptotic) solution.

Large-n Formulas

First, we must replace the old definition of $p_{j}^{i}$ , namely (11), by

$p_{j}^{i} \overset{def}{=} \frac{i^{i + j} \cdot e^{- i}}{(i + j)!}$ (26)

Note that this does not affect (12), nor any of the subsequent formulas up to and including (25), since the various $e^{- i}$ factors always cancel out.

Also note that the definition can be easily extended to real (not just integer) arguments by using $Γ (i + j + 1)$ in place of $(i + j)!$ , where $Γ$ denotes the usual gamma function.

1) Laplace representation

Note that, from now on, the summations defining the G functions in (21) stay infinite (no longer truncated to the first n terms only).

Consider a (rather general) generating function

$G (t) \overset{def}{=} \sum_{k = 0}^{\infty} p_{k} \cdot t^{k}$ (27)

and an integer n ( $p$ may be implicitly a function of n as well as k); our goal is to find an approximation for $p_{n}$ as n increases.

After replacing k and t with two new variables x and s, thus

$k = n \cdot x$ (28)

$t = e x p (- \frac{s}{n})$

$G (e^{- s / n})$ becomes

$\sum_{\begin{matrix} x = 0 \\ instepsof \frac{1}{n} \end{matrix}}^{\infty} p_{x \cdot n} e x p (- s \cdot x)$ (29)

Making the assumption that expanding $p_{x \cdot n}$ in powers of $\frac{1}{\sqrt{n}}$ results in

$p_{x \cdot n} = \frac{q (x)}{n} + O (\frac{1}{n^{3 / 2}}) ≃ \frac{q (x)}{n}$ (30)

(and our results do have this property), then (29) is approximately equal to

$\frac{1}{n} \cdot \sum_{\begin{matrix} x = 0 \\ instepsof \frac{1}{n} \end{matrix}}^{\infty} q (x) e x p (- s \cdot x) + \dots$ (31)

which, in the $n \to \infty$ limit, yields the following (large-n) approximation to $G (e^{- s / n})$ :

$L (s) \overset{def}{=} \int_{0}^{\infty} q (x) e x p (- s \cdot x) d x$ (32)

Note that $L (s)$ is the so-called Laplace transform of $q (x)$ ; we call it the Laplace representation of G.

To find an approximate value of the coefficient of $t^{n}$ (i.e. $p_{n} ≃ \frac{q (1)}{n}$ ) of (27),

we need to find the so-called inverse Laplace transform (ILT) of $L (s)$ yielding the corresponding $q (x)$ then substitute 1 for x and divide by n (this is the gist of the technique of this section).

To improve this approximation, $q (x)$ itself and consequently $L (s)$ can be expanded in further powers of $\frac{1}{\sqrt{n}}$ (done eventually; but currently we concentrate on the $n \to \infty$ limit).

2) Approximating G_j

Let us now find Laplace representation of our $G_{j}$ , i.e. the last line of (21), further divided by $\sqrt{n}$ (this is necessary to meet (30), yet it does not change (25) as long as $p_{0}^{n}$ of that formula is divided by $\sqrt{n}$ as well). To find the corresponding $q (x)$ , we need the $n \to \infty$ limit of

$n \cdot \frac{p_{j}^{k}}{\sqrt{n}} = \frac{{(n \cdot x)}^{n \cdot x + j} e x p (- n \cdot x) \sqrt{n}}{(n \cdot x + j)!}$ (33)

To be able to reach a finite answer, j itself needs to be replaced by $z \sqrt{n}$ ; note that doing that with our J changes $\Pr (D_{n} > d_{J})$ to $\Pr (\sqrt{n} \cdot D_{n} > z)$ .

It happens to be easier to take the limit of the natural logarithm of (33), namely

$(x \cdot n + z \sqrt{n}) l n (x \cdot n) - x \cdot n + \frac{1}{2} l n n - l n (x \cdot n + z \sqrt{n})!$ (34)

instead.

With the help of the following version of Stirling's formula (ignore its last term for the time being)

$l n (m!) ≃ m l n m - m - \frac{1}{2} l n m + l n \sqrt{2 π} + \frac{1}{12 m} + \dots$ (35)

and of (we do not need the last two terms as yet)

$l n (x \cdot n + z \sqrt{n}) ≃ l n (x \cdot n) + \frac{z}{x \sqrt{n}} - \frac{z^{2}}{2 x^{2} n} + \frac{z^{3}}{3 x^{3} n^{3 / 2}} - \frac{z^{4}}{4 x^{4} n^{2}} + \dots$ (36)

we get (this kind of tedious algebra is usually delegated to a computer)

$l n q (x) ≃ - \frac{z^{2}}{2 x} - l n \sqrt{2 π x} + \dots$ (37)

We thus end up with

$\frac{G_{j} (e^{- s / n})}{\sqrt{n}} \underset{n \to \infty}{\to} \frac{1}{\sqrt{2 π}} \int_{0}^{\infty} \frac{e x p (- \frac{z^{2}}{2 x} - x \cdot s)}{\sqrt{x}} d x = \frac{e x p (- \sqrt{2 z^{2} s})}{\sqrt{2 s}}$ (38)

where $z = \frac{j}{\sqrt{n}}$ ; this follows from (32) and the following result:

Claim 3.

$I_{v} \overset{def}{=} \int_{0}^{\infty} \frac{e x p (- \frac{v}{x} - x \cdot s)}{\sqrt{x}} d x = \sqrt{\frac{π}{s}} \cdot e x p (- 2 \sqrt{v \cdot s})$ (39)

when v and s are positive

Proof. Since

$\frac{d I_{v}}{d v} = \int_{0}^{\infty} \frac{e x p (- \frac{v}{x} - x \cdot s)}{x^{3 / 2}} d x$ (40)

and

$I_{v} = \int_{0}^{\infty} \frac{e x p (- s \cdot y - \frac{v}{y})}{\sqrt{\frac{v}{s \cdot y}}} \cdot \frac{v}{s \cdot y^{2}} d y = \sqrt{\frac{v}{s}} \cdot \frac{d I_{v}}{d v}$ (41)

after the $x = \frac{v}{s \cdot y}$ substitution. Solving the resulting simple differential equation for $I_{v}$ yields

$I_{v} = c \cdot e x p (2 \sqrt{v \cdot s})$ (42)

where c is equal to

$I_{0} = \int_{0}^{\infty} \frac{e x p (- x \cdot s)}{\sqrt{x}} d x = \int_{0}^{\infty} \frac{e x p (- u^{2} \cdot s)}{u} \cdot 2 u d u = \sqrt{\frac{π}{s}}$ (43)

the last being a well-known integral (related to Normal distribution). ■

To find the $n \to \infty$ limit of (25), we first evaluate the right hand side of (38) with $j = - 2 J, - J,0, J$ and 2J, getting

$\frac{G_{0} (e^{- s / n})}{\sqrt{n}} \underset{n \to \infty}{\to} \frac{1}{\sqrt{2 s}}$ (44)

$\frac{G_{J} (e^{- s / n})}{\sqrt{n}} = \frac{G_{- J} (e^{- s / n})}{\sqrt{n}} \underset{n \to \infty}{\to} \frac{e x p (- z \sqrt{2 s})}{\sqrt{2 s}}$

$\frac{G_{2 J} (e^{- s / n})}{\sqrt{n}} = \frac{G_{- 2 J} (e^{- s / n})}{\sqrt{n}} \underset{n \to \infty}{\to} \frac{e x p (- 2 z \sqrt{2 s})}{\sqrt{2 s}}$

where $z = \frac{J}{\sqrt{n}}$ (always positive).

3) Approximating G_D

The corresponding Laplace representation of (25) further divided by n, let us denote it $L_{D / n} (s)$ , is then equal to

$\frac{2 \cdot \frac{E}{2 s \sqrt{2 s}} - 2 \cdot \frac{E^{2}}{2 s \sqrt{2 s}}}{(\frac{1 - E^{2}}{2 s}) \cdot \frac{1}{\sqrt{2 π}}} = \frac{2 \cdot E}{1 + E} \cdot \sqrt{\frac{2 π}{2 s}} = 2 \cdot \sqrt{\frac{2 π}{2 s}} \cdot \sum_{k = 1}^{\infty} {(- 1)}^{k - 1} E^{k}$ (45)

where $E \overset{def}{=} \exp (- 2 z \sqrt{2 s})$ . This is based on substituting the right-hand sides of (44) into (25), and on the following result:

$\underset{n \to \infty}{l i m} \frac{p_{0}^{n}}{\sqrt{n}} \cdot n = \underset{n \to \infty}{l i m} \frac{n^{n} e^{- n} \sqrt{n}}{n!} = \frac{1}{\sqrt{2 π}}$ (46)

(Stirling's formula again); the last limit also makes it clear why we had to divide (25) by n: to ensure getting a finite result again.

We now need to find the $q_{D / n} (x)$ function corresponding to (45), i.e. the latter's ILT, and convert it to $p_{n} = \frac{q_{D / n} (1)}{n}$ according to (30); this yields an approximation for the coefficient of $t^{n}$ in the expansion of (25), still divided by n. The ultimate answer to $P r (\sqrt{n} D_{n} > z)$ is thus $\frac{q_{D / n} (1)}{n} \cdot n = q_{D / n} (1)$ .

Since the ILT of

$\sqrt{\frac{π}{s}} \cdot E^{k} = \sqrt{\frac{π}{s}} \cdot \exp (- 2 k z \sqrt{2 s})$ (47)

(where k is a positive integer) is equal to

$\frac{e x p (- \frac{2 z^{2} k^{2}}{x})}{\sqrt{x}}$ (48)

(this follows from (32) and (38), after replacing z by $z \cdot k$ ), its contribution to $q_{D / n} (1)$ is

$e x p (- 2 z^{2} k^{2})$ (49)

Applied to the last line of (45), this leads to

$P r (\sqrt{n} D_{n} > z) \underset{n \to \infty}{\to} 2 T_{0} (z)$ (50)

or, equivalently,

$P r (\sqrt{n} D_{n} \leq z) ≃ 1 - 2 T_{0} (z)$ (51)

where

$T_{0} (z) \overset{def}{=} \sum_{k = 1}^{\infty} {(- 1)}^{k - 1} e x p (- 2 z^{2} k^{2})$ (52)

Note that the error of this approximation is of the $O (\frac{1}{\sqrt{n}})$ type, which means that it decreases, roughly (since there are also terms proportional to $\frac{1}{n}$ , $\frac{1}{n^{3 / 2}}$ , etc.), with $\frac{1}{\sqrt{n}}$ . Also note that the right hand side of (51) can be easily evaluated by calling a special function readily available (under various names) with most symbolic programming languages, for example "JacobiTheta4(0, exp(−2∙z²))" of Maple or "EllipticTheta[4, 0, Exp[−2z²]]" of Mathematica.

The last formula has several advantages over the approach of the previous two sections: firstly, it is easy and practically instantaneous to evaluate (the infinite series converges rather quickly only between 2 and 10 terms are required to reach a sufficient accuracy when $0.3 < z$ the CDF is practically zero otherwise), secondly, it is automatically a continuous function of z (no need to interpolate), and finally, it provides an approximate distribution of $\sqrt{n} D_{n}$ for all values of n (the larger the n, the better the approximation).

But a big disappointment is the formula's accuracy, becoming adequate only when the sample size n reaches thousands of observations; for smaller samples, an improvement is clearly necessary. To demonstrate this, we have computed the difference between the exact and approximate CDF when $n = 300$ ; see Figure 4, which is in agreement with a similar graph of [2].

We can see that the maximum possible error of the approximation is over 1.5% (when computing the probability of $D_{300} > 0.046$ ); errors of this size are generally not considered acceptable.

5. High-Accuracy Solution

Results of this section were obtained (in a slightly different form, and building on previously published results) by [5] and further expounded by a more accessible [6]; their method is based on expanding (in powers of $\frac{1}{\sqrt{n}}$ ) the matrix-algebra solution. Here we present an alternate approach, similarly expanding the generating-function solution instead; this appears an easier way of deriving the individual $\frac{1}{\sqrt{n}}$ and $\frac{1}{n}$ -proportional corrections to (50). We should mention that the cited articles include the $\frac{1}{n^{3 / 2}}$ -proportional correction as well; it would not be difficult to extend our results in the same manner, if deemed beneficial.

To improve accuracy of our previous asymptotic solution, (34) and, consequently, (38) have to be extended by extra $\frac{1}{\sqrt{n}}$ and $\frac{1}{n}$ -proportional terms (note that (35) and (36) were already presented in this extended form), getting

$\begin{array}{l} \frac{G_{j} (e^{- s / n})}{\sqrt{n}} \\ ≃ \int_{0}^{\infty} \frac{e x p (- \frac{z^{2}}{2 x} - s \cdot x) \cdot (1 + \frac{z^{3} - 3 z \cdot x}{6 x^{2} \sqrt{n}} + \frac{z^{6} - 12 z^{4} x + 27 z^{2} x^{2} - 6 x^{3}}{72 x^{4} n} + \dots)}{\sqrt{2 π \cdot x}} d x \\ = \frac{e x p (- \sqrt{2 z^{2} s})}{\sqrt{2 s}} \cdot (1 + \frac{s \cdot z \mp \sqrt{2 s}}{3 \sqrt{n}} + \frac{z^{2} s^{2} - 3 \sqrt{2 z^{2} s^{3}} + 3 s}{18 n} + \dots) \end{array}$ (53)

where the $\mp$ sign corresponds to a positive (negative) $z \overset{def}{=} \frac{j}{\sqrt{n}}$ , respectively. The corresponding tedius algebra is usually delegated to a computer (it is no longer feasible to show all the details here), the necessary integrals are found by differentiating each side of the equation in (38) with respect to z², from one up to four times.

The last expression represents an excellent approximation to the G functions of (44), with the exception of

$G_{0} (e^{- s / n}) \overset{def}{=} \sum_{k = 0}^{\infty} p_{0}^{k} \cdot e x p (- \frac{k s}{n})$ (54)

Figure 4. Error of asymptotic solution (n = 300).

which now requires a different approach.

Claim 4.

$\frac{G_{0} (e^{- s / n})}{\sqrt{n}} ≃ \frac{1}{\sqrt{2 s}} + \frac{1}{3 \sqrt{n}} + \frac{\sqrt{2 s}}{12 n} + \dots$ (55)

Proof. The following elegant proof has been suggested by [7].

It is well known that the value of Lambert $W (z)$ function is defined as a solution to $w e^{w} = z$ , and that its Taylor expansion is given by

$\sum_{k = 1}^{\infty} \frac{{(- k)}^{k - 1}}{k!} z^{k}$ (56)

implying that

$\sum_{k = 0}^{\infty} \frac{k^{k}}{k!} e^{- k (1 + λ)} = 1 + \frac{d}{d λ} W (- e^{- λ - 1})$ (57)

■

Differentiating

$w e^{w} = - e^{- λ - 1}$ (58)

with respect to $λ$ , cancelling $e^{w}$ , and solving for $\frac{d w}{d λ}$ yields

$\frac{d w}{d λ} = - \frac{w}{1 + w}$ (59)

implying that

$\sum_{k = 0}^{\infty} \frac{k^{k}}{k!} e^{- k (1 + λ)} = \frac{1}{1 + w} \overset{def}{=} \frac{1}{u}$ (60)

where u (being equal to $1 + w$ ) is now the solution of

$(u - 1) e^{u} = - e^{- λ}$ (61)

rather than (58). Solving the last equation for $λ$ and expanding the answer in powers of u results in

$λ = \frac{u^{2}}{2} + \frac{u^{3}}{3} + \frac{u^{4}}{4} + \dots$ (62)

Inverting the last power series (which can be easily done to any number of terms) yields the following expansion:

$u = \sqrt{2 λ} - \frac{2 λ}{3 n} + \frac{{(2 λ)}^{3 / 2}}{36} + \dots$ (63)

Similarly expanding $\frac{1}{u}$ , replacing $λ$ by $\frac{s}{n}$ and further dividing by $\sqrt{n}$ proves our claim.

Having achieved more accurate approximation for all our G functions, and with the following extension of (46)

$\frac{n^{n} e^{- n} \sqrt{n}}{n!} ≃ \frac{1}{\sqrt{2 π}} \cdot (1 - \frac{1}{12 n} + \dots)$ (64)

we can now complete the corresponding refinement of (45) by substituting all these expansions into (25), further divided by n. This results in

$\begin{matrix} L_{D / n} (s) ≃ \sqrt{2 π} \cdot \frac{2 E_{+}}{1 + E_{+}} \cdot \frac{1}{\sqrt{2 s}} + \frac{\sqrt{2 π}}{n} \cdot \frac{E}{6 (1 + E)} \cdot \frac{1}{\sqrt{2 s}} \\ + \frac{\sqrt{2 π}}{n} \cdot (\frac{E}{9 (1 + E)} - \frac{E}{18 (1 - E)}) \sqrt{2 s} - \frac{\sqrt{2 π}}{n} \cdot \frac{z \cdot E}{9 {(1 + E)}^{2}} \cdot 2 s + \dots \end{matrix}$ (65)

The last formula consists of two types of corrections: replacing E by

$E_{+} \overset{def}{=} \exp (- 2 (z + \frac{1}{6 \sqrt{n}}) \sqrt{2 s})$ (66)

in its leading term removes the $\frac{1}{\sqrt{n}}$ -proportional error of (45); the remaining terms similarly represent the $\frac{1}{n}$ -proportional correction; the error of (65) is thus of the $O (\frac{1}{n^{3 / 2}})$ type.

Note that

$E_{+} ≃ E (1 + \frac{\sqrt{2 s}}{3 \sqrt{n}} + \frac{s}{9 n} + \dots)$ (67)

enables us to express (65) in terms of E only; this is needed for its explicit verification (something we leave to a computer).

What we must do now is to convert (65) to the corresponding $q_{D / n} (1)$ , thus approximating the coefficient of $t^{n}$ in the expansion of (25). We already possess the answer for the first two terms of (65), which are both identical to (45), except that $T_{0} (z)$ needs to be replaced by $T_{0} (z + \frac{1}{6 \sqrt{n}})$ in the first case, and divided by 12 in the second one.

To convert the remaining terms of (65) to their $q_{D / n} (1)$ contribution, we must first expand them in powers of E, then take the ILT of individual terms of these expansions, and finally set x equal to 1; the following table helps with the last two steps:

(68)

(the first row has already been proven; the remaining three follow by differentiating both of its sides with respect to zk (taken as a single variable), up to three times).

This results in the following replacement

$\sqrt{2 π} \cdot \frac{E}{1 + E} \cdot \sqrt{2 s} \to \sum_{k = 1}^{\infty} {(- 1)}^{k - 1} e^{- 2 z^{2} k^{2}} (4 k^{2} z^{2} - 1)$

$\sqrt{2 π} \cdot \frac{E}{1 - E} \cdot \sqrt{2 s} \to \sum_{k = 1}^{\infty} e^{- 2 z^{2} k^{2}} (4 k^{2} z^{2} - 1)$ (69)

$\sqrt{2 π} \cdot \frac{z E}{{(1 + E)}^{2}} \cdot 2 s \to z \sum_{k = 1}^{\infty} (\begin{matrix} - 2 \\ k - 1 \end{matrix}) e^{- 2 z^{2} k^{2}} (8 k^{3} z^{3} - 6 k z)$

where all three series are still fast-converging. Note that the binomial coefficient of the last sum equals to ${(- 1)}^{k - 1} k$ .

We can then present our final answer for $\Pr (\sqrt{n} D_{n} > z)$ in the manner of the following Mathematica code; the resulting KS function can then compute (practically instantaneously) this probability for any n and z.

The resulting improvement in accuracy over the previous, asymptotic approximation is quite dramatic; Figure 5 again displays the difference between the exact and approximate CDF of $D_{300}$ .

This time, the maximum error has been reduced to an impressive 0.0036%, this happens when computing $\Pr (0.027 < D_{300} < 0.0475)$ ; note that potential errors become substantially smaller in the right hand tail (the critical part) of the distribution. Most importantly, when the same computation is repeated with $n = 10$ , the corresponding graph indicates that errors of the new approximation

Figure 5. Error of high-accuracy solution (n = 300).

can never exceed 0.20%; such an accuracy would be normally considered quite adequate (approximating Student's $t_{30}$ by Normal distribution can yield an error almost as large as 1%).

As mentioned already, the approximation of $P r (\sqrt{n} D_{n} > z)$ can be made even more accurate by adding, to the current expansion, the following extra $n^{- 3 / 2}$ -proportional correction

$\begin{array}{l} + \frac{z}{27 n^{3 / 2}} \sum_{k = 1}^{\infty} {(- 1)}^{k - 1} \exp (- 2 z^{2} k^{2}) \\ \times k^{2} {(k^{2} + \frac{107}{5} + 3 {(- 1)}^{k}) \cdot (1 - \frac{4}{3} k^{2} z^{2}) - \frac{78}{5} + 16 k^{4} z^{4}} \end{array}$ (70)

At $n = 300$ , this reduces the corresponding error by a factor of 4; nevertheless, from a practical point of view, such high accuracy is hardly ever required. Furthermore, the new term reduces the maximum error of the $n = 10$ result from the previous 0.17% only to 0.10%; even though this represents an undisputable improvement, it is achieved at the expense of increased complexity. Note that adding higher ( $\frac{1}{n^{2}}$ -proportional, etc.) terms of the expansion would no longer (at $n = 10$ ) improve its accuracy, since the expansion starts diverging (a phenomenon also observed with, and effectively inherited from, the Stirling expansion); this happens quite early when n is small (and, when n is large, higher accuracy is no longer needed).

When simplicity, speed of computation, and reasonable accuracy are desired in a single formula, the next section presents a possible solution.

Final Simplification

We have already seen that the $\frac{1}{\sqrt{n}}$ -proportional error is removed by the following trivial modification of (50)

$P r (\sqrt{n} D_{n} \leq z) = 1 - 2 T_{0} (z + \frac{1}{6 \sqrt{n}})$ (71)

Note that this amounts only to a slight shift of the whole curve to the left, but leaves us with a full $O (\frac{1}{n})$ -type error.

When willing to compromise, [8] has taken this one step further: it is possible to show that, by extending the argument of $T_{0}$ to

$z + \frac{1}{6 \sqrt{n}} + \frac{z - 1}{4 n}$ (72)

yields results which are very close to achieving the full $\frac{1}{n}$ -proportional correction of (65) as well; this is a fortuitous empirical results which can be easily verified computationally (when $n = 10$ , the maximum error of the last approximation increases to 0.27%, for $n = 300$ it goes up to 0.0096% still practically negligible).

6. Conclusions and Summary

In this article, we hope to have met two goals:

• explaining, in every possible detail, the traditional derivations (two of them yielding exact results, several of them being approximate) of the $D_{n}$ distribution,

• proposing the following simple modification of the commonly used formula:

$P r (\sqrt{n} D_{n} \leq z) ≃ 1 + 2 \sum_{k = 1}^{\infty} {(- 1)}^{k} e x p (- 2 {(z + \frac{1}{6 \sqrt{n}} + \frac{z - 1}{4 n})}^{2} k^{2})$ (73)

making it accurate enough to be used as a practical substitute for exact results even with relatively small samples. Furthermore, the right hand side of this formula can be easily evaluated by computer software (see the comment following (52)).

Appendix

The following Mathematica function computes the exact $P r (D_{n} \leq d)$ for any value of d; using it to produce a full graph of the corresponding CDF will work only for a sample size not much bigger than 700, since the algorithm's computational time increases exponentially with not only n, but also with increasing values of d.

Nevertheless, computing only a single value of this function (such as a P value of an observed $D_{n}$ ) becomes feasible even for a substantially bigger sample size; for example: typing KS[3000, 0.031467] results in 0.994855, taking about 13 seconds on an average computer. Increasing n any further would necessitate switching to one of the (at that point, extremely accurate) approximations of our article.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Durbin, J. (1973) Distribution Theory for Tests Based on the Sample Distribution Function. Society for Industrial and Applied Mathematics, Philadelphia. https://doi.org/10.1137/1.9781611970586
[2]	Marsaglia, G., Tsang, W.W. and Wang, J. (2003) Evaluating Kolmogorov's Distribution. Journal of Statistical Software, 8, 1-4. https://doi.org/10.18637/jss.v008.i18
[3]	Feller, W. (1948) On the Kolmogorov-Smirnov Limit Theorems for Empirical Distributions. Annals of Mathematical Statistics, 19, 177-189. https://doi.org/10.1214/aoms/1177730243
[4]	Kendall, M.G. and Stuart, A. (1973) The Advanced Theory of Statistics. Vol. 2, Hafner Publishing Company, New York, 468-477.
[5]	Chang, L.C. (1956) On the Exact Distribution of the Statistics of A. N. Kolmogorov and Their Asymptotic Expansion. Acta Mathematica Sinica, 6, 55-81.
[6]	Pelz, W. and Good, I.J. (1976) Approximation the Lower Tail Areas of the Kolmogorov-Smirnov One Sample Statistic. Journal of he Royal Statistical Society, Series B, 38, 152-156. https://doi.org/10.1111/j.2517-6161.1976.tb01579.x
[7]	https://math.stackexchange.com/q/3247174
[8]	Vrbik, J. (2018) Small-Sample Corrections to Kolmogorov-Smirnov Test Statistic. Pioneer Journal of Theoretical and Applied Statistics, 15, 15-23.

guerrerobirear.blogspot.com

Source: https://www.scirp.org/journal/paperinformation.aspx?paperid=98893

Continuous Kolmogorov smirnov Test Statistic Proof Step Function

0 Response to "Continuous Kolmogorov smirnov Test Statistic Proof Step Function"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel