0
$\begingroup$

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 $A\subseteq \mathbb{N}$ we set $$\mu^{+}(A)= \lim \sup_{n\to\infty}\frac{|A \cap\{1,\ldots,n\}|}{n+1}.$$

We say that a bitstream $s$ is normal if every finite $01$-string appears infinitely often. For any finite $01$-string $\sigma$ we let $\text{Start}(\sigma)$ be the set of starting points of $\sigma$ inside $s$, and $\sigma$ is said to be frequent is $s$ if $\mu^+(\text{Start}(\sigma))>0$.

Question. Is there a normal bitstream $s$ with infinitely many frequent finite $01$-strings?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ A random bitstream has the property you want (for every finite bitstring the set of starting points has positive density) with probability one. $\endgroup$ Commented Aug 21, 2019 at 10:01

1 Answer 1

Reset to default
2
$\begingroup$

Yes. Enumerate the set of all finite $0$-$1$-sequences as $\langle\sigma_n:n\in\omega\rangle$ such that each sequence is listed infinitely often. Define $s$ to be the sequence that starts with $a_0$ copies $\sigma_0$, $a_1$ copies of $\sigma_1$, $a_2$ copies of $\sigma_2$, $\dots$, $a_n$ copies of $\sigma_n$, $\dots$, where the $a_n$ are determined, recursively as follows: $a_0=1$. When you ready to add copies of $\sigma_n$ let $a_n$ be the length of $s$ thus far and let $l_n$ be the length of $\sigma_n$. Append $a_n$ copies of $\sigma_n$ to $s$. The new sequence has length $a_n(1+l_n)$ (so $a_{n+1}=a_n(1+l_n)$) and it has at least $a_n$ points where a copy of $\sigma_n$ starts. This shows that in the end for a sequence $\sigma$ of length $l$ we have $\mu^+(\mathrm{Start}(\sigma))\ge 1/(1+l)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.