Können Sie Pi als einen einfachen Zufallsgenerator verwenden?

30

Ich habe diese Frage kürzlich bei math.SE gesehen. Es hat mich zum Nachdenken gebracht. Könnte Pi als grober Zufallsgenerator verwendet werden? Ich meine, die Ergebnisse sind bekannt (wie lange wurde pi bis jetzt berechnet?), Aber Pi scheint ziemlich zufällig zu sein, wenn man 1 Ziffer auf einmal nimmt.

Ergibt das überhaupt einen Sinn?

Earlz
quelle
Wo werden diese Zufallszahlen verwendet?
NullUserException
2
Theoretisch könnte es sein, aber es wäre wahrscheinlich weniger optimal als die derzeitigen Methoden. Nur Instinkte dazu, aber es scheint, dass der zufällige Pool auf diese Weise mit weniger Aufwand größer ist.
Rig
@NullUserException Nicht sicher ... Ich habe mich nur gefragt, ob sie überhaupt verwendet werden können. Ich
gehe
3
@FrustratedWithFormsDesigner - Teil des ent-Pakets. Es verwendet die Zufallszahlen, um die Fläche eines Kreises zu berechnen, der in ein Quadrat eingeschrieben ist, und daraus kann man pi berechnen. Unter Verwendung der Bits von pi als Zufallszahlen gibt es eine gewisse Eleganz, um diese Daten zur Berechnung von pi zu verwenden.
1
@FrustratedWithFormsDesigner ent ist eine Code-Suite zur Analyse der Pseudozufälligkeit von Bytes. Ein Test darin ist ein Monte Carlo zur Berechnung des Pi und zum Vergleich der Zufallsberechnung mit dem tatsächlichen Wert, um zu sehen, wie zufällig er ist.

Antworten:

50

Durchsuchen Sie http://www.befria.nu/elias/pi/binpi.html , um den Binärwert von pi zu erhalten (damit es einfacher war, in Bytes zu konvertieren, als Dezimalstellen zu verwenden) und führen Sie ihn dann durch ent Für eine Analyse der zufälligen Verteilung der Bytes bekomme ich folgendes:

Entropie = 7,954093 Bits pro Byte.

Eine optimale Komprimierung würde die Größe dieser 4096-Byte-Datei um 0 Prozent verringern.

Die Chi-Quadrat-Verteilung für 4096 Stichproben beträgt 253,00 und würde diesen Wert in 52,36 Prozent der Fälle zufällig überschreiten.

Der arithmetische Mittelwert der Datenbytes beträgt 126,6736 (127,5 = zufällig).

Der Monte-Carlo-Wert für Pi beträgt 3,120234604 (Fehler 0,68 Prozent).

Der serielle Korrelationskoeffizient beträgt 0,028195 (völlig unkorreliert = 0,0).

Also ja, wenn Sie pi für zufällige Daten verwenden, erhalten Sie ziemlich zufällige Daten ... und erkennen, dass es sich um bekannte zufällige Daten handelt.


Aus einem Kommentar oben ...

Abhängig davon, was Sie tun, können Sie jedoch die Dezimalstellen der Quadratwurzel einer beliebigen Primzahl als Zufallsgenerator verwenden. Diese sollten mindestens gleichmäßig verteilte Ziffern haben. - Paxinum

Also habe ich die Quadratwurzel von 2 in binär berechnet, um die gleichen Probleme zu lösen. Mit Wolframs Iteration habe ich ein einfaches Perl-Skript geschrieben

#!/usr/bin/perl
use strict;
use Math::BigInt;

my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;

while(1) {
    my $unew;
    my $vnew;

    if($u->bcmp($v) != 1) { # $u <= $v
        $unew = $u->bmul(4);
        $vnew = $v->bmul(2);
    } else {
        $unew = ($u->bsub($v)->bsub(1))->bmul(4);
        $vnew = ($v->badd(2))->bmul(2);
    }   

    $v = $vnew;
    $u = $unew;

    #print $i,"  ",$v,"\n";
    if($i++ > 10000) { last; }
}

open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);

Läuft dies für die ersten 10 übereinstimmenden A095804, so war ich zuversichtlich, dass ich die Sequenz hatte. Der Wert v n, wie er binär geschrieben ist, wobei der Binärpunkt nach der ersten Ziffer liegt, ergibt eine Annäherung an die Quadratwurzel von 2.

Die Verwendung von ent gegen diese Binärdaten erzeugt:

Entropy = 7.840501 bits per byte.

Optimum compression would reduce the size
of this 1251 byte file by 1 percent.

Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.

Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).

quelle
Genau die Art der Antwort, nach der ich gesucht habe. Ich habe keine Ahnung, wie ich all diese
Dinge
Müssen Sie nicht einen Weg finden, um einen Teil davon zufällig auszuwählen, auch wenn die Zahlenverteilung ziemlich zufällig ist ?
Blumer
1
@Blumer Nr. Die Zufälligkeit wird an einer Folge von Zahlen gemessen. Die Folge von pi-Ziffern soll zufällig sein. Siehe en.wikipedia.org/wiki/Statistical_randomness
Simon Bergot
11
Absolut richtig. Und weil es sich um bekannte Zufallsdaten handelt, trauen Sie sich nie, diese für kryptografische Zwecke zu verwenden.
Falcon
3
+1 für "bekannte Zufallsdaten". Wenn Sie zufällige Daten benötigen, die jemand nicht erraten kann, ist pi nichts für Sie. Wenn Sie aus irgendeinem Grund nur eine Reihe zufälliger Zahlen benötigen, funktioniert es einwandfrei.
Jmoreno
5

