Warum ist es unmöglich, wirklich zufällige Zahlen zu erzeugen?

Ich habe versucht, ein Hobby-Problem zu lösen, bei dem eine Million Zufallszahlen generiert werden mussten. Aber mir wurde schnell klar, dass es schwierig wird, sie einzigartig zu machen. Ich habe das Algorithm Design Manual aufgegriffen , um etwas über die Erzeugung von Zufallszahlen zu lesen.

Es gibt den folgenden Absatz, den ich nicht vollständig verstehen kann.

Leider sieht das Erzeugen von Zufallszahlen viel einfacher aus, als es wirklich ist. Tatsächlich ist es grundsätzlich unmöglich, auf einem deterministischen Gerät echte Zufallszahlen zu erzeugen. Von Neumann [Neu63] sagte es am besten: „Wer arithmetische Methoden zur Erzeugung von Zufallszahlen in Betracht zieht, befindet sich natürlich in einem Zustand der Sünde.“ Das Beste, auf das wir hoffen können, sind Pseudozufallszahlen, ein Strom von Zahlen, die als solche erscheinen wenn sie zufällig generiert wurden.

Warum ist es unmöglich, in einem deterministischen Gerät wirklich Zufallszahlen zu erzeugen? Was bedeutet dieser Satz?

Man sollte nach einem kryptografisch sicheren Pseudozufallszahlengenerator suchen . Die meisten PRNG sind lineare Kongruenzgeneratoren (also next numbereine lineare Funktion von previous number). Wenn Sie also next numbergegen zeichnen, erhalten previous numberSie ein Diagramm mit parallelen Linien. Ein CSPRNG wird das nicht tun. Der Kompromiss ist, dass sie langsam sind.

Ich gruppiere Zufallszahlengeneratoren in 3 Kategorien :

1. Gut genug für die Hausaufgaben.
2. Gut genug, um auf Ihre Firma zu wetten.
3. Gut genug, um auf dein Land zu wetten.

Warum ist es unmöglich, in einem deterministischen Gerät wirklich Zufallszahlen zu erzeugen?

Ein deterministischer Gerät wird immer die gleiche Leistung erzeugen , wenn die gleichen Ausgangsbedingungen und Eingänge gegeben - das ist , was es bedeutet , zu sein deterministic. "Wirklich zufällige Zahl" ist eher eine philosophische Sichtweise, denn was es bedeutet, zu sein, randomist der Kern des philosophischen Nabelschauens (die Leute sind sich nicht einmal sicher, ob der atomare Zerfall zufällig ist oder einem Muster folgt, das wir einfach nicht herausfinden können noch). Ein kryptografisch sicherer Zufallszahlengenerator benötigt eine externe Entropiequelle, um das Gerät nicht deterministisch zu machen.

Wahre Zufälligkeit impliziert Nichtdeterminismus. Wenn es deterministisch ist, kann es genau vorhergesagt werden (das bedeutet Determinismus); Wenn es vorhergesagt werden kann, ist es nicht zufällig.

Das Beste, was Sie von einem deterministischen Pseudozufallszahlengenerator erhalten können, ist ein Strom von Zahlen mit einem sehr langen Zyklus (das Nichtwiederholen ist unmöglich, es sei denn, Ihr RNG-Gerät verfügt über unbegrenzten Speicherplatz), der für die Länge des Zyklus a erzeugt Stream-Nummern, die alle anderen Eigenschaften einer zufälligen Sequenz erfüllen (wobei eine gleichmäßige Verteilung der Werte am interessantesten ist).

Um dieses Problem zu lösen, haben viele moderne UNIXe und Unix-ähnliche Kernel-RNGs, die physikalische Rauschquellen verwenden, um echte Zufälligkeit zu erzeugen.

Ein weiterer gängiger Ansatz besteht darin, die aktuelle Zeit als Ausgangswert für ein deterministisches RNG ( srand(time(NULL));in C) zu verwenden. kryptografisch ist dies wertlos, da die aktuelle Zeit kein Geheimnis ist, aber für Dinge wie physische Simulationen oder Videospiele ist es gut genug.

Das zweite Kapitel des Buches Diskrete Ereignissimulation: Ein erster Kurs von Lawrence Leemis bietet eine fantastische Einführung in Zufallszahlengeneratoren (genauer gesagt Pseudozufallszahlengeneratoren).

Ein Auszug aus seinem Buch erklärt es meiner Meinung nach gut:

