TAOCP 3.5 Exercise 28

Section 3.5: What Is a Random Sequence?

Exercise 28. ▶ [**] [HM21] Use the sequence (11) to construct a ${0..1}$ sequence that is 3-distributed, for which $\Pr{U_n \ge \frac{1}{2}} = \frac{1}{4}$.

Verified: yes
Solve time: 1m14s

Let $(X_n)$ be the periodic binary sequence (11),

$0001,0001,1101,1101,0001,0001,1101,1101\cdots,$

which is 3-distributed. Define

$$ U_n=\frac12,X_nX_{n+1}. $$

Since $(X_n)$ is 3-distributed, the pair $(X_n,X_{n+1})$ assumes each of the four binary values $00,01,10,11$ with probability $1/4$. Hence

$$ \Pr!\left(U_n\ge\frac12\right) =\Pr(X_nX_{n+1}=11) =\frac14. $$

Furthermore, $U_n$ depends only on the adjacent pair $(X_n,X_{n+1})$. Every block

$$ (U_n,U_{n+1},U_{n+2}) $$

is therefore determined by the 4-tuple

$$ (X_n,X_{n+1},X_{n+2},X_{n+3}), $$

and these 4-tuples occur with the frequencies required by the 3-distribution of $(X_n)$. Consequently $(U_n)$ is a 3-distributed ${0,\tfrac12}$ sequence, hence a $[0,..,1)$ sequence, and it satisfies

$$ \Pr!\left(U_n\ge\frac12\right)=\frac14. $$

Thus

$$ \boxed{U_n=\frac12,X_nX_{n+1}} $$

gives the required example. ∎