TAOCP 3.3.1 Exercise 5

Let the observations be arranged in increasing order: \begin{aligned} X_{(1)}&=0.

taocpmathematicsalgorithmsvolume-2medium

Section 3.3.1: General Test Procedures for Studying Random Data

Exercise 5. [22] Let $F(x)$ be the uniform distribution, Fig. 3(b). Find $K_{20}^+$ and $K_{20}^-$ for the following 20 observations:

0.14, 0.732, 0.442, 0.162, 0.259, 0.442, 0.189, 0.693, 0.698, 0.302, 0.442, 0.434, 0.141, 0.017, 0.318, 0.869, 0.772, 0.678, 0.354, 0.718,

and state whether these observations are significantly different from the expected behavior with respect to either of these two tests.

Verified: yes
Solve time: 10m02s

Solution

Let the observations be arranged in increasing order:

$$ \begin{aligned} X_{(1)}&=0.017, & X_{(2)}&=0.140, & X_{(3)}&=0.141, & X_{(4)}&=0.162,\ X_{(5)}&=0.189, & X_{(6)}&=0.259, & X_{(7)}&=0.302, & X_{(8)}&=0.318,\ X_{(9)}&=0.354, & X_{(10)}&=0.434, & X_{(11)}&=0.442, & X_{(12)}&=0.442,\ X_{(13)}&=0.442, & X_{(14)}&=0.678, & X_{(15)}&=0.693, & X_{(16)}&=0.698,\ X_{(17)}&=0.718, & X_{(18)}&=0.732, & X_{(19)}&=0.772, & X_{(20)}&=0.869. \end{aligned} $$

Since $F(x)$ is the uniform distribution on $[0,1]$,

$$ F(x)=x. $$

The one-sided Kolmogorov-Smirnov statistics are

$$ K_n^+=\max_{1\le i\le n}\left(\frac{i}{n}-X_{(i)}\right), \qquad K_n^-=\max_{1\le i\le n}\left(X_{(i)}-\frac{i-1}{n}\right). $$

For $n=20$, compute the relevant differences.

Computation of $K_{20}^+$

$$ \frac{i}{20}-X_{(i)} $$

gives:

$$ \begin{array}{c|c} i & \frac{i}{20}-X_{(i)}\ \hline 1&0.033\ 2&-0.040\ 3&0.009\ 4&0.038\ 5&0.061\ 6&0.041\ 7&0.048\ 8&0.082\ 9&0.096\ 10&0.066\ 11&0.108\ 12&0.158\ 13&0.208\ 14&0.022\ 15&0.057\ 16&0.102\ 17&0.132\ 18&0.168\ 19&0.178\ 20&0.131 \end{array} $$

The maximum occurs at $i=13$:

$$ K_{20}^+=0.65-0.442=0.208. $$

Hence

$$ \boxed{K_{20}^+=0.208}. $$

Computation of $K_{20}^-$

$$ X_{(i)}-\frac{i-1}{20} $$

gives:

$$ \begin{array}{c|c} i & X_{(i)}-\frac{i-1}{20}\ \hline 1&0.017\ 2&0.090\ 3&0.041\ 4&0.012\ 5&-0.011\ 6&0.009\ 7&0.002\ 8&-0.032\ 9&-0.046\ 10&-0.016\ 11&-0.058\ 12&-0.108\ 13&-0.158\ 14&0.028\ 15&-0.007\ 16&-0.052\ 17&-0.082\ 18&-0.118\ 19&-0.128\ 20&-0.081 \end{array} $$

The maximum occurs at $i=2$:

$$ K_{20}^-=0.140-0.050=0.090. $$

Therefore

$$ \boxed{K_{20}^-=0.090}. $$

Significance

For $n=20$, the 5% one-sided Kolmogorov-Smirnov critical value is approximately

$$ \frac{1.22}{\sqrt{20}} \approx 0.273. $$

Comparing:

$$ K_{20}^+=0.208<0.273, $$

$$ K_{20}^-=0.090<0.273. $$

Neither statistic exceeds the critical value.

Therefore the observations are not significantly different from the uniform distribution with respect to either one-sided Kolmogorov-Smirnov test.

$$ \boxed{K_{20}^+=0.208,\qquad K_{20}^-=0.090.} $$

$$ \boxed{\text{No significant deviation from uniformity is detected by either test.}} $$