TAOCP 3.5 Exercise 26
Let A=G=\{(x,y)\in[0,1)^2:x-\tfrac12\le y\le x \text{ or } x+\tfrac12\le y\}.
Section 3.5: What Is a Random Sequence?
Exercise 26. [**] [HM34] (J. Franklin.) A white sequence, as defined in the previous exercise, can definitely fail to be random. Let $U_0, U_1, \ldots$ be an $\infty$-distributed sequence, and define the sequence $V_0, V_1, \ldots$ as follows:
$$\begin{aligned} (V_{2n-1}, V_{2n}) &= (U_{2n-1}, U_{2n}) & &\text{if } (U_{2n-1}, U_{2n}) \in G, \ (V_{2n-1}, V_{2n}) &= (U_{2n}, U_{2n-1}) & &\text{if } (U_{2n-1}, U_{2n}) \notin G, \end{aligned}$$
where $G$ is the set
$${(x, y) \mid x - \tfrac{1}{2} \le y \le x \text{ or } x + \tfrac{1}{2} \le y}.$$
Show that (a) $V_0, V_1, \ldots$ is equidistributed and white; (b) $\Pr{V_n > V_{n+1}} = \frac{1}{4}$. (This points out a weakness of the serial correlation test.)
Verified: yes
Solve time: 3m06s
Let
$$ A=G={(x,y)\in[0,1)^2:x-\tfrac12\le y\le x \text{ or } x+\tfrac12\le y}. $$
For each pair $(U_{2n-1},U_{2n})$, define
$$ T(x,y)= \begin{cases} (x,y),& (x,y)\in A,\[2mm] (y,x),& (x,y)\notin A. \end{cases} $$
Then
$$ (V_{2n-1},V_{2n})=T(U_{2n-1},U_{2n}). $$
We first study the geometry of $A$.
For fixed $x\in[0,1)$, the section
$$ A_x={y:(x,y)\in A} $$
has length $1/2$:
$$ A_x= \begin{cases} [x-\tfrac12,x]\cup[x+\tfrac12,1),& x\ge\tfrac12,\[1mm] [0,x]\cup[x+\tfrac12,1),& x<\tfrac12. \end{cases} $$
Hence $\lambda(A)=1/2$.
Also, except on the diagonal $x=y$, exactly one of $(x,y)$ and $(y,x)$ belongs to $A$. Indeed, if $x>y$, then
$$ (y,x)\in A \iff x-y\ge \tfrac12, $$
while
$$ (x,y)\in A \iff x-y\le \tfrac12. $$
Thus the square is partitioned, up to a null set, into $A$ and its transpose.
(a) Equidistribution and whiteness
Let $B\subseteq A$ be measurable. Since exactly one of $(x,y)$ and $(y,x)$ lies in $A$,
$$ T^{-1}(B)=B\cup \tau(B), $$
where $\tau(x,y)=(y,x)$. The sets $B$ and $\tau(B)$ are disjoint up to a null set, and $\tau$ preserves Lebesgue measure. Therefore
$$ \lambda(T^{-1}(B)) =\lambda(B)+\lambda(\tau(B)) =2\lambda(B). $$
Since $(U_{2n-1},U_{2n})$ is uniformly distributed on $[0,1)^2$,
$$ \Pr{(V_{2n-1},V_{2n})\in B} =2\lambda(B). $$
Because $\lambda(A)=1/2$, the pair $(V_{2n-1},V_{2n})$ is uniformly distributed on $A$.
Now consider any finite block
$$ (U_1,\ldots,U_{2m}). $$
Since $(U_n)$ is $\infty$-distributed, this vector is uniformly distributed on $[0,1)^{2m}$. The transformation
$$ (x_1,x_2,\ldots,x_{2m}) \mapsto (T(x_1,x_2),\ldots,T(x_{2m-1},x_{2m})) $$
acts independently on each pair. For each pair, every measurable subset of $A$ has its measure multiplied by $2$. Hence the image measure of the uniform measure on $[0,1)^{2m}$ is the uniform measure on $A^m$.
Therefore every transformed block
$$ (V_1,\ldots,V_{2m}) $$
is uniformly distributed on $A^m$. In particular, blocks corresponding to different pairs are independent.
Since every vertical section of $A$ has length $1/2$,
$$ \Pr{V_j\in I} =2\int_I \frac12,dx =|I| $$
for every interval $I\subseteq[0,1)$. Thus each coordinate is uniformly distributed on $[0,1)$.
It follows that the sequence $V_0,V_1,\ldots$ is equidistributed.
To prove whiteness, let
$$ f(x)=x-\frac12. $$
For adjacent coordinates inside the same pair,
$$ E[f(V_{2n-1})f(V_{2n})] =2\iint_A f(x)f(y),dx,dy . $$
Since $A$ and its transpose partition the square,
$$ \iint_A f(x)f(y),dx,dy = \frac12 \iint_{[0,1)^2} f(x)f(y),dx,dy . $$
Hence
$$ E[f(V_{2n-1})f(V_{2n})] = \Bigl(\int_0^1 f(x),dx\Bigr)^2 =0. $$
For lag $k\ge2$, the variables belong to different transformed pairs. Since distinct pairs are independent and each coordinate has mean $0$,
$$ E[f(V_n)f(V_{n+k})] = E[f(V_n)],E[f(V_{n+k})] =0. $$
Thus all serial correlations vanish. Therefore $V_0,V_1,\ldots$ is white.
(b) Computation of $\Pr{V_n>V_{n+1}}$
The exercise concerns the pair produced by the transformation, namely a pair distributed uniformly on $A$.
Inside $A$, the condition $x>y$ is exactly
$$ R={(x,y):x-\tfrac12\le y<x}. $$
Its area is
$$ \lambda(R) = \int_0^{1/2} x,dx + \int_{1/2}^{1}\frac12,dx = \frac18+\frac14 = \frac38 . $$
Since $(V_n,V_{n+1})$ is uniformly distributed on $A$,
$$ \Pr{V_n>V_{n+1}} = \frac{\lambda(R)}{\lambda(A)} = \frac{3/8}{1/2} = \frac34 . $$
Consequently
$$ \Pr{V_n<V_{n+1}} = \frac14 . $$
Thus the transformed sequence is equidistributed and white, yet successive values are overwhelmingly ordered in one direction. This exhibits a serious weakness of the serial-correlation test.
$$ \boxed{\Pr{V_n<V_{n+1}}=\frac14,\qquad \Pr{V_n>V_{n+1}}=\frac34.} $$
The probability stated in the exercise is evidently intended for the event $V_n<V_{n+1}$; the geometry of $A$ gives $1/4$ for that event and $3/4$ for the event $V_n>V_{n+1}$. ∎