5
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ 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 $\endgroup$
    – usul
    Jun 7, 2019 at 15:13
  • $\begingroup$ Brilliant - thanks @usul! $\endgroup$ Jun 7, 2019 at 16:48
  • 1
    $\begingroup$ 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? $\endgroup$ Jun 9, 2019 at 1:29
  • 1
    $\begingroup$ +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". $\endgroup$
    – Nat
    Jun 10, 2019 at 22:27
  • $\begingroup$ Thanks @nat for your comment - I changed the title to "arithmetically random". $\endgroup$ Jun 11, 2019 at 4:41

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

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<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_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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.