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.