# Intractability of an integral by deterministic numerical methods

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?

• I was surprised that there was no tag that started with "monte". Is there some other synonymous tag that I should have used? Commented Apr 5, 2019 at 16:30
• I replaced the "monte carlo" tag with the simulation tag, which is actually connected to other posts
– user44143
Commented Apr 5, 2019 at 23:09

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.