Otdfbt

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 $010101ldots$? 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 $mathbbN$ denote the set of non-negative integers. We can identify every bit-stream, that is function $f:mathbbNto 0,1$ with some $Aincal P(mathbbN)$ (take $A = f^-1(1)$).

Given any $Ssubseteq mathbbN$ we define maps $mu_S^+, mu_S^-:cal P(mathbbN)to[0,1]$ by $$mu^+_S(A)= lim sup_ntoinftyfrac1+, text and mu^-_S(A)= lim inf_ntoinftyfrac1+.$$

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

For $a,bin mathbbN$ with $a>0$ we set $S_a,b = an+b:ninmathbbN$ and we say that $Aincal P(mathbbN)$ is arithmetically random if $A$ is well-balanced with respect to $S_a,b$ for any $a,binmathbbN$ with $a>0$.

What is an example of an arithmetically random set $Aincal P(mathbb N)$?

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

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 mathbbN 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,0leq d_1<d_2<ldots<d_k left|
sum_n=1^M e_n+d_1 e_n+d_2 cdots e_n+d_k
right|
$$
with $M+d_kleq N.$ They prove that for any sequence,

$$
W(e_1,ldots,e_N) leq sqrt3 N C_2(e_1,ldots,e_N)
$$
while for almost all sequences in $pm 1^N$ one has
$$
sqrtN ll C_2(e_1,ldots,e_N) ll sqrtNlog N
$$

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