2
$\begingroup$

For $A\subseteq \omega$ we let the lower and upper density be defined as $$\mu^-(A):= \lim\inf_{n\to\infty}\frac{|A\cap n|}{n+1} \text{ and } \mu^+(A):= \lim\sup_{n\to\infty}\frac{|A\cap n|}{n+1}$$ respectively.

Let $s:\omega\to\{0,1\}$ be an infinite binary string, $n\in\omega\setminus\{0\}$ a positive integer and $t\in\{0,1\}^n$ a finite binary string of length $n$. Then we define the set of starting points of $t$ in $s$ by $$\text{start}(t, s) = \{k\in \omega: (\forall i\in n)\; t(i) = s(k+i)\}.$$ We say that $s$ is uniform for $t\in\{0,1\}^n$ if $$\mu^-\big(\text{start}(t,s)\big) = \mu^+\big(\text{start}(t,s)\big) = 1/2^n.$$

(The $1/2^n$ part is motivated by the fact that there are $2^n$ binary strings of length $n$.) We say that $s:\omega\to\{0,1\}$ is strongly uniform if for all positive integers $n$ and for all $t\in\{0,1\}^n$ we have that $s$ is uniform for $t$.

It is not clear to me whether strongly uniform infinite binary strings exist. A candidate could be the Champernowne binary string which is obtained by concatenating the binary representations of the integers: $$0\; 1 \; 10\; 11\; 100\; 101\;\ldots.$$

Question. Is the the Champernowne binary string strongly uniform? If not, is there a strongly uniform infinite binary string?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ Your tendency to denote the set $\{0,\dots,n-1\}$ by $n$, even in questions outside of foundations of mathematics, may be irksome and/or confusing for some. It is irksome to me. I would also usually prefer seeing $\mathbb N_0$ in place of $\omega$ -- which latter is used very differently (say) in probability. On the other hand, the symbol $\mathbb N_0$ is universally understood unambiguously. $\endgroup$
    – Iosif Pinelis
    Commented Feb 15, 2023 at 20:24
  • $\begingroup$ Isn't the notation $\{0,\ldots,n-1\} = n$ also immensely practical and compact? See $A \cap n$ vs $A \cap \{0,\ldots,n-1\}$. - But I get your point about $\omega$ having a different meaning in other mathematical domains. I just love $\omega$ and $\{0,\ldots,n-1\} = n$ for saving me so much typing labor! $\endgroup$
    – Dominic van der Zypen
    Commented Feb 15, 2023 at 20:37
  • 5
    $\begingroup$ I think a serious priority should be making our posts more easily and broadly understood (perhaps even by beginners, where possible). Saving on our typing is, I would suggest, is not that important. $\endgroup$
    – Iosif Pinelis
    Commented Feb 15, 2023 at 20:55
  • 2
    $\begingroup$ $[n] := \{1,2,\ldots,n\}$ is much more common in finite combinatorics. $\endgroup$
    – Sam Hopkins
    Commented Feb 16, 2023 at 1:35
  • $\begingroup$ Point taken @IosifPinelis, and thanks for reminding me of this compact notation, Sam! $\endgroup$
    – Dominic van der Zypen
    Commented Feb 16, 2023 at 17:00

1 Answer 1

Reset to default
6
$\begingroup$

Yes, the Champernowne binary string is normal (or strongly uniform, in your terms); see also here.

Almost all infinite binary string are normal, in the sense that the set of the corresponding real numbers in $[0,1]$ is of Lebesgue measure $1$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's right - the Champernowne string is normal, but strong uniformity is a much stronger condition than normalcy, because it has this measure requirement $\mu^-\big(\text{start}(t, s)\big) = \mu^+\big(\text{start}(t, s)\big) = 1/2^n$ for strings of length $n$. This requirement is missing in the definition of normal $\endgroup$
    – Dominic van der Zypen
    Commented Feb 15, 2023 at 19:49
  • 2
    $\begingroup$ @DominicvanderZypen Strong uniformity is exactly normality (in base 2). See e.g. en.wikipedia.org/wiki/Normal_number for the definition. $\endgroup$
    – Emil Jeřábek
    Commented Feb 15, 2023 at 20:07
  • 1
    $\begingroup$ @DominicvanderZypen : According to the definition at en.wikipedia.org/wiki/Normal_number#Definitions , an infinite binary string $s$ is normal (in base $2$) if, for all finite binary strings $t$ one has $\lim_{n\to\infty}\frac {N_s(t,n)}n=\frac1{2^{|t|}}$, where $|t|$ denotes the length of the string $t$ and $N_s(t,n)$ is the number of times the string $t$ appears as a substring in the first $n$ digits of $S$. $\endgroup$
    – Iosif Pinelis
    Commented Feb 15, 2023 at 20:12
  • 1
    $\begingroup$ Previous comment continued: That is, $N_s(t,n)=|\text{start}(t,s)\cap[n]|$. So, $\mu^-\big(\text{start}(t,s)\big) = \mu^+\big(\text{start}(t,s)\big)=1/2^{|t|}$ iff $\lim_{n\to\infty}\frac {N_s(t,n)}n=\frac1{2^{|t|}}$. So, your term "strongly uniform" is the same as "normal". $\endgroup$
    – Iosif Pinelis
    Commented Feb 15, 2023 at 20:12
  • $\begingroup$ OK thanks -> apologies to @IosifPinelis, will accept and upvote your answer. $\endgroup$
    – Dominic van der Zypen
    Commented Feb 15, 2023 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .