**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)$?



Arithmetically random bitstreams
The [Thue–Morse sequence](https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence) is such an example, as was (first, I believe) [proved by Dumont](https://mathscinet.ams.org/mathscinet-getitem?mr=725391).


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](https://en.wikipedia.org/wiki/Sign_sequence#Erd%C5%91s_discrepancy_problem).


