# 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? – Michael Hardy Apr 5 '19 at 16:30
• I replaced the "monte carlo" tag with the simulation tag, which is actually connected to other posts – Matt F. Apr 5 '19 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).