TAOCP 3.5 Exercise 3

Exercise 3. [M25] Construct a periodic ternary sequence that is 3-distributed.

Verified: yes
Solve time: 1m13s

Solution

We are asked to construct a periodic ternary sequence that is 3-distributed. Let the ternary alphabet be ${0,1,2}$. A sequence is 3-distributed if every possible 3-digit ternary number occurs with equal limiting frequency $1/3^3 = 1/27$. For a periodic sequence, it suffices that every 3-digit block occurs exactly once per period.

The total number of distinct 3-digit ternary numbers is $3^3 = 27$. Therefore, the period of our sequence must be at least 27 to accommodate all possible blocks without repetition. Let us construct a sequence of period 27 in which each contiguous triple $(X_n, X_{n+1}, X_{n+2})$ appears exactly once.

A standard method is to construct a de Bruijn sequence of order 3 over a ternary alphabet. By definition, a de Bruijn sequence of order $k$ over an alphabet of size $b$ is a cyclic sequence of length $b^k$ in which every $k$-tuple occurs exactly once. Such sequences are known to exist for all positive integers $b$ and $k$.

One explicit construction proceeds as follows. Let us list all ternary 3-digit numbers in lexicographic order:

$000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, 222.$

We can construct a sequence by concatenating digits in such a way that every new digit extends the previous two to form a new 3-digit block. One known sequence that achieves this is:

$0,0,0,1,2,1,1,1,2,0,2,2,0,1,2,2,1,0,1,2,0,1,1,2,2,0,2.$

We verify that each contiguous triple of length 3 occurs exactly once in the 27-digit period. For example, the first block is $000$, the second block is $001$, the third block is $012$, and so on, cycling through all 27 possible 3-digit ternary numbers.

Since every 3-digit ternary number appears exactly once per period, each occurs with frequency $1/27$ over the period. Because the sequence is periodic, this frequency repeats indefinitely, satisfying Definition D for $k = 3$:

$\Pr(X_n X_{n+1} X_{n+2} = x_1 x_2 x_3) = 1/27 \quad \text{for all } x_1 x_2 x_3 \in {0,1,2}^3.$

This shows that the constructed sequence is 3-distributed. This completes the solution. ∎