In Alltagssituationen lassen sich Wahrscheinlichkeiten nur schwer fassen. Zwar können wir zum Beispiel die Wahrscheinlichkeit mit einem Sechstel beziffern, eine bestimmte Zahl mit einem Würfel zu würfeln. Doch in Wirklichkeit ist das Ereignis nicht zufällig: Würden wir alle Einzelheiten darüber kennen, wie sich die Hand bewegt und welche Kräfte auf den Würfel während des Wurfs wirken, ließe sich das Ergebnis exakt vorhersagen. In der Praxis sind all diese Details aber nicht verfügbar. In der Mathematik bezeichnet man solche Situationen daher als pseudozufällig: Obwohl ein Ereignis zufällig wirkt, ist es das in Wahrheit nicht – es fehlen bloß die nötigen Informationen.

Ähnlich verhält es sich, wenn man Google um eine Zufallszahl bittet. Die Suchmaschine hat keinen Zugang zu einem perfekten Zufallsgenerator. Die gelieferte Zahl entspringt also keinem zufälligen Prozess. Trotzdem scheint das Ergebnis für Nutzerinnen und Nutzer zufällig, weil man nicht weiß, welches Verfahren Google verwendet (oder welche Parameter und Eingaben dabei exakt einfließen). Die von der Suchmaschine erzeugte Zahl ist also ebenfalls pseudozufällig.

Pseudozufallszahlen tauchen in allen möglichen Bereichen auf: Modellierungen, Kasinos und Lotterien setzen auf solche Zahlen, ebenso verwenden sie Banken und Finanzinstitute für ihre Sicherheitssysteme und, um Betrug zu erkennen. Da Hacker ein großes Interesse daran haben, die genutzten Pseudozufallsgeneratoren zu knacken, haben Fachleute ausgeklügelte Methoden entwickelt, um diese Zahlen zu erzeugen. So beruhen beispielsweise viele Generatoren auf physikalischen Verfahren: Das Cybersicherheits- und Internetdienstleistungsunternehmen Cloudflare hat zum Beispiel ein System namens »LavaRand« entwickelt, das Lavalampen zur Erzeugung von Pseudozufallszahlen verwendet.

Was ist wirklich Zufall?

Woran lässt sich an einer Menge von Punkten erkennen, ob sie von einem echten Zufallsprozess stammen oder ob sie durch ein festgelegtes Verfahren erzeugt wurden? Diese Frage ist für zahlreiche Bereiche der Mathematik von zentraler Bedeutung. Inzwischen gibt es eine Vielzahl von Tests, die Zufälligkeit feststellen sollen. Allerdings sind diese nicht perfekt, ihnen entgehen manche Muster. Deterministisch erzeugte Zahlenfolgen, die diese Tests dennoch erfüllen, werden als pseudozufällig bezeichnet. Pseudozufällige Eigenschaften haben alle möglichen Anwendungen: vom Verständnis der Primzahlen bis hin zu etwas, das als Quantenchaos bekannt ist.

Während der Coronapandemie begann ich, mich mit einem Problem zu beschäftigen, das mit Pseudozufälligkeit zusammenhängt: die Suche nach zufälligem Verhalten, wo es keinen Zufall gibt. Die Arbeit startete mit einer E-Mail, die ich an den Mathematiker Niclas Technau schickte, der damals an der Universität Tel Aviv tätig war. Mitte 2022, also fast drei Jahre später, hatten wir, obwohl wir uns nie persönlich getroffen hatten, gemeinsam drei Arbeiten verfasst und die bisher einzigen Beispiele für Folgen gefunden, die extrem starke Zufälligkeitstests bestehen.

Wie gleichmäßig sind Punkte verteilt?

Der wohl einfachste Test untersucht die Verteilung der vermeintlich zufällig erzeugten Variablen. Angenommen, es gibt zwei Quadrate, in denen mehrere Punkte verstreut sind: Bei einem Quadrat füllen sie die gesamte Fläche aus, beim anderen ist eine Hälfte hingegen leer.

Welches Punktmuster sieht zufälliger aus? Die meisten tippen auf das erste Quadrat – schließlich wäre es sehr unwahrscheinlich, dass ein Zufallsprozess die untere Hälfte eines Kästchens bei so vielen Punkten leer lässt. Daher dient die Gleichverteilung als erster Anhaltspunkt für einen zufälligen Prozess. Möchte man also prüfen, ob die Muster innerhalb eines Quadrats zufällig erzeugt werden, sollte man untersuchen, ob jeder Bereich der Fläche einen gerechten Anteil an Punkten besitzt. Falls ja, dann sind die Punkte gleichmäßig verteilt. Das Ergebnis dieses Tests wird umso aussagekräftiger, je mehr Punkte man betrachtet. Falls sie tatsächlich zufällig entstehen, sinkt die Wahrscheinlichkeit eines ungewöhnlichen Verhaltens (etwa, dass alle Punkte in der oberen Hälfte eines Quadrats landen) mit wachsender Anzahl von Punkten.

