Zufallszahlen | MathePrisma

Problem

Bis heute scheint sich keine allgemein akzeptierte Definition für Zufallsfolgen durchgesetzt zu haben. Im klassischen Werk von Knuth ([17], Chapter 3, Section 5) findet man eine Reihe von Präzisierungsvorschlägen. Eine notwendige, aber bei weitem nicht ausreichende Forderung ist die folgende:

Forderung

Für eine Zufallsfolge $(x_n)_{n\ge 1}$ sollte zu jedem $s\in\mathbb{N}$ die aus ihr abgeleitete vektorwertige Folge

$\begin{equation*} ((x_n,x_{n+1},..., x_{n+s-1}))_{n\ge 1} \end{equation*}$

gleichverteilt modulo $1$ sein.

Eine solche Folge heißt gleichmäßig gleichverteilt.

Das entspricht unserer Intuition, daß bei einer Zufallsfolge aufeinanderfolgende Elemente unkorreliert sein sollten.

Ein interessantes Ergebnis in dieser Richtung ist das folgende Theorem ([17], Chapter 3, Section 5, Theorem F):

Satz

Wählt man zufällig ein $\Theta>1$ , so ist mit Wahrscheinlichkeit $1$ die Folge $(\Theta^n)_{n\ge 1}$ gleichmäßig gleichverteilt.

Interessanterweise ist bis heute für kein einziges explizit gegebenes $\Theta>1$ bekannt, daß die zugehörige Folge gleichmäßig gleichverteilt ist. Man weiß noch nicht einmal, ob Folgen wie $(\pi^n)_{n\ge 1}$ und $(e^n)_{n\ge 1}$ gleichverteilt modulo $1$ sind.

Wie erzeugen?

Gleichmäßig gleichverteilte Zahlenfolgen scheinen also gute Kandidaten für Zufallsfolgen zu sein. Wenn sie bei Monte-Carlo-Methoden auf dem Computer eingesetzt werden sollen, muß man sie durch ein deterministisches Computer-Programm schnell erzeugen können. Dies widerspricht jedem Begriff von Zufälligkeit und wir erhalten so bestenfalls Pseudozufallsfolgen. Aber was sind gute und schnelle Algorithmen zu ihrer Erzeugung?