De Bruijn Sequence and Universal Cycle Constructions

A DB sequence is in one to one correspondence with an Euler cycle in the de Bruijn graph. Each Euler cycle corresponds to a unique spanning in-tree (arborescence) with respect to some arbitrary root. Thus, a DB sequence can be generated uniformly at random as follows (see Fleury's Euler cycle algorithm).

For Eulerian graphs, an arborescence can be generated uniformly at random by performing a simple random backwards walk until every vertex is visited. The first time a vertex is visited, the edge is recorded as a tree edge in the random arborescence [KMUW96]. The running time of the above algorithm depends on the cover time of the random walk, which is the number of steps it takes to visit every vertex; it has exponential time delay and requires exponential space. The following tables (for $k=2$) illustrate the minimum, maximum, and average ratios of the cover time to total edges ($2^n$) applying this method over 100,000 iterations for $n\leq 15$ and over 10,000 iterations for $16 \leq n \leq 24$.

If an application does not require a sequence generated uniformly at random, an algorithm which applies a Burrows-Wheeler Transform can be applied; it outputs each DB sequence with positive probability [LP24]. The algorithm requires exponential space and has an exponent time delay with respect to the order $n$, but produces the sequence in $\alpha(n)$-amortized time per symbol for $k=2$, where $\alpha(n)$ is the inverse Ackerman function. The first estimate on the mean discrepancy of DB sequences is obtained using this algorithm [LP24].