\input amstex
\input amsppt.sty

\nologo

\magnification1200
\hsize13cm
\vsize19cm

\def\al{\alpha}
\def\be{\beta}
\def\Om{\Omega}
\def\om{\omega}
\def\F{\Cal F}

\topmatter 
\title Blockgleichverteilung von Zufallszahlenfolgen
\endtitle 
\author Robert F. Tichy
\endauthor 
\address 
Technische Universit\"at Wien
\endaddress

\endtopmatter
\document

F\"ur verschiedene Zwecke ist es notwendig zu kl\"aren, ob eine Folge
,\kern-1pt,zuf\"allig`` ist. Man kann dazu zweckm\"a\ss ig
deterministische Kriterien verwenden (vgl\. D.~E.~Knuth, {\it The Art
of Computer Programming, Vol.~2}, Sect.~3.5): Sei etwa eine unendliche
0,1-Folge $\om$ gegeben, so kann sie als zuf\"allig betrachtet werden,
wenn f\"ur beliebiges $k\in \Bbb N$ jeder 0,1-Block der L\"ange $k$
mit der Wahrscheinlichkeit $2^{-k}$ vorkommt. Eine st\"arkere
Zuf\"alligkeitsbedingung empfiehlt ebenfalls Knuth:

Sei $k=k(n)$ eine wachsende Folge nat\"urlicher Zahlen und 
$$D_{k(n)}(\om)=\max_{\vert u\vert=k(n)}\left\vert \frac {\Om(u,n)}
{n} - 2^{-k(n)}\right\vert,$$
wobei $\Om(u,n)$ die Anzahl der Vorkommnisse des Blocks $u$ (der
L\"ange $\vert u\vert$) im $n$-ten Anfangsabschnitt von $\om$
bezeichnet. Man verlangt nun, da{\ss} $2^{k(n)}D_{k(n)}(\om)$ gegen 0
konvergiert (d.h. $\om$ ist $k(n)$-gleichverteilt).

\proclaim{Satz}Fast alle Folgen $\om$ {\rm(}$0,1$ gleich-wahrscheinlich{\rm)} sind
$k(n)$-gleichverteilt, falls
$$k(n)\le \lg n-\lg\lg n-2\lg\lg\lg n.\quad (\lg=\log_2)$$

\endproclaim

Ausf\"uhrliche Beweise werden in der gemeinsamen Arbeit \cite{1} mit
Ph.~{\smc Flajolet} und P.~{\smc Kirschenhofer} erscheinen. Die
Beweise beruhen einerseits auf der Methode der ``correlation
polynomials" von Guibas und Odlyzko sowie andererseits auf der
Sattelpunktmethods. 





\Refs
\ref\no1\by P. Flajolet, P. Kirschenhofer, R. F. Tichy
\paper Deviations from uniformity in random strings\jour 
Probab\. Theory Related Fields\vol 80\yr 1988\pages 139--150\endref


\endRefs





\enddocument
