# Arithmetically random bitstreams

Motivation (informal). When trying to generate a random bit-stream, we expect that "half of the" bits are $$0$$, and the "other half" are $$1$$. So, how about $$010101\ldots$$? Well, we would also expect that if we look at every second member of the sequence, then "half of" those bits are $$0$$ and the other half are $$1$$. So, let's make this precise.

Formal version. Let $$\mathbb{N}$$ denote the set of non-negative integers. We can identify every bit-stream, that is function $$f:\mathbb{N}\to \{0,1\}$$ with some $$A\in{\cal P}(\mathbb{N})$$ (take $$A = f^{-1}(\{1\})$$).

Given any $$S\subseteq \mathbb{N}$$ we define maps $$\mu_S^+, \mu_S^-:{\cal P}(\mathbb{N})\to[0,1]$$ by $$\mu^{+}_S(A)= \lim \sup_{n\to\infty}\frac{|A\cap S \cap\{1,\ldots,n\}|}{1+|S\cap \{1,\ldots,n\}|}, \text{ and } \mu^{-}_S(A)= \lim \inf_{n\to\infty}\frac{|A\cap S \cap\{1,\ldots,n\}|}{1+|S\cap \{1,\ldots,n\}|}.$$

We say that $$A$$ is well-balanced with respect to $$S$$ if $$\mu^+_S(A) = \mu^-_S(A) = 1/2$$.

For $$a,b\in \mathbb{N}$$ with $$a>0$$ we set $$S_{a,b} = \{an+b:n\in\mathbb{N}\}$$ and we say that $$A\in{\cal P}(\mathbb{N})$$ is arithmetically random if $$A$$ is well-balanced with respect to $$S_{a,b}$$ for any $$a,b\in\mathbb{N}$$ with $$a>0$$.

What is an example of an arithmetically random set $$A\in{\cal P}(\mathbb N)$$?

• Going by this title and motivation, it's worth pointing out a generalization: algorithmic randomness. This is one test of randomness; we can formulate other tests, and even asks for sequences that pass all such tests. en.wikipedia.org/wiki/Algorithmically_random_sequence
– usul
Jun 7, 2019 at 15:13
• Brilliant - thanks @usul! Jun 7, 2019 at 16:48
• You might also read Knuth's discussion of random sequences in Volume 2 of The Art Of Computer Programming, especially Chapter 3.5, What is a Random Sequence? Jun 9, 2019 at 1:29
• +1 for the neat question, though I'd suggest not seeing this notion of a sequence being well-balanced as relating to it being "truly random".
– Nat
Jun 10, 2019 at 22:27
• Thanks @nat for your comment - I changed the title to "arithmetically random". Jun 11, 2019 at 4:41

The Thue–Morse sequence is such an example, as was (first, I believe) proved by Dumont.

If you take a uniformly random real number in $$[0,1]$$, its binary expansion will have this property with probability $$1$$; I imagine it is conjectured that the binary expansion of every algebraic irrational number has this property.

You might also be interested in the related Erdös discrepancy problem.

The Champernowne constant $$C_2$$ ( see https://en.wikipedia.org/wiki/Champernowne_constant ) has the stronger property of normality (see https://en.wikipedia.org/wiki/Normal_number#Properties) for properties of normal numbers. If you examine a normal number along an infinite arithmetic progression and extract the resulting digits, this is also a normal number

• True, although it's interesting to note that the convergence to normality (or to well-balanced as in the OP) is extremely slow. Jun 11, 2019 at 16:51

Mauduit and Sarkozy have studied essentially this and other related pseudorandomness measures for finite as well as infinite $$\{\pm 1\}-$$valued sequences, see here (not paywalled)and the references therein.

Briefly, for a finite sequence $$(e_1,\ldots, e_N)\in \{\pm 1\}^N$$ of length $$N,$$ they define the well-distribution measure of the sequence by $$W(e_1,\ldots,e_N)=\max_{a,b,t \in \mathbb{N}} \left| \sum_{j=0}^{t-1} e_{a+jb} \right|$$ where the maximum is taken over all AP's within $$\{1,2,\ldots,N\}$$.

Another measure they define is the correlation measure of order $$k$$

$$C_k(e_1,\ldots,e_N)=\max_{M,0\leq d_1 with $$M+d_k\leq N.$$ They prove that for any sequence,

$$W(e_1,\ldots,e_N) \leq \sqrt{3 N C_2(e_1,\ldots,e_N)}$$ while for almost all sequences in $$\{\pm 1\}^N$$ one has $$\sqrt{N} \ll C_2(e_1,\ldots,e_N) \ll \sqrt{N\log N}$$

They also consider Champerpowne, Thue-Morse, and other sequences, with respect to these measures.

• That's beautiful, thanks @kodlu for this wonderful answer! Jun 11, 2019 at 16:05