Intractability of an integral by deterministic numerical methods

Question

Suppose $X_1,\ldots,X_n$ is an i.i.d. sample from a probability distribution with continuous c.d.f. $F.$ Let $F_n$ be the empirical c.d.f. $$ F_n(x) = \frac 1 n \sum_{k=1}^n \mathbf 1_{X_n\le x} = \frac{\text{how many of }X_1,\ldots,X_n \text{ are} \le x} n. $$ Let \begin{align} D_n & = \sup \left\{ |F(x) - F_n(x)| : x\in\mathbb R \right\} \tag 1 \\[4pt] & = \text{the maximum discrepancy statistic.} \end{align} The probability distribution of $D_n$ does not depend on which continuous c.d.f. $F$ is involved. This is the Kolmogorov–Smirnov distribution.

Now suppose $X_1\sim N(\mu,\sigma^2)$ and they're still i.i.d. and instead of $F$ in line $(1)$ above, you put \begin{align} \widehat F_n = {} & \text{the c.d.f. of the normal} \\[4pt] & \text{distribution with expectation} \\[6pt] & \overline X = (X_1+\cdots+X_n)/n \\[6pt] & \text{and variance } \frac 1 {n-1} \sum_{k=1}^n (X_i -\overline X)^2. \end{align} The maximum discrepancy statistic then becomes stochastically smaller. Its distribution becomes the Lilliefors distribution.

Wikipedia says that values of the c.d.f. of the Lilliefors distribution have been computed only by Monte Carlo methods.

Is there some proof that no deterministic numerical method can do this efficiently?

Answer 1

For small $n$ Monte Carlo integration is not needed. For $n$ up to 100 see Kolmogorov-Smirnov Tests when Parameters are Estimated with Applications to Tests of Exponentiality and Tests on Spacings (table 3).

These exact results were used to construct the Graphs for Use with the Lilliefors Test for Normal and Exponential Distributions. There are also analytical approximations, see An Analytic Approximation to the Distribution of Lilliefors’s Test Statistic for Normality.