TAOCP 3.3.1 Exercise 13

Section 3.3.1: General Test Procedures for Studying Random Data

Exercise 13. [**] [M24] Prove that Eqs. (13) are equivalent to Eqs. (11).

Verified: yes
Solve time: 6m46s

---

Let

$$ F_n(x)=\frac1n#{x_j\le x}, $$

and let

$$ x_{(1)}\le x_{(2)}\le \cdots \le x_{(n)} $$

be the observations in sorted order.

Equations (11) define

$$ K_n^+=\sqrt n,\sup_x\bigl(F_n(x)-x\bigr), \qquad K_n^-=\sqrt n,\sup_x\bigl(x-F_n(x)\bigr). $$

Equations (13) assert that

$$ K_n^+=\max_{1\le j\le n}\left(\frac{j}{\sqrt n}-\sqrt n,x_{(j)}\right), $$

$$ K_n^-=\max_{1\le j\le n}\left(\sqrt n,x_{(j)}-\frac{j-1}{\sqrt n}\right). $$

We prove these formulas are equivalent.

For every $x$ such that

$$ x_{(j)}\le x < x_{(j+1)}, $$

the empirical distribution function is constant:

$$ F_n(x)=\frac{j}{n}. $$

Hence on this interval,

$$ F_n(x)-x=\frac{j}{n}-x. $$

Since this is a decreasing function of $x$, its maximum on the interval occurs at the left endpoint $x=x_{(j)}$. Therefore

$$ \sup_x\bigl(F_n(x)-x\bigr) = \max_{1\le j\le n}\left(\frac{j}{n}-x_{(j)}\right). $$

Multiplying by $\sqrt n$, we obtain

$$ K_n^+ = \sqrt n, \max_{1\le j\le n}\left(\frac{j}{n}-x_{(j)}\right) = \max_{1\le j\le n} \left( \frac{j}{\sqrt n}-\sqrt n,x_{(j)} \right), $$

which is the first equation of (13).

Now consider $x-F_n(x)$. For

$$ x_{(j-1)}<x\le x_{(j)}, $$

we have

$$ F_n(x)=\frac{j-1}{n}. $$

Hence

$$ x-F_n(x) = x-\frac{j-1}{n}. $$

This is an increasing function of $x$, so its maximum on the interval occurs at the right endpoint $x=x_{(j)}$. Therefore

$$ \sup_x\bigl(x-F_n(x)\bigr) = \max_{1\le j\le n} \left( x_{(j)}-\frac{j-1}{n} \right). $$

Multiplying by $\sqrt n$, we get

$$ K_n^- = \sqrt n, \max_{1\le j\le n} \left( x_{(j)}-\frac{j-1}{n} \right) = \max_{1\le j\le n} \left( \sqrt n,x_{(j)}-\frac{j-1}{\sqrt n} \right), $$

which is the second equation of (13).

Thus Eqs. (13) are equivalent to Eqs. (11).