Pseudozufallsfolgen

Pseudozufallsfolgen sind deterministische Zahlenfolgen, die von Algorithmen erzeugt werden und in vielen Anwendungen Zufälligkeit simulieren. Obwohl die Werte rechnerisch festgelegt sind, weisen sie statistische Eigenschaften auf, die echten Zufallsfolgen ähneln. Der Begriff bezieht sich typischerweise auf sogenannte Pseudozufallszahlengeneratoren (PRNGs), die aus einem Startwert, dem Seed, eine Folge von Zahlen erzeugen.

Die meisten PRNGs arbeiten rekursiv: aus dem aktuellen Zustand wird durch eine mathematische oder bitweise Operation der nächsten Zustand berechnet. Ein bekanntes Beispiel ist der lineare Kongruenzgenerator (LCG): s_{n+1} = (a s_n + c) mod m, wobei a, c und m festgelegt sind. Die ursprüngliche Ausgangszahl s_0 muss gesetzt werden. Die Ausgabe wird üblicherweise in reelle Werte im Intervall [0,1) transformiert.

Eigenschaften wie Gleichverteilung, Unabhängigkeit und der Umfang (Periodenlänge) hängen von der Wahl des Algorithmus ab. In der Praxis ist die Folge oft sehr lang periodisch, doch perfekte Unabhängigkeit gibt es nicht. Zudem können Korrelationen auftreten, wodurch bestimmte Muster sichtbar werden, wenn große Datensätze analysiert werden.

Anwendungen: Simulationen (Monte Carlo), numerische Integration, Optimierungsverfahren und andere Algorithmen, die Zufälligkeit erfordern. In sicherheitsrelevanten Kontexten werden PRNGs durch kryptografisch sichere PRNGs (CSPRNGs) ersetzt oder ergänzt, um Vorhersagbarkeit zu verhindern.

Die Qualität von PRNGs wird mit statistischen Tests beurteilt, etwa Diehard-, Dieharder- oder NIST-Test-Suiten. Gute Generatoren bestehen große Tests, zeigen geringe Korrelationen und eine zuverlässige Gleichverteilung der Ausgaben.

Historisch gab es frühe Ansätze wie den Middle-Square-Generator, gefolgt von Lehmer-LCGs und modernen Generatoren wie Mersenne Twister oder PCG. Jedes System hat Stärken, Schwächen und passende Anwendungsbereiche.