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 '19 at 10:36
  • $\begingroup$ Your randomness notion is Church stochasticity, which is distinct from each of the randomness notions on the wikipedia page. $\endgroup$ – Dan Turetsky Jul 1 '19 at 11:08
  • 1
    $\begingroup$ Thanks @DanTuretsky , I will check out Church stochasticity. I will change the question to make it more precise. $\endgroup$ – Dominic van der Zypen Jul 1 '19 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 '19 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$ – 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$.


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.