In der Vergangenheit wurden drei Arten von Zufallszahlengeneratoren für Computeranwendungen empfohlen: (a) Nachschlagetabellengeneratoren im Stil der 1950er Jahre, wie zum Beispiel die RAND-Korporationstabelle mit einer Million Zufallszahlen; (b) Hardware-Generatoren wie zum Beispiel thermische "weißes Rauschen" -Geräte; und (c) algorithmische (Software-) Generatoren. Von diesen drei Typen haben nur algorithmische Generatoren eine breite Akzeptanz erreicht. Der Grund dafür ist, dass nur algorithmische Generatoren das Potenzial haben, alle der folgenden allgemein akzeptierten Kriterien zur Erzeugung von Zufallszahlen zu erfüllen. Ein Generator sollte sein:

• zufällig - in der Lage, eine Ausgabe zu erzeugen, die alle angemessenen statistischen Zufallstests besteht;
• steuerbar - kann auf Wunsch seine Ausgabe reproduzieren;
• tragbar - in der Lage, dieselbe Ausgabe auf einer Vielzahl von Computersystemen zu erzeugen;
• effizient - schnell, mit minimalen Anforderungen an Computerressourcen;
• dokumentiert - theoretisch analysiert und ausgiebig getestet.

Während es möglich sein könnte, einen Generator für weißes Rauschen zu verwenden, um "bessere" Zufallszahlen zu erhalten, haben sie sich nicht durchgesetzt, da sie die meisten der oben genannten Kriterien nicht erfüllen.

Ich würde empfehlen, dass Sie ein Exemplar dieses Buches (oder etwas Ähnliches) in die Hände bekommen. Wenn Sie genau wissen, wie PRNG arbeitet, können Sie Ihre Bemühungen definitiv unterstützen.

Weil Sie Code schreiben müssen, um die Zufallszahlen zu generieren, und Code NICHT zufällig ist. (Es ist deterministisch)

Sie beginnen also mit einem oder mehreren "Seed-Werten", die bei "Random" (normalerweise dem aktuellen Zeitstempel) ausgewählt wurden, und verwenden ihn dann in einem Algorithmus, um mit der Generierung von Zahlen zu beginnen. Das gesamte Set basiert jedoch auf dem ursprünglichen Seed-Wert!

Also , wenn Sie Ihren Code erneut mit dem exakt gleichen Seed - Wert (e) ausführen, werden Sie die exakt gleiche Menge von Zahlen bekommen! Wie kann eine vernünftige Person das als Zufall bezeichnen? Aber es sieht wirklich zufällig aus.

Wenn Sie sie eindeutig machen möchten, überprüfen Sie nach dem Generieren einer Nummer einfach, ob Sie diese Nummer bereits haben. Wenn Sie dies tun, werfen Sie sie weg und generieren Sie eine neue Nummer.

Da Sie Zufallszahlen generieren, sollten Sie erwarten, dass die generierten Werte nicht eindeutig sind. Dies ist eine Eigenschaft der Zufälligkeit - Sie können nicht sagen, dass eine Folge von wirklich zufälligen (oder sogar pseudozufälligen) Zahlen eindeutig ist, da diese Anforderung es ermöglichen würde, den endgültigen Wert im Bereich vorherzusagen und die Wahrscheinlichkeit von zu ändern alle nicht gewählten Nummern bei jeder Auswahl einer neuen.

Ich habe eine sehr einfache Definition von Pseudo Random :

Zu viele unbekannte Variablen zur Vorhersage.

Ich habe auch eine einfache Definition von True Random :

Unendlich unbekannte Variablen.

Das Problem mit einem Computer ist, dass er immer ALLE Variablen kennt. Die Zufallszahl ist einfach eine mathematische Funktion eines Startwerts .
Das Beste, was wir tun können, ist, dem Computer einen pseudozufälligen Startwert zu geben, der normalerweise auf einer Variablen basiert, die wir nicht vorhersagen können (wie die genaue Zeit).

Obwohl ein Computer absolut nicht in der Lage ist, eine Zufallszahl zu erstellen, ist es gut, zu viele Variablen einzuführen, um sie vorherzusagen!

