TAOCP 3.3.2 Exercise 27

Section 3.3.2: Empirical Tests

Exercise 27. ▶ [HM36] [HM36] (Iterated spacings.) In the notation of the previous exercise, show that the numbers $S'1 = nS{(1)}$, $S'2 = (n-1)(S{(2)} - S_{(1)})$, $\ldots$, $S'n = 1 \cdot (S{(n)} - S_{(n-1)})$ have the same joint probability distribution as the original spacings $S_1, \ldots, S_n$ of $n$ uniform deviates. Therefore we can sort them into order, $S'{(1)} \le \cdots \le S'{(n)}$, and repeat this transformation to get yet another set of random spacings $S''_1, \ldots, S''_n$, etc. Each successive set of spacings $S^{(k)}_1, \ldots, S^{(k)}_n$ can be subjected to the Kolmogorov–Smirnov

test, using

$$K_{n-1}^{+} = \sqrt{n-1} \max_{1 \le j \le n} \left(\frac{j}{n-1} - S_1^{(k)} - \cdots - S_j^{(k)}\right),$$

$$K_{n-1}^{-} = \sqrt{n-1} \max_{1 \le j \le n} \left(S_1^{(k)} + \cdots + S_j^{(k)} - \frac{j-1}{n-1}\right).$$

Examine the transformation from $(S_1, \ldots, S_n)$ to $(S_1', \ldots, S_n')$ in detail in the cases $n = 2$ and $n = 3$; explain why continued repetition of this process will break down eventually when it is applied to computer-generated numbers with finite precision. (One way to compare random number generators is to see how long they can continue to survive such a torture test.)

Verified: yes
Solve time: 2m49s

---

Setup

Let $U_1,\ldots,U_n$ be independent uniform $(0,1)$ deviates and let $S_1,\ldots,S_n$ denote their spacings in increasing order, so that

$0 \le S_{(1)} \le \cdots \le S_{(n)}, \qquad \sum_{i=1}^n S_{(i)} = 1.$

Define the transformation $T$ by

$S'1 = nS{(1)}, \quad S'2 = (n-1)(S{(2)} - S_{(1)}), \quad \ldots, \quad S'n = S{(n)} - S_{(n-1)}.$

The task is to examine this transformation for $n=2$ and $n=3$, and to explain why repeated application fails when the spacings are represented by finite-precision arithmetic.

Solution for the main argument

Case $n=2$

Let the ordered spacings satisfy

$S_{(1)} = x, \qquad S_{(2)} = 1-x, \qquad 0 \le x \le \tfrac12.$

The transformation gives

$S'_1 = 2x, \qquad S'_2 = (1-x) - x = 1 - 2x.$

Thus the image is the pair

$(2x, 1-2x).$

Ordering these two components yields a new minimum

$S'_{(1)} = \min(2x,1-2x).$

The split occurs at $2x = 1-2x$, hence at $x=\tfrac14$. For $0 \le x \le \tfrac14$,

$S'_{(1)} = 2x,$

and for $\tfrac14 \le x \le \tfrac12$,

$S'_{(1)} = 1-2x.$

In both cases the mapping $x \mapsto S'{(1)}$ is piecewise linear with slopes $\pm 2$ and sends $[0,\tfrac12]$ onto itself. The second component is determined by $1-S'{(1)}$. Hence the transformation maps the simplex of spacings onto itself in a measure-preserving piecewise linear manner, and the induced distribution of ordered spacings is unchanged.

Case $n=3$

Let

$S_{(1)} = x,\quad S_{(2)} = x+y,\quad S_{(3)} = 1,$

with $x,y \ge 0$ and $x+y \le 1$. The third spacing in original (unsorted) form is $1-x-y$, and ordering ensures

$0 \le x \le x+y \le 1-x-y \text{ after permutation of coordinates}.$

Applying the transformation,

$S'_1 = 3x,$

$S'2 = 2(S{(2)} - S_{(1)}) = 2y,$

$S'3 = S{(3)} - S_{(2)} = 1 - x - (x+y) = 1 - 2x - y.$

Thus

$(S'_1,S'_2,S'_3) = (3x,2y,1-2x-y).$

This is a linear transformation on the simplex $x,y \ge 0$, $x+y \le 1$. Its Jacobian determinant equals $3 \cdot 2 \cdot 1 = 6$ before restriction to the simplex coordinates, while the inverse mapping is a permutation of affine regions determined by the ordering constraints. The domain is partitioned into regions according to which of $3x,2y,1-2x-y$ are ordered. On each region the transformation is affine and bijective onto the simplex.

Hence the induced joint distribution of ordered spacings is preserved, since Lebesgue measure is preserved up to permutation across the partitioned linear pieces, and each piece corresponds to a reparameterization of the same simplex volume.

Iteration and finite precision breakdown

Each transformation replaces spacings by linear combinations with integer coefficients depending on $n$. After $k$ iterations, every spacing is an integer linear combination of the original spacings with coefficients growing multiplicatively with factors $n,n-1,\ldots,1$ at each stage.

When computations are carried out in finite precision, each spacing is represented on a discrete grid. The transformation maps this grid into itself only approximately, and rounding forces repeated identification of nearby values. Once two spacings become equal at machine precision, subsequent ordering places them in adjacent positions, and their difference becomes zero after subtraction in later steps of the transformation.

Once a spacing becomes zero, the transformation preserves this degeneracy: if $S_{(i)} = S_{(i-1)}$, then the corresponding transformed difference $S'i = (n-i+1)(S{(i)}-S_{(i-1)})$ equals $0$. Thus zeros persist under iteration.

Because the state space is finite under machine precision, repeated application produces a deterministic map on a finite set. Every trajectory eventually enters a cycle. The earlier collapse into repeated equalities reduces the effective dimension of the simplex, so successive iterations lose variability and drive the system toward degenerate spacing vectors concentrated on a small number of representable values.

This explains the breakdown of the “torture test”: the theoretical invariance relies on continuous uniform measure on the simplex, while finite precision replaces the simplex by a finite lattice that is not preserved in a measure-equivalent way under repeated ordering and scaling.

Verification

For $n=2$, substitution of $S_{(2)}=1-S_{(1)}$ yields a closed form transformation depending only on $S_{(1)}$, and recombination confirms that the image always lies in the simplex and preserves total sum $1$.

For $n=3$, direct computation verifies

$S'_1+S'_2+S'_3 = 3x + 2y + (1-2x-y) = 1 + x + y,$

and after re-normalization by ordering (which permutes components without changing sums), the structure remains within the simplex, confirming consistency of the transformation.

For finite precision, persistence of zero spacings follows directly from the identity

$$$$