Maximum discrepancy  Output  

As articulated in [Gol81], binary DB sequences:
The DB sequences with the smallest discrepancy are based on the complementing cycling register (CCR). It is easy to prove that the two CCR concatenation constructions in [GS18], which correspond to the shiftrules CCR2 and CCR3, have discrepancy less than $2n$. This is because the maximum discrepancy in any single CCR cycle is $n$ [GS17]. Experimentally, the shift rule by Huang [H90] demonstrates slightly smaller discrepancy, though no formal analysis has been given.
The greedy Prefersame and Preferopposite, along with the lexicographic composition concatenation approach all appear to have discrepancies of $O(n^2)$. The table below summarizes their discrepancies along with the four shift rules based on the CCR.
The DB sequences with the maximal discrepancy can be obtained by considering weight (density) ranges. By taking a universal cycle $U_1$ for all binary strings with weight from 0 to $\lceil n/2 \rceil 1$ and joining it with a universal cycle $U_2$ for all binary strings with weights from $\lceil n/2 \rceil$ to $n$, the discrepancy will be close to the discrepancy of $U_1$, which is ${n1 \choose \lfloor n/2 \rfloor}$. It is conjectured that the maximal discrepancy for any DB sequence is ${n1 \choose \lfloor n/2 \rfloor} + \lfloor n/2 \rfloor$, which by Stirling's approximation is $\Theta(\frac{2^n}{\sqrt{n}})$. This is exactly the discrepancy obtained by this construction, which is available for generation and download above [GS20]. The table below shows the discrepancy of this sequence, along with the coollex concatenation construction which is also based on weight ranges. The table also illustrates the discrepancies for the shift rules PCR1 (Granddaddy), PCR2 (Grandmama), PCR3, and PCR4.
The "Random" column is obtained by taking the average discrepancy of 10000 random sequences of length $2^n$. Such a random sequence is expected to have discrepancy $\Theta(2^{n/2} \sqrt{\log n})$. It remains an open problem to define/construct a DB sequence that is provably close to these random values. Experimentally, the shiftrule PCR4 constructs a DB sequence that is closest to the expected discrepancy of a random sequence.