Es ist in der Tat nicht möglich, echte Zufallszahlen in Software zu generieren, wie andere darauf hingewiesen haben. Mit Hardware ist es jedoch möglich, ein Gerät zu bauen, das echte Zufallszahlen * generieren kann. Im Internet gibt es einige Beispiele dafür, und es gibt eine Vielzahl von Methoden, von der Messung der Zeit zwischen den Ticks am Geigerzähler bis zur Abtastung des weißen Rauschens (meistens Hintergrundstrahlung aus dem Universum) eines nicht abgestimmten Empfängers. Ich selbst habe ein paar mit ein paar der verfügbaren Methoden gebaut.

* Jeder gute Physikfreak wird darauf hinweisen, dass angesichts der Art und Weise, wie das Universum funktioniert, keines dieser Elemente hypertechnisch rein zufällig ist, es jedoch keinen vernünftigen Weg gibt, die Ergebnisse vorherzusagen, sodass sie für diese Diskussion ausreichen.

Ohne spezielle Hardware können Sie auf keinen Fall eine Zufallszahl erzeugen. In meinem ersten Jahr schlugen ein paar Klassenkameraden und ich einen Zufallszahlengenerator vor, der im Grunde einen AM-Empfänger hat und auf 4 verschiedene Kanäle abgestimmt ist, um den Eingang in einen A / D-Wandler zu bekommen und alle zu addieren (modulo Ihre maximale Anzahl). Da die Kombination des analogen Eingangs von einer beliebigen Anzahl von Stationen zufällig ist und wir mit dem A2D-Konverter eine große Anzahl von Zufallszahlen erzeugen könnten, schlugen wir vor, dass dies ein guter Generator sein könnte. Selbstverständlich ist auch dies im philosophischen Sinne nicht wirklich zufällig, obwohl dies für die meisten praktischen Zwecke funktionieren könnte.

Determinismus ist im Wesentlichen eine Funktion. Denken Sie aus der Algebra daran, dass eine Funktion eine Entsprechung zwischen einer Domäne und einem Bereich ist, sodass jedes Mitglied der Domäne genau einem Mitglied des Bereichs entspricht.

Also, wenn f (x) = z, f (x)! = Y, es sei denn, y ist z. Das ist eine Funktion. Stellen Sie sich JavaScript vor:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

Egal wie oft Sie es aufrufen, Add(2,3)es wird immer 5 zurückgegeben. Mit anderen Worten, Add () ist eine deterministische Funktion.

Externe Faktoren können dazu führen, dass sich Add nicht deterministisch verhält. Zum Beispiel, wenn Sie Multithreading in die Gleichung einführen. Menschliche Eingaben verursachen auch Nichtdeterminismus.

Jetzt wird es interessant.

"Wer arithmetische Methoden zur Erzeugung von Zufallszahlen in Betracht zieht, befindet sich natürlich in einem Zustand der Sünde."

Anmerkung Von Neumann führt aus, "arithmetische Methoden zur Herstellung von [...]". Dies spricht nicht über menschliche Eingabe, Parallelität, lesenen Musterwindgeschwindigkeiten von einem präzisen Instrumente oder andere nicht-algorithmische Weise von Zufall Herstellung Eingang auf eine deterministische Funktion.

Dies besagt einfach, dass eine Funktion oder ein Funktionssystem nicht plötzlich nicht deterministisch werden wird. Mit anderen Worten, Add (2,3) gibt bei gleichen Eingaben weder 6 noch etwas anderes als 5 zurück . Das ist unmöglich.

Der zitierende Autor geht noch einen Schritt weiter.

Das Beste, auf das wir hoffen können, sind Pseudozufallszahlen, ein Strom von Zahlen, die so aussehen, als ob sie zufällig generiert wurden.

Der Kontext wurde zuvor als "auf einem deterministischen Gerät" definiert. Ich könnte den Streit hier beenden. Was aber, wenn wir den Kontext ändern, indem wir dem System ein neues Element hinzufügen? Ein nicht deterministisches Element, das als Eingabe hinzugefügt wird, macht das System zu einem nicht deterministischen System. Durch Entfernen des nicht deterministischen Elements werden wir jedoch auf ein deterministisches System zurückgeführt. Wenn wir die Eingaben irgendwie verfolgen oder anderweitig reproduzieren können, können wir ein Ergebnis reproduzieren. Aber dieser ganze Absatz ist tangential zu dem, was der Autor sagt. Erinnere dich an den Kontext.

Man könnte über die Bedeutung des Nichtdeterminismus streiten. Noch einmal tangential. Erinnere dich an den Kontext.

Er hat also recht. Auf jedem deterministischen Gerät ist es für ein deterministisches System unmöglich, ein echtes Zufallsergebnis zu erzeugen.