Das Prinzip der Gleichverteilung lässt sich nicht nur auf Punktmuster, sondern auch auf Zahlen anwenden. Angenommen, man untersucht eine Zahlenfolge mit Werten zwischen 0 und 1. Bei einer gleichmäßig verteilten, zufälligen Folge hat jede Zahl in dem Intervall die gleiche Wahrscheinlichkeit, Teil der Folge zu sein. Auf den ersten Blick wirkt 0,142, 0,566, 0,274, 0,265, ..., zum Beispiel zufällig, obwohl sie sich durch die Gleichung x_n = {πn²} ergibt (die geschweiften Klammern bedeuten, dass man den ganzzahligen Teil des Ergebnisses ignoriert). Die erste Zahl ist also π·1² = 3,1415…. Wenn man die 3 entfernt und nach der dritten Nachkommastelle rundet, erhält man 0,142. Das zweite Glied ergibt sich durch π·2² = 12,566…; ohne die 12 ist das 0,566.

Um festzustellen, ob die Folge gleichmäßig verteilt ist, kann man untersuchen, wie viele Folgenglieder in einem bestimmten Teilbereich zwischen 0 und 1 liegen. Der »gerechte« Anteil müsste der Anzahl der Glieder multipliziert mit der Länge des betrachteten Bereichs entsprechen. Auf diese Weise lässt sich feststellen, dass x_n = {πn²} gleichmäßig verteilt ist. Das trifft allerdings nicht auf die Folge x_n = {³⁄₇n²} zu, weil sie keine Zahlen aus dem Intervall zwischen 0,05 und 0,1 enthält. Der Gleichverteilungstest würde diese Folge also direkt ausschließen, während die durch {πn²} erzeugten Zahlen nach diesem Test noch immer zufällig aussehen. Diese Ergebnisse gehen auf die Pionierarbeit des Mathematikers Hermann Weyl aus dem Jahr 1916 zurück.

Andere Testverfahren

Obwohl die Gleichverteilung nützlich ist, bietet sie nur eine sehr grobe Methode, um die Zufälligkeit eines Musters zu messen. Das zeigt folgendes Beispiel:

Auch wenn die Punkte in allen drei Kästchen gleichmäßig verteilt sind, wirken nicht alle zufällig erzeugt. Links sind die Abstände zwischen den Punkten sehr ähnlich, und im mittleren Bild schließen sich die Punkte zu Gruppen zusammen. Nur im rechten Quadrat scheint ihre Verteilung wirklich zufällig.

Solche Fälle veranlassten Fachleute, anspruchsvollere Zufallstests zu entwickeln, die als Lückenverteilung und Paarkorrelation bezeichnet werden. Ersterer misst die Größe der Lücken zwischen den Punkten, letzterer ihre Häufung – also, wie stark sie sich gruppieren oder auseinanderklaffen. Bei diesen Tests wird untersucht, wie sich die Anzahl an Lücken beziehungsweise an Paaren von nah beieinander liegenden Punkten verändert, wenn man immer mehr Punkte berücksichtigt. Falls die Ergebnisse mit den Werten übereinstimmen, die man bei Zufallsdaten erwarten würde, spricht man von »poissonscher« Paarkorrelation oder Lückenverteilung, benannt nach dem französischen Mathematiker Siméon-Denis Poisson.

Diese Tests sind nützlich, doch es bleibt schwierig zu beweisen, dass eine gesamte Folge sie tatsächlich erfüllt. Im Grunde ist es einfacher zu zeigen, dass Punkte einem Muster folgen, als umgekehrt. Mathematikerinnen und Mathematiker wollen aber einen schlüssigen Beweis – und geben sich nicht damit zufrieden, bloß eine große Anzahl von Punkten zu testen.

Die zuvor genannten Zahlenfolgen sind Teil einer beliebten Reihe von Folgen, die sich durch x_n = αn^θ} ausdrücken lassen, wobei α und θ jeweils eine Zahl darstellen (etwa α = π und θ = 2). Das waren die ersten Beispiele, die Weyl zum Verständnis der Gleichverteilung verwendete. Es wurde zwar bewiesen, dass fast alle Werte von α und θ eine Folge mit poissonscher Paarkorrelation ergeben – doch bis vor Kurzem kannte man kein einziges konkretes Beispiel dafür. Das ist ein häufiges Problem in der Mathematik: Man kann zeigen, dass die meisten Möglichkeiten zu einem bestimmten Ergebnis führen, aber trotzdem keinen spezifischen Fall konstruieren. Es ist wie die Suche nach dem Heu im Heuhaufen. Eine Folge mit poissonscher Lückenverteilung zu finden, scheint noch aussichtsloser.

