Kolmogorov Smirnov p-values not uniform under the null in R?

Question

It is well known that the distribution of the p-value in a statistical test is $U(0,1)$ under the null. Now, consider the following implementation of the two-samples Kolmogorov Smirnov test on normal samples:

K = 1e4
n = 100
p.val = sapply(1:K,FUN = function(x) ks.test(rnorm(n),rnorm(n),exact=TRUE)$p.value)
mean(p.val<0.05)
plot(p.val,main = 'Plot of p.val')
hist(p.val,freq=FALSE)

p.val is far from being uniformly distributed and takes only discrete values. In addition, the proportion of p.val < 0.05 does not seem to be 0.05, but slightly less, around 0.037 during my testings.

What is going on here? In the 1 sample case, we get the results as expected though, this problems is specific to the two-samples case.

EDIT: The problem lies in the fact that the p-value is not uniformly distributed under null in general. Thanks @whuber for pointing it out.

Let $\boldsymbol{X}^n = (X_1, \dots, X_n)$ be a vector of observation. In general a statistical test at level $\alpha \in (0,1)$ has the form:

\begin{equation} \phi_{\alpha} = 1_{T(\boldsymbol{X}^n) \in \mathcal{R}_{\alpha}} \end{equation} Where $T$ is a real functional of the observations and $\mathcal{R}_{\alpha}$ is the critical region, i.e. $\mathcal{R}_{\alpha} \subset \mathbb{R}$ such that $\mathbb{P}(T(\boldsymbol{X}^n) \in \mathcal{R}_{\alpha}) \leq \alpha$ under the null hypothesis. Now let $P$ be the p-value of the test, i.e. by definition: \begin{equation} P = \inf \{x \in (0,1) | \phi_{x} = 1\}. \end{equation} Then for any $\alpha \in (0,1)$ we have: \begin{align} \mathbb{P}(P \leq \alpha) &= \mathbb{P}(\inf \{x \in (0,1) | \phi_{x} = 1\} \leq \alpha)\\ & = \mathbb{P}(\phi_{\alpha} = 1). \end{align} The last equation is because the two events $\{ \inf \{x \in (0,1) | \phi_{x} = 1\} \leq \alpha \}$ and $\{ \phi_{\alpha} = 1 \}$ are equal. But under the null, the only guarantee is that $\mathbb{P}(\phi_{\alpha} = 1) \leq \alpha$, i.e. that $\mathbb{P}(P \leq \alpha) \leq \alpha$, hence $P$ is not uniform in general.

In order to get uniformly distributed p-values, the familly $\{\phi_{\alpha}|0\leq \alpha \leq 1\}$ must be exactly of level $\alpha$ (in the sense the the type I error must be exactly $\alpha$) the distribution of the test statistic must be absolutely continuous and the null must be simple. Because the 2-samples KS test has discret test statistic, the p-value cannot be uniformly distributed.

Answer 1

It is not surprising that when dealing with a two sample test with a fairly small sample size (100), the test statistic (and thus the p-value) takes on discrete values. Increasing n (and decreasing K to reduce computational time) leads to a less discontinuous distribution.

As whuber pointed out in the comments, the fact that the p-value is obligately discrete leads to unusually high histogram bars. The apparent skew in the distribution is an artefact of the bins used to construct it and the discrete values possible for the test statistic in the low n setting.

K = 1000
n = 1000
p.val = sapply(1:K,FUN = function(x) ks.test(rnorm(n),rnorm(n),exact=TRUE)$p.value)
mean(p.val<0.05)
#> [1] 0.055
plot(p.val,main = 'Plot of p.val')

hist(p.val,freq=FALSE, breaks = "FD")

^{Created on 2019-10-15 by the reprex package (v0.3.0)}