Nun, neben anderen Eigenschaften eines Zufallszahlengenerators möchten Sie wahrscheinlich, dass es sich um eine normale Zahl handelt . Einige Antworten in der math.SE-Frage, die Ihre Frage inspiriert haben, weisen darauf hin, dass pi derzeit als normal angesehen wird, aber nicht bewiesen wurde.

bA
quelle
2

Ein solcher Generator wäre ein Pseudozahlengenerator, dh bei gleichem Startwert wäre das Ergebnis immer das gleiche. In den meisten Frameworks gibt es jedoch das gleiche Problem, wenn Sie den Standard-Zufallszahlengenerator verwenden: Pseudozufall.

Die Verteilung der Ziffern scheint den Standard-Zufallszahlengeneratoren ziemlich ähnlich zu sein¹, so dass die Ziffern von π für gewöhnliche Szenarien zur Erzeugung von Zufallszahlen verwendet werden können.

Das Problem ist, dass der Algorithmus im Vergleich zu gewöhnlichen Zufallszahlengeneratoren wahrscheinlich sehr langsam sein wird, sodass er in der Praxis nicht sehr nützlich ist.


¹ Ich glaube, es ist wahr, aber ich habe keinen Beweis. Es wäre interessant (und nicht kompliziert), einen Vergleich auf der Grundlage einer großen Anzahl von Zahlen durchzuführen.

Arseni Mourzenko
quelle
5
@NullUserException: Nein, einige Zufallszahlengeneratoren verwenden eine Entropiequelle. Dies kann entweder über spezielle Hardware erfolgen (der Ansatz von random.org ) oder unter Verwendung vorhandener Entropiequellen (messbare Schwankungen innerhalb vorhandener Hardwaresensoren, bestimmte Arten von Benutzerinteraktionen, Mikrovariationen bei bestimmten Arten von Leistungstests usw.). ).
Brian
1
@NullUserException: Es gibt kryptografisch gesichertes PRNG, das immer noch pseudozufällig ist. Dann gibt es echte RNG, die auf Eingaben aus der realen Welt basieren: radioaktiver Zerfall, Lärm usw.
Arseni Mourzenko
2
@MainMa Aber selbst dann ist die Zufälligkeit von radioaktivem Zerfall, Umgebungsgeräuschen, die von Benutzereingaben usw. herrühren, umstritten. Nur weil wir ein Muster nicht erkennen, heißt das nicht, dass es nicht existiert.
NullUserException
1
@NullUserException: Letztes Jahr veröffentlichten Colbeck / Renner einen Artikel, der beweisen soll: "Keine Erweiterung der Quantentheorie kann die Vorhersagekraft verbessern." Unter der Annahme, dass dies zutrifft, kann es eine Entropiequelle geben, die wirklich unvorhersehbar ist, anstatt nur unmöglich vorherzusagen.
Brian
1
@MainMa - Sie würden immer noch mathematische Tests für die Zufälligkeit durchführen. Obwohl die zugrunde liegende Physik zufällig ist (nach unserem besten Wissen), bedeutet dies nicht, dass es sich um eine Messung handelt. Detektoren aller Art haben in der realen Welt eine Menge 'interessantes' Verhalten
Martin Beckett
2

Die Zufälligkeit der Ziffern von pi (oder auch jeder anderen Sequenz) kann wohl durch sogenannte "Batterietests" überprüft werden. Ein beliebter Batterietest ist der von George Marsaglia Diehard Battery Test von . Es gibt auch die NIST-Sonderpublikation 800-22 , die eine Reihe solcher Tests und die Ergebnisse der Anwendung dieser Tests auf eine Reihe physikalischer Konstanten beschreibt, einschließlich -lo und behold -pi für über eine Million Bits. Das Ergebnis von pi ist in Anhang B des Berichts angegeben und sieht folgendermaßen aus:

Statistical Test                            P-value
Frequency                                   0.578211
Block Frequency (m = 128)                   0.380615
Cusum-Forward                               0.628308
Cusum-Reverse                               0.663369
Runs                                        0.419268
Long Runs of Ones                           0.024390
Rank                                        0.083553
Spectral DFT                                0.010186
Non-overlapping Templates (m = 9, B = 000000001)          0.165757
Overlapping Templates (m = 9)               0.296897
Universal                                   0.669012
Approximate Entropy (m = 10)                0.361595
Random Excursions (x = +1)                  0.844143
Random Excursions Variant (x = -1)          0.760966
Linear Complexity (M = 500)                 0.255475
Serial (m = 16, 2m∇Ψ )                      0.143005

Ist pi ein guter Zufallsgenerator? Sehen Sie sich die obigen Ergebnisse an (oder durchsuchen Sie die Bedeutungen der Variablen in der linken Spalte, wenn Sie keine Ahnung haben, was sie bedeuten) und prüfen Sie, ob sie Ihren Anforderungen entsprechen.

sm535
quelle
1
Das Read me für Diehard sagt, dass es ungefähr 10-12 Megabyte Binärdaten benötigt (das Beste, was ich finden konnte, sind 32 Kilobyte). Wenn Sie es gegen die ASCII-Daten laufen lassen, würde der Test ziemlich weit von dem entfernt sein, was die Anwendung erwartet.
Meine Antwort lautete auf die OP-Frage und die ursprüngliche Frage zu Math.SE - von denen keine etwas über ASCII im Vergleich zu Binärdaten oder die Länge der Stichprobe sagte. Wie kann die statistische Zufälligkeit einer Sequenz ohne ausreichend großen Stichprobenumfang bestimmt werden?
sm535