# Computationally random bitstreams and normalcy

Let $$\mathbb{N}$$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $$s:\mathbb{N}\to \{0,1\}$$, with some $$A\in{\cal P}(\mathbb{N})$$: take $$A = s^{-1}(\{1\})$$.

Given any $$S\subseteq \mathbb{N}$$ we define maps $$\mu_S^+, \mu_S^-:{\cal P}(\mathbb{N})\to[0,1]$$ by setting, for every $$A\in{\cal P}(\mathbb{N})$$, $$\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$$.

We say that $$A\subseteq \mathbb{N}$$ is computationally random if for every computable set $$S\subseteq\mathbb{N}$$, the set $$A$$ is well-balanced with respect to $$S$$. Morevover, we say that the bitstream $$s:\mathbb{N}\to\{0,1\}$$ is computationally random if $$s^{-1}(\{1\})$$ is computationally random.

Note that neither the Thue-Morse sequence or the Champernowne sequence $$C_2$$ are computationally random.

Question. Is every computationally random bitstream normal (that is, every finite $$01$$-string appears infinitely often)?

• The linked article has a variety of definitions for algorithmic randomness, focusing on Martin-Lof randomness. Which one of those do you think might be identical with yours? – Matt F. Jul 1 '19 at 10:36
• Your randomness notion is Church stochasticity, which is distinct from each of the randomness notions on the wikipedia page. – Dan Turetsky Jul 1 '19 at 11:08
• Thanks @DanTuretsky , I will check out Church stochasticity. I will change the question to make it more precise. – Dominic van der Zypen Jul 1 '19 at 12:29
• You need to be more clear on your definition of "normal". I think you mean to say normal in base 2, meaning that for every length $l$, every finite binary string of length $l$ appears with asymptotic density $\frac{1}{2^l}$, not just infinitely often. – James Jul 1 '19 at 14:07
• You want to restrict $S$ to be infinite. It's obviously not true if $S = A \cap \{1,\ldots,N\}$ for some $N$. – Robert Israel Jul 1 '19 at 14:47

Let $$s$$ be a computationally random bitstring. Consider $$\tilde{s}$$ defined by $$\tilde{s}(2n) = \tilde{s}(2n+1) = s(n)$$. Then $$\tilde{s}$$ should also be computationally random, but it does not contain any $$010$$ or $$101$$.