Approaches to biomedical knowledge

The Kolmogorov–Smirnov (KS) test

Suppose that we have an i.i.d. sample \(X_1,\ldots , X_n\) with some unknown distribution \(\mathbb{P}\) and we would like to test the hypothesis that \(\mathbb{P}\) is equal to a particular distribution \(\mathbb{P}_0\), i.e. decide between the following hypotheses:

\[ \begin{aligned} H_0 : \mathbb{P} &= \mathbb{P}_0 \\ H_1 : \mathbb{P} & \neq \mathbb{P}_0 \\ \end{aligned} \]

The KS test is a non-parametric¹ method for comparing probability distributions and checking if two samples differ significantly.

The question

• We have a sample \(x_1, \dots, x_n\).
• One-sample question: could it have come from a specified distribution \(F\) (for example \(N(0,1)\))?
• Two-sample question: could two samples come from the same distribution?
• Chi-square tests require binning the data. The KS test works on the raw values, with no binning.
• Both questions are answered by comparing cumulative distribution functions.

The empirical CDF (ECDF)

The ECDF is the fraction of \(n\) ordered observations at or below \(x\):

\[F_n(x) = \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{x_i \le x\}\]

It is a step function that jumps by \(1/n\) at each data point and rises from 0 to 1.

The test statistic

\[D_n = \sup_x \left| F_n(x) - F(x) \right|\]

\(D_n\) is the largest vertical gap between the ECDF and the hypothesized CDF.

• \(D_n\) is always between 0 and 1.
• Small \(D_n\): the sample looks like \(F\).
• Large \(D_n\): the sample is far from \(F\), so we reject.
• The largest gap can occur anywhere along the distribution.

Computing \(D_n\) by hand

The ECDF is a step function and \(F\) is continuous, so the largest gap occurs at a data point, either just before or just after a jump. We must check both:

• Just after the jump (ECDF is above \(F\)): \(D_n^+ = \max_i \left(\tfrac{i}{n} - F(x_{(i)})\right)\)
• Just before the jump (ECDF is below \(F\)): \(D_n^- = \max_i \left(F(x_{(i)}) - \tfrac{i-1}{n}\right)\)

\[D_n = \max(D_n^+,\, D_n^-)\]

What would \(D_n\) look like if \(H_0\) were true?

Simulate 10,000 samples of size \(n = 30\) from \(N(0,1)\) and compute \(D_n\) for each:

The p-value is the fraction of this null distribution at least as large as the observed \(D_n\).

How \(D_n\) scales with \(n\)

Under \(H_0\), \(D_n\) shrinks like \(1/\sqrt{n}\).¹ The scaled quantity \(\sqrt{n}\, D_n\) has (approximately) the same distribution for every \(n\). This is the Kolmogorov distribution.

n=  30  95th pct of D_n = 0.241   95th pct of sqrt(n)*D_n = 1.322
n= 120  95th pct of D_n = 0.122   95th pct of sqrt(n)*D_n = 1.338

At \(\alpha = 0.05\), the asymptotic critical value is

\[D_{n,\,0.05} \approx \frac{1.36}{\sqrt{n}}\]

• In practice, software computes the p-value (scipy.stats.kstest or R’s ks.test).

Under an alternative

Sample from \(N(0.5, 1)\) and test against \(N(0,1)\):

KstestResult(statistic=np.float64(0.4050996543021373), pvalue=np.float64(5.826477046905052e-05), statistic_location=np.float64(0.35427336756472355), statistic_sign=np.int8(-1))

• The ECDF lies below the null CDF, because the sample is shifted right.
• For a pure location shift, the gap is largest near the middle of the distribution, where the CDF is steepest.

The two-sample test

Compare two samples directly with no hypothesized \(F\):

\[D_{n,m} = \sup_x \left| F_{1,n}(x) - F_{2,m}(x) \right|\]

KstestResult(statistic=np.float64(0.145), pvalue=np.float64(0.6860480075289528), statistic_location=np.float64(-0.06437262729863982), statistic_sign=np.int8(1))

The rejection threshold uses the effective sample size \(nm/(n+m)\), in place of \(n\).

Summary

• The KS test compares an ECDF with a CDF, or two ECDFs with each other.
• \(D_n\) is the largest vertical gap.
• Under \(H_0\), \(\sqrt{n}\, D_n\) has a fixed distribution, so we can assign a p-value.
• Use scipy.stats.kstest or ks_2samp (R: ks.test).
• Remember the pitfalls: continuous data, estimated parameters, and tail sensitivity.

References: * NIST Engineering Statistics Handbook §1.3.5.16 MIT OCW 18.443, Lecture 14.