TAOCP 3.3.3 Exercise 23

The flawed solution fails at a structural point: it tries to import permutation symmetry of the joint vector $(U_n,U_{n+1},U_{n+2})$, which does not exist for a deterministic dynamical system.

taocpmathematicsalgorithmsvolume-1math-hard

Section 3.3.3: Theoretical Tests

Exercise 23. [M28] The previous exercise gives the probability that $U_{n+1} < U_n$. What is the probability that $U_{n+2} < U_{n+1} < U_n$, assuming that $U_n$ is a random real number between zero and one?

Verified: yes
Solve time: 5m20s

The flawed solution fails at a structural point: it tries to import permutation symmetry of the joint vector $(U_n,U_{n+1},U_{n+2})$, which does not exist for a deterministic dynamical system. The correct approach is to compute the event directly from the underlying probability space, not from false exchangeability.

The key observation is that the linear congruential map on the unit interval is conjugate to a shift on base-$a$ expansions, and the ordering event reduces to a purely digit-based comparison problem where symmetry can be made rigorous.

1. Reduction to the case $\theta=0$

Let

$$ s(x)={ax+\theta}, \qquad a\in\mathbb{Z},\ a\neq 1. $$

Let $x^\ast$ be the fixed point of the affine map on the circle:

$$ x^\ast \equiv ax^\ast + \theta \pmod 1 \quad\Rightarrow\quad x^\ast = \frac{\theta}{1-a} \ (\mathrm{mod}\ 1). $$

Define $y_n = U_n - x^\ast \ (\mathrm{mod}\ 1)$. Then

$$ y_{n+1} = {a y_n}. $$

This is a measure-preserving conjugacy, and adding the constant $x^\ast$ to all three variables preserves inequalities. Hence

$$ U_{n+2} < U_{n+1} < U_n \quad\Longleftrightarrow\quad y_{n+2} < y_{n+1} < y_n. $$

So it suffices to assume

$$ U_{n+1} = {a U_n}. $$

2. Digit representation

Write $U_0$ in base $a$ (for simplicity $a\ge 2$; the sign change case is analogous):

$$ U_0 = 0.d_1 d_2 d_3\ldots \quad (d_i \in {0,1,\dots,a-1}). $$

Then the map $x \mapsto ax \bmod 1$ is the left shift:

$$ U_1 = 0.d_2 d_3 d_4\ldots,\qquad U_2 = 0.d_3 d_4 d_5\ldots $$

Thus we compare three shifted sequences:

$$ S_0 = (d_1,d_2,d_3,\dots),\quad S_1 = (d_2,d_3,d_4,\dots),\quad S_2 = (d_3,d_4,d_5,\dots). $$

The digits $(d_i)$ are i.i.d. uniform on ${0,\dots,a-1}$.

3. How lexicographic order is determined

The event

$$ S_2 < S_1 < S_0 $$

is lexicographic.

Compare the three sequences from left to right. Let $k$ be the first index where the triple

$$ (d_k,d_{k+1},d_{k+2}) $$

is not constant.

Such a $k$ exists almost surely.

Before this index, all three shifts agree. At index $k$, the three sequences are determined by the triple

$$ X = d_k,\quad Y = d_{k+1},\quad Z = d_{k+2}, $$

and from that point onward, all three sequences share identical tails, so the ordering is decided entirely by the ordering of $(Z,Y,X)$ at the first decisive comparison.

More precisely, the first position where any two of $S_0,S_1,S_2$ differ is exactly where the triple $(X,Y,Z)$ is first non-constant, and the lexicographic order between the shifts is determined by the ordering of these three digits.

Thus the event reduces to a purely finite symmetry statement:

$$ S_2 < S_1 < S_0 \quad\Longleftrightarrow\quad Z < Y < X $$

at the first decisive index.

4. Symmetry of the decisive triple

The triple $(X,Y,Z)$ consists of three independent uniform digits on ${0,\dots,a-1}$.

Conditioned on the event that they are not all equal, all $6$ strict orderings of $(X,Y,Z)$ are equally likely by full permutation symmetry of i.i.d. sampling.

Ties occur with probability $O(a^{-1})$ but contribute nothing to strict order events, since ties do not produce a strict chain.

Hence:

$$ \Pr(Z < Y < X \mid \text{not all equal}) = \frac{1}{6}. $$

Since the event of all-equal digits at the decisive index has probability zero in the limiting lexicographic comparison, this conditional value is the final probability.

5. Conclusion

The probability that three successive iterates form a strictly decreasing chain is

$$ \boxed{\Pr(U_{n+2} < U_{n+1} < U_n) = \frac{1}{6}}. $$

Why this fixes the original errors

  • No assumption of exchangeability of $(U_n,U_{n+1},U_{n+2})$.
  • No use of false permutation symmetry of the dynamical system.
  • The computation is done on the underlying i.i.d. digit space.
  • The ordering event is reduced to a finite symmetric triple at the first decisive digit, where true symmetry applies.