Unabhängige Zufallsfolgen

Zufallsfolgen heißen unabhängig, wenn die Quelle, die diese Zufallszahlen erzeugt, ohne Gedächtnis arbeitet. Das heißt: Unabhängig von den zuvor erzeugten Gliedern der Zufallsfolge wird die nächste zufällige Zahl generiert – so als ob diese Zahl das erste Glied der Zufallsfolge ist.

Unabhängige Zufallsfolgen haben deshalb die folgende Eigenschaft:

P[Xi trifft Ereignis x] = P[x1 trifft Ereignis x] für i = 2, 3, 4, ....

Zum Beispiel kann man aus k unabhängigen, gleichverteilten Münzwürfen (P[Xi = 0] = P[Xi = 1] = 0,5 für i=1, 2, 3, ...) eine zufällige gleichverteilte Zufallszahl X aus dem Wertebereich 0, ..., 2^k-1 bestimmen:

X = 2^(k-1)*X1 + 2^(k-2)*X2 + ... + 2^1*X[k-1] + Xk

Das kann man nur wegen der Unabhängigkeit so einfach ausführen, da bei Unabhängigkeit die folgende multiplikative Formel gilt:

P[X=x] = P[X = x =2^(k-1)x1 + 2^(k-2)x2 + ... + xk]
  = P[X1 = x1 und X2 = x2 und ... und Xk = xk]
  = P[X1 = x1] * P[X2 = x2] * ... * P[Xk = xk]
  = ½ * ½ * ... * ½ = 2^(-k).

Die Formel x =2^(k-1)x1 + 2^(k-2)x2 + ... + xk beschreibt hierbei die Zahl x in Binärdarstellung.