A zoo of computable binary normal sequences.

Abstract

Historically there has been a virtual absence of constructive methods to produce broad classes of "certifiably random" infinite sequences, despite considerable interest in this endeavor. Previously, we proved a theorem that yielded explicit algorithms to produce diverse sets of normal numbers, reasonable candidates for random sequences, given their limiting equidistribution of subblocks of all lengths. Herein, we develop this algorithmic approach much further, systematizing the normal number generation process in several ways. We construct delineated, distinct sets of normal numbers (classified by the extent to which initial segments deviate from maximal irregularity), with virtually any allowable specified rate of convergence to 0 of this deviation, encompassing arbitrarily fast and slow rates, and accommodating asymmetric behavior above or below a centered median. As a corollary, we provide an explicit construction of a normal number that satisfies the Law of the Iterated Logarithm. We also produce distinct families of "biased" normal numbers, with virtually any specified rate of convergence of the bias (to 0). This latter theory is in part motivated by the remarkable observation that the binary version of Champernowne's number, which is also normal, is biased-any initial segment has more 1s than 0s. Finally, we construct an interesting normal sequence with arbitrarily fast convergence to equidistribution of singleton blocks, yet arbitrarily slow convergence of pairs, which has profound implications both for probability theory, and for metrics to evaluate the "near-randomness" of sequences.