BLOCKGLEICHVERTEILUNG VON ZUFALLSZAHLENFOLGEN

Robert F. Tichy

Für verschiedene Zwecke ist es notwendig zu klären, ob eine Folge ,,zufällig“ ist. Man kann dazu zweckmäßig deterministische Kriterien verwenden (vgl. D. E. Knuth, The Art of Computer Programming, Vol. 2, Sect. 3.5): Sei etwa eine unendliche 0,1-Folge ω gegeben, so kann sie als zufällig betrachtet werden, wenn für beliebiges k ∈ ℕ jeder 0,1-Block der Länge k mit der Wahrscheinlichkeit 2^{−k} vorkommt. Eine stärkere Zufälligkeitsbedingung empfiehlt ebenfalls Knuth:

Sei k = k(n) eine wachsende Folge natürlicher Zahlen und

D_{k(n)}(ω) = max_{|u|=k(n)} |\frac{Ω(u, n)}{n} − 2^{−k(n)}| ,

wobei Ω(u, n) die Anzahl der Vorkommnisse des Blocks u (der Länge |u|) im n-ten Anfangsabschnitt von ω bezeichnet. Man verlangt nun, daß 2^{k(n)}D_{k(n)}(ω) gegen 0 konvergiert (d.h. ω ist k(n)-gleichverteilt).

Satz. Fast alle Folgen ω (0, 1 gleich-wahrscheinlich) sind k(n)-gleichverteilt, falls

k(n) ≤ lg n − lg lg n − 2 lg lg lg n. (lg = log_{2})

Ausführliche Beweise werden in der gemeinsamen Arbeit [1] mit Ph. Flajolet und P. Kirschenhofer erscheinen. Die Beweise beruhen einerseits auf der Methode der “correlation polynomials” von Guibas und Odlyzko sowie andererseits auf der Sattelpunktmethods.

References

1. P. Flajolet, P. Kirschenhofer, R. F. Tichy, Deviations from uniformity in random strings, Probab. Theory Related Fields 80 (1988), 139–150.

Technische Universität Wien