TAOCP 3.5 Exercise 31
Let \nu_n=\#\{\,0\le j<n : U_j<\tfrac12\,\}.
Section 3.5: What Is a Random Sequence?
Exercise 31. [**] [M30] Show that ${0..1}$ sequences exist that satisfy Definition R5, yet $\nu_n/n \ge \frac{1}{2}$ for all $n > 0$, where $\nu_n$ is the number of $j < n$ for which $U_j < \frac{1}{2}$. (This might be considered a nonrandom property of the sequence.)
Verified: no
Solve time: 4m25s
Let
$$ \nu_n=#{,0\le j<n : U_j<\tfrac12,}. $$
We must construct a sequence $U_0,U_1,\ldots\in[0,1)$ that satisfies Definition R5, yet
$$ \nu_n\ge \frac n2\qquad (n>0). $$
The previous construction failed because it modified an R5 sequence on a set of positive density. We therefore use a different argument.
Choose any sequence $V_0,V_1,\ldots$ satisfying Definition R5. Such sequences exist.
For $n\ge0$, define
$$ S_n=#{,0\le j<n:V_j<\tfrac12,}-\frac n2 . $$
Since Definition R5 implies that the interval $[0,\tfrac12)$ has frequency $1/2$,
$$ \frac1n#{,0\le j<n:V_j<\tfrac12,}\longrightarrow \frac12 , $$
hence
$$ S_n=o(n). $$
Now define
$$ M_n=\min_{0\le m\le n}S_m . $$
Since $S_n=o(n)$, we also have $M_n=o(n)$. Indeed, for every
$\varepsilon>0$, there exists $N$ such that $|S_m|\le \varepsilon m$ for
all $m\ge N$. Then for $n\ge N$,
$$ M_n\ge \min!\Bigl(\min_{m<N}S_m,,-\varepsilon n\Bigr), $$
and therefore $M_n/n\to0$.
Set
$$ a_n=M_n-M_{n-1}\qquad (n\ge1), $$
with $M_{-1}=0$. Since $M_n$ is nonincreasing, each $a_n\le0$.
Furthermore,
$$ \sum_{j=1}^{n} a_j=M_n . $$
For each $n\ge1$, insert $-2a_n$ copies of the value $0$ immediately
before $V_n$. Since $a_n$ is an integer $\le0$, the number
$-2a_n$ is a nonnegative even integer.
Let $U$ be the resulting sequence.
The prefix inequality
Consider the sequence as it is built from left to right.
Before the copies inserted at stage $n$, the cumulative excess
$$ E=\nu-\frac{\text{length}}2 $$
equals
$$ S_n-M_{n-1}. $$
Indeed, the original terms contribute $S_n$, while the previously inserted
zeros contribute
$$ \frac12\sum_{j=1}^{n-1}(-2a_j) = -\sum_{j=1}^{n-1}a_j = -M_{n-1}. $$
Since $M_{n-1}\le S_n$, we have
$$ S_n-M_{n-1}\ge0. $$
Each inserted zero increases $E$ by $1/2$, because it increases
$\nu$ by $1$ and the length by $1$. Therefore $E$ remains
nonnegative throughout the inserted block.
After all $-2a_n$ zeros have been inserted, the excess becomes
$$ S_n-M_{n-1}-a_n = S_n-M_n \ge0. $$
Appending the term $V_n$ changes $E$ by either $+1/2$ or $-1/2$.
The resulting excess is
$$ S_{n+1}-M_n . $$
Since $M_n\le S_{n+1}$, this is again nonnegative.
By induction, at every position of the sequence $U$,
$$ \nu-\frac{\text{length}}2\ge0. $$
Hence
$$ \nu_n\ge \frac n2 \qquad (n>0). $$
Verification of Definition R5
Let $D$ be the set of inserted positions.
Up to the point corresponding to the first $n$ terms of $V$, the total
number of inserted elements is
$$ \sum_{j=1}^{n}(-2a_j) = -2M_n = o(n). $$
Thus the number of inserted positions among the first $N$ terms of $U$ is
$o(N)$. Therefore $D$ has asymptotic density $0$.
Fix $k\ge1$. A $k$-tuple of consecutive terms in $U$ differs from the
corresponding $k$-tuple in the original sequence $V$ only if its starting
position lies within distance $k-1$ of some inserted position. The set of
such starting positions also has density $0$.
Consequently, for every $k$-dimensional box
$$ [a_1,b_1)\times\cdots\times[a_k,b_k)\subset[0,1)^k, $$
the counts of $k$-tuples in $U$ and $V$ differ by $o(N)$ among the
first $N$ starting positions. Therefore the limiting frequencies are the
same for $U$ and $V$.
Since $V$ satisfies Definition R5, the sequence $U$ also satisfies
Definition R5.
Thus there exists a sequence satisfying Definition R5 for which
$$ \frac{\nu_n}{n}\ge\frac12 \qquad (n>0). $$
This is the required example. ∎