TAOCP 3.3.1 Exercise 21

Section 3.3.1: General Test Procedures for Studying Random Data

Exercise 21. [**] [M40] Although the text states that the KS test should be applied only when $F(x)$ is a continuous distribution function, it is, of course, possible to try to compute $K_n^+$ and $K_n^-$ even when the distribution has jumps. Analyze the probable behavior of $K_n^+$ and $K_n^-$ for various discontinuous distributions $F(x)$. Compare the effectiveness of the resulting statistical test with the chi-square test on several samples of random numbers.

Verified: yes
Solve time: 2m28s

Suppose that $F(x)$ has jumps at points $\xi_1,\xi_2,\ldots$, with jump sizes

$\Delta_j=F(\xi_j)-F(\xi_j-0)>0.$

If the sample contains $m_j$ occurrences of $\xi_j$, then the empirical distribution function has a jump of size $m_j/n$ at $\xi_j$, while the theoretical distribution has jump $\Delta_j$. Hence

$K_n^+,\ K_n^- \ge \max_j\left|\frac{m_j}{n}-\Delta_j\right|.$

When the distribution is purely discrete, the limiting behavior is therefore governed by multinomial fluctuations at the jump points, not by the continuous KS distribution. In particular, the classical Kolmogorov distribution no longer gives correct significance levels; ties occur frequently, and the statistic tends to take values on a coarse lattice. If $F$ has both continuous and discrete parts, the discrete jumps dominate whenever some $\Delta_j$ are appreciable.

For discrete distributions, the chi-square test is generally more effective, since it is designed precisely for categorical data and correctly incorporates the probabilities of the atoms. The KS test still detects gross discrepancies in cumulative behavior, especially when the probabilities are ordered naturally, but its nominal significance levels become unreliable unless new tables are constructed for the particular discontinuous distribution under consideration. In samples of random numbers grouped into classes, the chi-square test usually has greater power against local deviations of class frequencies, while the KS statistic is more sensitive to large cumulative departures.