Prüfung auf "Zufälligkeit"

Zvoni

Erfahrenes Mitglied
Hiho an alle.

ich habe einen Lotto-Algoritmus entworfen (und auch schon geschrieben), und würde jetzt gerne wissen, ob man diesen Algoritmus auf "Zufälligkeit" prüfen kann.

Hintergrund: Ich habe meinen Algoritmus gegen Fisher-Yates (Knuth-Shuffle) antreten lassen, und zwar in der Konfiguration:
10.000 aus 100.000.000 (Zehntausend aus Hundert Millionen) ohne Zurücklegen und ohne Beachtung der Reihenfolge (wobei die Reihenfolge für den Test unerheblich ist, da das ja nur eine Sortierung ist bei beiden Algo's).

Ergebnis:
Mein Algo ca. 2 Sekunden
Fisher-Yates ca. 18 Sekunden

Fisher-Yates ist ja bekanntlich ein anerkannter Algoritmus, und das schon seit Jahren.
Mich würde es jetzt interessieren, ob es ein Verfahren/Tool gibt, die Ergebnis-Menge zu prüfen, ob mein algo die gleiche "Zufälligkeit" aufweist wie beim Knuth-Shuffle.

Ich habe in einem anderen Forum einen Hinweis auf so ein Verfahren bekommen, werde aber nicht wirklich schlau daraus
Diehard Battery-Tests: http://stat.fsu.edu/pub/diehard/
 

Bratkartoffel

gebratene Kartoffel
Premium-User
Hi,

kenne mich da aus mathematische Sicht nicht so gut aus, aber mir fallen auf die Schnelle mal zwei Möglichkeiten zum Testen ein.

Du könntest dir die Zufallszahlen als Bytes generieren lassen, diese in einer Datei speichern und anschließend dann (zum Beispiel mit HxD) die Menge der einzelnen Bytes anschauen. Die Verteilung der Bytes von 0x00 bis 0xFF sollte ziemlich regelmäßig sein.

Eine andere Möglichkeit wäre es die oben genannte Datei dann zu komprimieren. Je größer der Zufall, desto weniger kann die Datei komprimiert werden.

Grüße,
BK
 

ComFreek

Mod | @comfreek
Moderator
Zufall zu prüfen ist nicht gerade trivial.

Ganz grobe Fehler deines Algorithmus könntest du allerdings leicht ausschließen, wenn du sehr viele Datenmengen generierst und prüfst, inwieweit die Häufigkeiten der Ergebnismengen abweichen.
Im besten Fall sollten sie nur sehr wenig abweichen.
 

Zvoni

Erfahrenes Mitglied
Hmmm, also um es jetzt vereinfacht darzustellen:
Ich lasse 10.000 mal meinen algo "6 aus 49" spielen, und führe statistik, wie oft jede zahl gezogen wurde, und theoretisch müssten alle zahlen mehr oder weniger gleich oft auftauchen?
Meinst du das?
 

sheel

I love Asm
Genau.

Aber wie Comfreek schon schreibt:
Einigermaßen gleiche Anzahlen sind zwar gut
aber keine 100%-ige Garantie für Zufälligkeit.

Zu den Diehard-Tests liefert Wikipedia + Links übrigens Genaueres.
 

Zvoni

Erfahrenes Mitglied
OK, werd ich mal ein wenig mit den DieHard-Tests rumspielen. Die Windows/DOS-Version habe ich mir schon gezogen. Werd mir mal die Dokus dazu angucken, und schauen ob ich da genauer durchsteige