Sequenzen über einem Alphabet

Sei ${\displaystyle \Sigma }$ ein endliches Alphabet und ${\displaystyle \Sigma ^{\infty }}$ bezeichne die Menge aller Folgen (= unendlichen Sequenzen) über diesem Alphabet. Sei ${\displaystyle S\in \Sigma ^{\infty }}$ eine solche Folge. Für jedes Zeichen ${\displaystyle a\in \Sigma }$ sei mit ${\displaystyle N_{S}(a,n)}$ die Anzahl bezeichnet, wie oft ${\displaystyle a}$ in den ersten ${\displaystyle n}$ Gliedern der Folge ${\displaystyle S}$ auftritt. Die Folge ${\displaystyle S}$ heißt einfach normal genau dann, wenn für jedes ${\displaystyle a}$ folgende Grenzwertbeziehung erfüllt ist:

${\displaystyle \lim _{n\to \infty }{\frac {N_{S}(a,n)}{n}}={\frac {1}{|\Sigma |}}}$

Sei ${\displaystyle w}$ ein Wort (= endliche Sequenz) über diesem Alphabet, also aus ${\textstyle \Sigma ^{*}=\bigcup _{n\in \mathbb {N} _{0}}\Sigma ^{n}}$, und sei ${\displaystyle N_{S}(w,n)}$ die Anzahl, wie oft das Wort ${\displaystyle w}$ als Teilwort in den ersten ${\displaystyle n}$ Zeichen der Folge ${\displaystyle S}$ auftritt. (Beispiel: Für ${\displaystyle S=01010101...}$ gilt ${\displaystyle N_{S}(010,8)=3}$.) Die Folge ${\displaystyle S}$ heißt normal genau dann, wenn für alle endlichen Wörter ${\displaystyle w\in \Sigma ^{\ast }}$ folgende Grenzwertbeziehung gilt:

${\displaystyle \lim _{n\to \infty }{\frac {N_{S}(w,n)}{n}}={\frac {1}{{|\Sigma |}^{|w|}}}}$

wobei ${\displaystyle |w|}$ die Länge des Worts ${\displaystyle w}$ bezeichnet und ${\displaystyle |\Sigma |}$ die Anzahl der Zeichen im Alphabet ${\displaystyle \Sigma }$.

Mit anderen Worten ist die Folge ${\displaystyle S}$ genau dann normal, wenn alle Wörter gleicher Länge ${\displaystyle k=|w|}$ mit der gleichen asymptotischen Häufigkeit auftreten. In einer normalen Binärfolge (= Folge über dem Alphabet ${\displaystyle \{0,1\}}$) kommen die Ziffern ${\displaystyle 0}$ und ${\displaystyle 1}$ im Grenzwert ${\displaystyle n\to \infty }$ mit der Häufigkeit ${\displaystyle {\tfrac {1}{2}}}$ vor, außerdem die Paarungen ${\displaystyle 00}$, ${\displaystyle 01}$, ${\displaystyle 10}$ und ${\displaystyle 11}$ mit der Häufigkeit ${\displaystyle {\tfrac {1}{4}}}$, die Tripletts ${\displaystyle 000}$, ${\displaystyle 001}$, ${\displaystyle 010}$, ${\displaystyle 011}$, ${\displaystyle 100}$, ${\displaystyle 101}$, ${\displaystyle 110}$ und ${\displaystyle 111}$ mit der Häufigkeit ${\displaystyle {\tfrac {1}{8}}}$ usw.

Betrachten wir nun als Zeichenfolge eine Ziffernfolge ${\displaystyle S_{x,b}}$ einer beliebigen reellen Zahl ${\displaystyle x}$ in der Darstellung in einem Stellenwertsystem (als Zahlensystem) mit einer ganzzahligen Basis ${\displaystyle b\geq 2}$ (${\displaystyle b}$-adische Darstellung). Die Zeichen sind hier die Ziffern dieser Darstellung von ${\displaystyle 0}$ bis ${\displaystyle b-1}$, das Alphabet ist also ${\displaystyle \Sigma _{b}=\{0,1,\dots ,b-1\}}$. Die Position des Dezimaltrenners (Komma) spielt keine Rolle.

Zu jedem ${\displaystyle k}$-stelligen Ziffernblock ${\displaystyle w}$ dieser Darstellung (d. h. aus Ziffern zur Basis ${\displaystyle b}$ und mit Länge ${\displaystyle |w|=k}$) bezeichnet ${\displaystyle N_{S_{x,b}}(w,n)}$ die Anzahl, mit welcher der Ziffernblock ${\displaystyle w}$ unter den ersten ${\displaystyle n}$ Nachkommastellen von ${\displaystyle x}$ auftritt.

Einfach normale Zahl

Die Zahl ${\displaystyle x\in \mathbb {R} }$ heißt einfach normal zur Basis ${\displaystyle b}$, wenn jede Ziffernfolge ${\displaystyle S_{x,b}}$ in der ${\displaystyle b}$-adischen Darstellung eine einfach normale Folge über dem Alphabet ${\displaystyle \Sigma _{b}}$ ist. (Wenn das der Fall ist, ist die Wahl für die Ziffernfolge eindeutig; allgemein ist diese Ziffernfolge nicht eindeutig, siehe 0,999...) Das ist genau dann der Fall, wenn für alle Ziffern ${\displaystyle a}$ dieser Darstellung gilt:

${\displaystyle \lim _{n\to \infty }{\frac {N_{S_{x,b}}(a,n)}{n}}={\frac {1}{b}}}$

Beispielsweise ist die Zahl ${\displaystyle {\tfrac {1}{3}}=0{,}{\overline {01}}_{2}}$ (periodischer Block von ${\displaystyle 01}$ in Basis ${\displaystyle 2}$) einfach normal in Basis ${\displaystyle 2}$, da die Ziffern ${\displaystyle 0}$ und ${\displaystyle 1}$ gleich häufig vorkommen.

Normale Zahl

Die Zahl ${\displaystyle x\in \mathbb {R} }$ heißt normal zur Basis ${\displaystyle b}$ genau dann, wenn die Ziffernfolge ${\displaystyle S_{x,b}}$ in der ${\displaystyle b}$-adischen Darstellung eine normale Folge über dem Alphabet ${\displaystyle \Sigma _{b}}$ ist. Das ist genau dann der Fall, wenn für jede endliche Sequenz ${\displaystyle w}$ von Ziffern dieser Darstellung gilt:

${\displaystyle \lim _{n\to \infty }{\frac {N_{S_{x,b}}(w,n)}{n}}={\frac {1}{b^{|w|}}}}$

(Die Sequenz ${\displaystyle w}$ bezeichnet man auch als ${\displaystyle k}$-stelligen Ziffernblock)

Es lässt sich zeigen, dass eine Zahl ${\displaystyle x}$ genau dann normal zur Basis ${\displaystyle b}$ ist, wenn die Folge

${\displaystyle (b^{n}x)_{n\geq 1}=(b\cdot x,b^{2}\cdot x,b^{3}\cdot x,\dots )}$

gleichverteilt modulo 1 ist.

Außerdem gilt folgende Äquivalenz: die Zahl ${\displaystyle x}$ ist genau dann normal zur Basis ${\displaystyle b}$, wenn sie einfach normal zu jeder der Basen ${\displaystyle b,b^{2},b^{3},\ldots }$ ist.

Absolut normale Zahl

Die Zahl ${\displaystyle x}$ heißt absolut normal, wenn sie zu jeder Basis ${\displaystyle b\geq 2}$ normal ist.