TAOCP 7.2.1.1 Exercise 100
Let $f_n(k)$ be the binary de Bruijn cycle of order $n$ constructed in Exercise 97, so that the infinite periodic sequence f_n(0), f_n(1), \ldots, f_n(2^n-1) contains every $n$-bit string exactly once...
Section 7.2.1.1: Generating All n-Tuples
Exercise 100. [40] [40] Do the de Bruijn cycles of exercise 97 provide a useful source of pseudo- random bits when n is large?
Verified: no
Solve time: 8m03s
Setup
Let $f_n(k)$ be the binary de Bruijn cycle of order $n$ constructed in Exercise 97, so that the infinite periodic sequence
$$ f_n(0), f_n(1), \ldots, f_n(2^n-1) $$
contains every $n$-bit string exactly once as a contiguous block (cyclically, indices taken modulo $2^n$). The sequence then repeats with period $2^n$.
The question asks whether these cycles provide a useful source of pseudo-random bits when $n$ is large, in the sense of statistical randomness and unpredictability.
A sequence is useful as pseudo-random bits only if it passes two distinct requirements: local statistical uniformity over many scales and unpredictability of future bits from past observations shorter than the full internal state.
Solution
Fix $n \ge 2$. The defining property of the de Bruijn cycle implies that for every binary string $s$ of length $n$, there exists a unique index $k \in {0, \dots, 2^n-1}$ such that
$$ (f_n(k), f_n(k+1), \dots, f_n(k+n-1)) $$
equals $s$, where indices are taken modulo $2^n$.
Let $m < n$. Every binary string $t$ of length $m$ occurs exactly $2^{n-m}$ times in one period. This follows because each occurrence of an $n$-bit block contributes exactly one occurrence of its first $m$ bits, and every $n$-bit block appears exactly once. Hence the empirical distribution of $m$-bit patterns is perfectly uniform for all $m < n$.
Let $k \ge 0$ and consider prediction of $f_n(k+1)$ from a finite past window
$$ (f_n(k-m+1), \dots, f_n(k)) $$
with $m < n$. There exist distinct $n$-bit blocks sharing the same last $m$ bits but differing in the next bit. Since each $n$-bit block occurs somewhere in the cycle, both extensions of any fixed $m$-bit suffix appear in the global sequence. Therefore the conditional distribution of the next bit given any history shorter than $n$ is not determined by frequency constraints alone, but the sequence itself is deterministic: once the full state
$$ (f_n(k-n+1), \dots, f_n(k)) $$
is known, the next bit is uniquely determined.
The construction in Exercise 97 defines $f_n$ through a deterministic recurrence on a state space of size $2^n$. Thus the sequence is a single directed cycle on all $n$-bit states, so the internal state evolves by a permutation of a finite set of size $2^n$.
Given the current state consisting of the last $n$ bits, the next bit is uniquely determined by the cycle successor map. This implies that an observer who reconstructs the internal state can predict all future bits with zero uncertainty. The entropy rate conditioned on full state is $0$.
The sequence has maximal period $2^n$, and it is balanced in the sense that every $n$-bit pattern appears exactly once per period. However, longer-range structure is rigid: the entire sequence is a single Hamiltonian cycle in the de Bruijn graph, so global correlations are enforced by construction.
For pseudo-randomness, unpredictability from partial observation is essential. Since the state size is exactly $n$ bits, any adversary who learns $n$ consecutive output bits determines the state and thus all future bits. Even without full reconstruction, the deterministic transition function ensures that the process is a finite-state automaton with no hidden entropy source.
Therefore the sequence is suitable for exhaustive coverage of patterns and for deterministic simulation where uniform visitation of all $n$-blocks is required, but it fails as a general pseudo-random bit generator because it lacks computational or statistical independence beyond window size $n$, and it is predictable from sufficiently short observation.
This completes the proof. ∎
Verification
The property that every $n$-bit string appears exactly once per period follows directly from the definition of a de Bruijn cycle. The counting argument for $m$-bit substrings with $m<n$ is valid because each occurrence is induced uniquely by its extension to an $n$-bit block, and no duplication occurs among $n$-blocks.
The state evolution uses exactly the $n$-bit window, consistent with the standard de Bruijn graph representation in which vertices are $(n-1)$-bit strings and edges correspond to $n$-bit overlaps. A cycle covering all edges induces a deterministic successor map, ensuring unique continuation from any full state.
Predictability from $n$ consecutive bits follows because those bits determine the current vertex in the cycle representation, hence determine the outgoing edge and the next bit uniquely.
All claims depend only on structural properties of de Bruijn cycles and do not require properties specific to the particular construction in Exercise 97 beyond existence of a single Hamiltonian cycle.
Notes
The sequence achieves optimal local uniformity: it is perfectly $n$-wise exhaustive in a sliding window sense. This property is stronger than many classical pseudorandom generators in distributional coverage but weaker in unpredictability.
From a computational perspective, the cycle can be generated by a constant-memory state machine of size $n$, which places it in a class of generators equivalent to finite automata rather than complexity-theoretic pseudorandom generators.
The main obstruction to randomness is not distributional bias but deterministic closure of state space. Any generator whose internal state has size $n$ bits cannot exceed $n$ bits of entropy regardless of cycle length $2^n$.