Hallo, angenommen ich verfüge über 10^6 natürliche Zahlen jeweils zwischen 1 und 10. Jemand behauptet die Zahlen seien zufällig erzeugt worden. Gibt es eine Methode festzustellen zu welcher Wahrscheinlichkeit das stimmt? Überlegung: Wenn alle Zahlen = 2 wären, dann wäre die Wahrscheinlichkeit, dass alle Zahlen zufällig sind sehr gering. Wenn alle Zahlen ungefähr gleich oft vorkommen, heißt das ja auch nicht unbedingt dass die Zahlen zufällig sind, es könnte z.B. eine Folge wie 1, 2, 3,4,5,6,7,8,9,1,2,3,.. sein. Irgendeine Idee? Danke, Thomas
Auch wenn jedesmal z.B. zweien kommen können die Zahlen zufällig sein. Jede Zahl von 1 bis 10 hat die gleiche Wahrscheinlichkeit vorzukommen.
http://de.wikipedia.org/wiki/Chi_Quadrat_Test Du mußt wissen welcher Verteilung das ganze genügen soll. (Gleichverteilung ...)
Bei 10^6 sollte es gleichverteit sein, aber wirklich feststellen kann
man das eher nicht. Bei Verschlüsselung braucht man gute Zufallszahlen,
da gibt es jede Menge Literatur über deren Erzeugung.
Es ist aber auch nicht schwer, Pseudozufallszahlen mit einer Periode
>10^6 zu erzeugen, die sehr gut gleichverteilt sind. Ohne Kenntnis des
Verfahrens ist es prinzipiell unmöglich, herauszubekommen, ob es echte
Zufallszahlen sind oder dich jemande beschei?t. Nur das Verfahren der
Herstellung sagt was aus.
Thomas wrote: > Hallo, > > angenommen ich verfüge über 10^6 natürliche Zahlen jeweils zwischen 1 > und 10. > > Jemand behauptet die Zahlen seien zufällig erzeugt worden. > > Gibt es eine Methode festzustellen zu welcher Wahrscheinlichkeit das > stimmt? > > Danke, > Thomas Der am häufigsten eingesetzte Test (bzw. Testbatterie) dürfte wohl der Diehard sein. http://www.stat.fsu.edu/pub/diehard/
Eine ganz nette erste Korrelationsanalyse, wie ich finde, die Zahlenfolge in Tupel bzw. Tripel zu zerlegen und sich dann den 2D- bzw. 3D-Plot davon anzuschauen. Gibt es korrelationen, erkennt man sofort ein MUster. Sind die Zahlen gleichverteilt wird die Zahlenebene, bzw. der Würfel homogen gefüllt. Kann man rel. Schnell in Mathematika schreiben und ist auch recht anschaulich. So habe ich z.B. einen selbstgebauten hardware-zufallszahlengenerator mit pseudo-zufallszahlen-algorythmen vergleichen könnnen. Wenn ich mich recht erinnere kann man auch die Entropie der Zahlenfolge berechnen. Für echte Zufallszahlen wird die Entropie maximal.
Also eine einzige Methode, die die Qualität der Zufälligkeit feststellt, gibt es nicht. Es gibt aber viele Techniken, die verschiedene Aspekte testen. Als guter Start: Teste per Histogramm die Verteilung. Gleichverteilungen lassen sich so sehr einfach verifizieren. Dieser Test stellt aber nur die Notwendigkeit fest, nicht aber ob es hinreichend ist. Dann: Korrelationen überprüfen. Teile dazu die Zufallszahlen in (z.B. 10,20,100 etc) Gruppen auf, wobei die erste Zahl in die Erste, die zweite Zahl in die zweite Gruppe ... die n-te dann wieder in die erste Gruppe usw. Zeichnest du nun die Zahlen zweier (oder mehr) Gruppen in einem Korrelationsdiagramm ein, dann sollte sich bei jeder beliebigen Wahl der Gruppen immer ein visuell zufälliges Muster (bei Gleichverteilung: die gesammte Fläche gleichverteilt bedeckt) ergeben und keine Puktwolke oder Wolke entlang einer Geraden. Gruss Jörg
Fürs Grobe würde ich die Zahlen in eine Datei schreiben und dann komprimieren (ZIP, RAR oder so). 3,3 bit pro Zahl mal 1 Million sind etwas über 400 kByte. Wenn die Dateigröße in höchster Kompressionsstufe kleiner ist, dann sind die Zahlen nicht zufällig.
Btw - ein guter Komprimierer macht genau das von Jörg vorgeschlagene.
Der beste Test, ob 10^6 Zahlen zufällig sind, ist folgender: Veröffentliche die ersten 999000 Zahlen und schreibe einen Wettbewerb aus, dass derjenige 1000000€ gewinnt, der die letzten 1000 Zahlen aus dem Anfang rekonstruiert. Du kannst die Signifikanz des Ergebnisses kontrollieren a) mit dem Anteil der veröffentlichen Zahlen b) mit der Höhe des Preisgeldes.
array unsigned int a[10]//alle Felder nullen
for(i=0;i<10^6;i++)
{
a[rand_1_10()-1]++;
}
gucken ob a[0] -> a[9] ungefährt gleich.
Lies nochmal die Fragestellung. > Wenn alle Zahlen ungefähr gleich oft vorkommen, heißt das ja auch > nicht unbedingt dass die Zahlen zufällig sind, es könnte z.B. eine > Folge wie 1, 2, 3,4,5,6,7,8,9,1,2,3,.. sein.
Ein χ²-Test geht auf die Ergebnismenge. Ich seh nicht, wie die Reihenfolge der Glieder da eingehen könnte. Wenn man den Test auf die charakteristische Funktion eines Wertes umbauen würde (zB b_i=1, falls a_i=3, 0 sonst) könnte man immer noch nicht Folgen erkennen, die zB periodisch sind. Mir würde Multiskalenanalyse einfallen, also zum Beispiel ne Wavelet-Trafo. Damit könnte man Regelmässigkeiten erkennen wie zB periodische Folgen oder wenn bestimmte Werte lokal seltener/öfter vorkommen. Ein Beispiel mit Bildchen ist etwa http://bioinform.genetika.ru/projects/reg/wavelets/wavelets.html wo DNA-Sequqnzen damit untersucht werden.
Links wiedergefunden: Neben den schon erwähnten Diehard-Tests http://www.stat.fsu.edu/pub/diehard/ gibt's noch eine Testbatterie vom NIST http://csrc.nist.gov/groups/ST/toolkit/rng/index.html und Min-Entropy: http://en.wikipedia.org/wiki/Min-entropy
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.