Die Suche nach einer pseudozufälligen Folge

Technau und ich hatten beschlossen, uns diesem Thema zu widmen. Im Anschluss an unsere ersten Onlinediskussionen begannen wir damit, Folgen mit dem Wert θ = ½ zu betrachten. Wir versuchten, einen Großteil der schweren mathematischen Maschinerie zu umgehen, die normalerweise für diese Aufgabe herangezogen wird (vor allem deshalb, weil ich sie nicht verstand). Wir griffen daher auf Methoden aus dem Jahr 1916 zurück, die Weyl für die Gleichverteilung genutzt hatte. Wir schafften es schließlich, das Problem, eine poissonsche Paarverteilung nachzuweisen, auf eine andere Aufgabe herunterzubrechen: den Nachweis, dass eine bestimmte Summe klein ist.

Zunächst konnten wir zeigen, dass die Summe nicht unendlich groß sein kann – aber es gelang uns nicht, sie genügend einzuschränken. Nach viel Kopfzerbrechen kam der Durchbruch: Wir erkannten, dass die genutzten Techniken besser funktionieren, wenn θ klein ist – also verkleinerten wir den Wert. Zusammen mit dem Mathematiker Athanasios Sourmelidis, der unabhängig von uns an demselben Problem gearbeitet hatte, konnten wir zeigen: Die Folge weist eine poissonsche Paarkorrelation (für jedes α) auf, wenn θ kleiner oder gleich ⅓ ist. Damit hatten wir erstmals eine ganze Familie von Zahlenfolgen gefunden, die nachweislich eine poissonsche Paarkorrelation besitzen.

Technau und ich haben die Methoden anschließend verallgemeinert, indem wir den Exponenten θ noch kleiner machten. Somit gelang es uns, zu zeigen, dass die entstehenden Folgen einen stärkeren Pseudozufälligkeitstest, die so genannten Dreifachkorrelationen, erfüllen. Indem wir θ weiter verkleinerten, konnten wir immer stärkere pseudozufällige Eigenschaften nachweisen. Unser Ansatz funktioniert, weil die Folge n^θ langsamer wächst, je kleiner der Exponent θ wird. Und dieses Verhalten ist nützlich, um die betreffende Summe einzugrenzen. Das ist der Grund, warum wir im Fall von θ = ½ keine Begrenzung für die Summe finden konnten.

Es gibt aber auch Folgen, die unabhängig vom Exponenten langsamer ansteigen als n^θ, wie zum Beispiel (logn)^A, wobei A eine beliebige Zahl größer als 0 ist. Logarithmen und deren Potenzen wachsen nur sehr, sehr langsam. Mit dieser Erkenntnis konnten wir zeigen, dass x_n = {α(log n)^θ} alle poissonschen Korrelationen (Paarkorrelationen, Dreierkorellationen und so weiter) und eine poissonsche Lückenverteilung aufweist, wenn θ > 1 ist.

Diese Kombination aus Korrelationen und Lückenverteilung ist der stärkste Pseudozufallstest. Und x_n = {α(log n)^θ} ist die einzige, uns bekannte Familie von Beispielen, die dieses Verhalten zeigt. Mit anderen Worten: Mit bisherigen mathematischen Methoden ist es unmöglich, festzustellen, ob es sich bei dieser Folge um deterministisch erzeugte oder zufällige Zahlen handelt – selbst nach unendlich vielen Stichproben.

Das Seltsame ist, dass die Folge für θ = 1 nicht einmal gleichmäßig verteilt ist. Bei xⁿ = {α logn} scheinen sich die Punkte links vom Intervall zwischen 0 und 1 zu häufen. Das lässt sich sogar mit bloßem Auge erkennen und hängt mit dem Benfordschen Gesetz zusammen. In diesem Fall ist sofort offensichtlich, dass die Folge nicht zufällig erzeugt wurde.

Die Welt der Pseudozufallszahlen steckt voller offener Fragen. Fachleute gehen davon aus, dass allerlei interessante Folgen pseudozufällig sind, haben aber keine Möglichkeit, das zu beweisen. Obwohl es in diesem Bereich viele Verbindungen zu anderen Gebieten der Mathematik gibt, sind etliche Vermutungen über pseudozufällige Folgen ungeklärt.

Technau, Sourmelidis und ich haben endlich eine Reihe von Beispielen geliefert, von denen wir zeigen konnten, dass sie starke pseudozufällige Eigenschaften besitzen. Unsere Techniken scheinen aber nur bei langsam wachsenden Folgen zu funktionieren. Vielleicht wird die Kombination unserer Methoden mit komplizierteren Ansätzen weitere Erkenntnisse bringen. Oder jemand entwickelt einen ganz neuen Werkzeugkasten, um zu entscheiden zu können, was zufällig ist und was nicht.