mikrocontroller.net

Forum: Offtopic Feststellen wie zufällig Zufallszahlen sind


Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: The Devil (devil_86)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://de.wikipedia.org/wiki/Chi_Quadrat_Test
Du mußt wissen welcher Verteilung das ganze genügen soll.
(Gleichverteilung ...)

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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/

Autor: Dr. Robotnik (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tom (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Tom (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Btw - ein guter Komprimierer macht genau das von Jörg vorgeschlagene.

Autor: Pragmatiker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: sssttata (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Tom (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

wo DNA-Sequqnzen damit untersucht werden.

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.