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

  • $\begingroup$ 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? $\endgroup$
    – Matt F.
    Jul 1, 2019 at 10:36
  • $\begingroup$ Your randomness notion is Church stochasticity, which is distinct from each of the randomness notions on the wikipedia page. $\endgroup$ Jul 1, 2019 at 11:08
  • 1
    $\begingroup$ Thanks @DanTuretsky , I will check out Church stochasticity. I will change the question to make it more precise. $\endgroup$ Jul 1, 2019 at 12:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – James
    Jul 1, 2019 at 14:07
  • 1
    $\begingroup$ You want to restrict $S$ to be infinite. It's obviously not true if $S = A \cap \{1,\ldots,N\}$ for some $N$. $\endgroup$ Jul 1, 2019 at 14:47

1 Answer 1


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

  • $\begingroup$ Very slick argument -- thanks! $\endgroup$ Jul 2, 2019 at 18:31

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.