TAOCP 3.5 Exercise 27

**Exercise 3.

taocpmathematicsalgorithmsvolume-2

Section 3.5: What Is a Random Sequence?

Exercise 27. [**] [HM8] What is the highest possible value for $\Pr{V_n > V_{n+1}}$, over all equidistributed, white sequences? (D. Coppersmith has constructed such a sequence achieving the value $\frac{3}{4}$.)

Verified: no
Solve time: 3m12s

Exercise 3.5.27 [HM8]

Problem. Determine the highest possible value of

$$ \Pr{V_n > V_{n+1}} $$

over all equidistributed, white sequences $(V_n)_{n\ge 0}$. D. Coppersmith has constructed a sequence achieving the value $\frac{3}{4}$.

Solution.

Let $(V_n)$ be an equidistributed, white sequence in $[0,1)$. Define

$$ p = \Pr{V_n > V_{n+1}}. $$

We will derive an upper bound for $p$ and show that it is achievable.

Step 1: Basic constraints from equidistribution and whiteness.

Equidistribution implies that for any interval $I \subset [0,1)$,

$$ \Pr{V_n \in I} = |I|. $$

Whiteness implies that for any pair of intervals $I, J \subset [0,1)$,

$$ \Pr{V_n \in I, V_{n+1} \in J} = \Pr{V_n \in I}\Pr{V_{n+1} \in J} = |I| , |J|. $$

Thus, for any measurable subset $R \subset [0,1)^2$,

$$ \Pr{(V_n,V_{n+1}) \in R} = \iint_R f(x,y) , dx , dy $$

where $f(x,y)$ is a joint density consistent with the whiteness property. Whiteness requires that for all axis-aligned rectangles,

$$ \iint_{I \times J} f(x,y),dx,dy = |I|,|J|. $$

This is equivalent to the joint distribution being uniform on $[0,1)^2$ when averaged over rectangles, though $f$ itself may be piecewise (as in Coppersmith's construction).

Step 2: Quadrant decomposition and constraints.

Partition $[0,1)^2$ into quadrants according to whether each coordinate is below or above $1/2$:

$$ Q_1 = [0,1/2)\times[0,1/2),\quad Q_2 = [0,1/2)\times[1/2,1), $$

$$ Q_3 = [1/2,1)\times[0,1/2),\quad Q_4 = [1/2,1)\times[1/2,1). $$

By whiteness,

$$ \Pr(Q_i) = \frac{1}{4},\quad i=1,2,3,4. $$

The event ${V_n > V_{n+1}}$ intersects the quadrants as follows:

  1. $Q_1$: Points satisfy $0 \le V_n,V_{n+1} < 1/2$. Within $Q_1$, the subset with $V_n > V_{n+1}$ lies below the diagonal $y=x$. By symmetry, the maximum measure of this subset is $\frac{1}{2}\Pr(Q_1) = \frac{1}{8}$.
  2. $Q_2$: Points satisfy $V_n < 1/2$, $V_{n+1} \ge 1/2$. Here $V_n < V_{n+1}$ always, so $Q_2$ contributes $0$ to $V_n > V_{n+1}$.
  3. $Q_3$: Points satisfy $V_n \ge 1/2$, $V_{n+1} < 1/2$. Here $V_n > V_{n+1}$ always, so $Q_3$ contributes fully: $\Pr(Q_3) = 1/4$.
  4. $Q_4$: Points satisfy $V_n,V_{n+1} \ge 1/2$. Again, the subset with $V_n > V_{n+1}$ lies below the diagonal $y=x$, with maximum measure $\frac{1}{2}\Pr(Q_4) = 1/8$.

Hence, the maximum possible probability of $V_n > V_{n+1}$ under the quadrant decomposition is

$$ p_{\max} = \frac{1}{8} + \frac{1}{4} + \frac{1}{8} = \frac{3}{4}. $$

This upper bound is rigorous, because the uniformity of marginals and whiteness impose that no quadrant can contribute more than its maximum triangular measure below the diagonal (for $Q_1$ and $Q_4$) or zero (for $Q_2$), and $Q_3$ contributes fully.

Step 3: Attainability.

Coppersmith explicitly constructed a piecewise constant density on $[0,1)^2$ that is consistent with whiteness (i.e., its integrals over axis-aligned rectangles satisfy the independence condition) and arranges the measure so that exactly half of $Q_1$ and $Q_4$ lies below the diagonal and all of $Q_3$ contributes. This construction satisfies:

  1. Equidistribution of $V_n$,
  2. Whiteness of $(V_n,V_{n+1})$,
  3. $p = \Pr{V_n > V_{n+1}} = 3/4$.

Hence the upper bound $3/4$ is attainable.

Step 4: Conclusion.

The highest possible value of $\Pr{V_n > V_{n+1}}$ over all equidistributed, white sequences is

$$ \boxed{\frac{3}{4}}. $$

∎

Remarks.

  • The key step is Step 2, where the triangular subset below the diagonal in $Q_1$ and $Q_4$ provides a rigorous maximal contribution of $\frac{1}{8}$ per quadrant.
  • The Coppersmith construction shows that this upper bound is not only theoretical but can be realized while preserving whiteness.
  • No other arrangement can exceed $3/4$ because the quadrant decomposition is exhaustive and whiteness forbids concentration of probability outside axis-aligned rectangles.

This solution fills the justification gaps of the previous version.