Zufallszahlen | MathePrisma

Diskrepanz-Abschätzung

Ein weiterer wichtiger Test untersucht die $s$ -dimensionale Diskrepanz der Folge

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

([7], Section 7; [24], Chapter 7). Hier zeigt sich die Stärke der Methoden, die in der Zahlentheorie für ganz andere Zwecke entwickelt wurden. Denn obwohl die Diskrepanz und ihre Abschätzungen durch Exponentialsummen ursprünglich für gleichverteilte Folgen entwickelt wurden, kann man sie auch auf periodische und damit sicher nicht gleichverteilte Folgen anwenden.

Voraussetzungen

Die schärfsten Aussagen bekommt man, wenn man die Diskrepanz einer vollen Periode betrachtet. Sei dazu wieder $m=p$ eine Primzahl, $y_0\not\equiv 0\,\bmod p$ und $r=0$ . Unter diesen Voraussetzungen konnte Niederreiter zeigen ([23], Remark 3.6):

Satz

Es gibt für jedes $s\ge 2$ eine Primitivwurzel $\lambda_s$ modulo $p$ , sodaß für die $s$ -dimensionale Diskrepanz des zugehörigen linearen Kongruenzgenerators

$\begin{equation*} D_{p-1}^\ast \ll \frac{(\log p)^s\,\log\log p}{p} \end{equation*}$

gilt. Die $\ll$ -Konstante hängt dabei nur von $s$ ab.

Auf der anderen Seite besagt der Satz von Roth ([19], Chapter 2, Theorem 2.1):

Satz

Es gibt eine nur von $s$ abhängige Konstante $C_s>0$ mit

$\begin{equation*} D_{p-1}^\ast \ge C_s \frac{(\log p)^{(s-1)/2}}{p} . \end{equation*}$

Es gibt also lineare Kongruenzgeneratoren, deren $s$ -dimensionale Diskrepanz über eine volle Periode nahezu bestmöglich ist.