OK, every random bitstring "eventually" contains as a substring every 2^k-bit integer, for every k. It should be relatively easy to compute the length of a random string necessary to make sure that the probability of seeing *every* 2^k-bit integer is > 1/2 (or > epsilon, for some a priori epsilon). Suppose I want to check this particular property of a RNG; how long should I wait -- i.e., how many bits -- before becoming suspicious that the RNG is somehow *censoring* certain subsequences? If I want to "censor" a RNG, I could simply keep a k-bit shift-register and look for the sequence I want to censor and simply flip the last bit in order to disagree. If want to censor 2 different substrings, I could keep 2 different shift-registers and comparators. I could also use the various sequence comparison hacks -- e.g., comparing the searched sequences with themselves to optimize how much state to keep around when checking for multiple censored subsequences. Suppose someone gives me a censored RNG, but no indication of k -- the number of bits in the censored sequence. How should I organize my computation to check for censoring for every k<n for some a priori maximum n that I'm willing to check for? At 02:05 PM 3/29/2018, Adam P. Goucher wrote:

I've wondered the same question before. My not-particularly-elegant solution is to take, for all n, the de Bruijn sequence of length 2^n, cyclically permuted such that it begins with a maximal string of zeroes, and concatenate them. So we get something like this:

01 0011 00010111 0000...

It's half as efficient as a single de Bruijn code, because you might have to go up to 2^(n+1) to find your favourite length-n bitstring.

Best wishes,

Adam P. Goucher

...

Sent: Thursday, March 29, 2018 at 1:36 AM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Infinitely long Gray-like codes ?

de Bruijn cycles might be a better starting point --- see OEIS A080679, and https://en.wikipedia.org/wiki/De_Bruijn_sequence

WFL

On 3/29/18, Henry Baker <hbaker1@pipeline.com> wrote:

...

Most of the applications in the Wikipedia article on Gray codes consider *fixed length* codes for some length n.

One of the properties of binary gray codes is that substrings of them contain all of the n-bit binary integers, but far more efficiently than simply concatenating all 2^n of them.

I'm interested in a slightly different *infinite* sequence of bits, which contain these n-bit substrings as early as possible, s.t., for any n, there is a function f(n) that tells my how large of an initial substring of this infinite sequence I have to generate in order to make sure that all 2^n binary integers appear at least once.

Furthermore, I may want to "tune" this infinite sequence in order to change the statistics of how frequently all of the different k-bit integers appear, how frequently all of the (k+1)-bit integers appear, etc.

Has anyone studied such sequences?