期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2012
卷号：109
期号：47
页码：19145-19150
DOI：10.1073/pnas.1215998109
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：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.
关键词：approximate entropy ; maximally irregular ; deficit from equidistribution
