Der beste Weg, um festzustellen, ob eine Liste von Bytes zufällig ist?

Gibt es da draußen einen Algorithmus, der einen Wert zurückgeben kann, der einen Grad an Zufälligkeit anzeigt? Ich glaube, es heißt Datenentropie .

Ich habe kürzlich diesen Artikel gelesen: http://faculty.rhodes.edu/wetzel/random/mainbody.html

Würde sein Ansatz, Münzwürfe zu analysieren, für Bytes gelten? Sollte ich wieder auf die Bitebene fallen, wo es wieder wahr / falsch ist, oder gibt es eine Möglichkeit, anhand des Vollbytewerts zu bestimmen?

Sind ihre besseren Analysen als dieser Artikel?

In TCS bestand ein anderer Ansatz für dieses Problem darin, Eigenschaften von Verteilungen zu testen , wobei zu unterscheiden ist, ob eine Verteilung (wirklich) gleichmäßig verteilt ist oder "nicht einmal annähernd" (auf formale Weise) einheitlich ist. Hier erhält man genaue Grenzen für die Anzahl der Proben, die zur Entscheidung über die Frage benötigt werden.

Siehe zum Beispiel Abschnitt 6 des folgenden Tutorials: http://people.csail.mit.edu/ronitt/papers/icm.ps

Insbesondere kann man entscheiden, ob eine Verteilung auf wirklich gleichmäßig ist oder ϵ- weit (in der gesamten Variationsentfernung ) von der Uniform mit O ( $[n]$$\epsilon$Abfragen / Stichproben aus der genannten Verteilung. (Dies ist auch in dem Sinne eng, dassΩ($O(\sqrt{n}/\epsilon^4)$Proben werden benötigt.)$\Omega(\sqrt{n})$

Es gibt keinen einzigen korrekten Algorithmus zur Messung der Zufälligkeit. Verschiedene statistische Tests sind ein möglicher Ansatz, wie die anderen bereits gesagt haben. Eine andere Möglichkeit besteht darin, die Bytesequenz zu komprimieren und zu sehen, was passiert. Wenn Sie ungefähr 8 Bit / Byte (oder mehr) erhalten, ist die Sequenz in Bezug auf das dem Kompressor zugrunde liegende Datenmodell zufällig.

Von den Standardkomprimierungsmethoden verwendet PPM ein explizites statistisches Modell, um das nächste Zeichen basierend auf dem vorhergehenden Kontext vorherzusagen. Seine Hauptschwäche besteht darin, dass es keine groß angelegte Wiederholbarkeit wie identische Wiederholungen einer langen zufälligen Sequenz nutzen kann.

Komprimierungsmethoden, die auf dem LZ77-Parsing oder der Burrows-Wheeler-Transformation (BWT) basieren, funktionieren gut, wenn die Sequenz viele wiederholte Teilzeichenfolgen enthält. Viele praktische Implementierungen haben jedoch eine begrenzte Block- / Fenstergröße, um Speicherplatz zu sparen, so dass sie auch keine Wiederholungen in großem Maßstab nutzen können.

Anstatt die Sequenz zu komprimieren, können Sie auch ein Maß für das Datenmodell des Kompressors berechnen: empirische Entropie höherer Ordnung für PPM, die Anzahl gleicher Buchstabenläufe in der BWT oder die Anzahl der Phrasen in der LZ77-Analyse. In den ersten beiden Fällen laufen 8 Entropiebits pro Byte oder n (1 - 1/256) für eine Folge der Länge n, was vollständig zufällige Daten bedeutet.

Von random.org:

Seltsamerweise ist es theoretisch unmöglich zu beweisen, dass ein Zufallszahlengenerator wirklich zufällig ist. Vielmehr analysieren Sie eine zunehmende Anzahl von Zahlen, die von einem bestimmten Generator erzeugt werden, und abhängig von den Ergebnissen steigt (oder sinkt Ihr Vertrauen in den Generator).

Weitere Informationen finden Sie hier

http://www.phy.duke.edu/~rgb/General/dieharder.php

Die Kolmogorov-Komplexität ist eine Möglichkeit, die Zufälligkeit von Zeichenfolgen zu messen, und sie ist algorithmisch nicht berechenbar. Mit diesem Begriff ist es unmöglich, die Zufälligkeit aller Zeichenfolgen zu messen. Die Existenz eines solchen Algorithmus könnte verwendet werden, um das Halteproblem zu lösen.

Wie in anderen Antworten erwähnt, ist die Entscheidungsversion dieses Problems (wie das Halteproblem und eine Reihe anderer Probleme wie das Kachelproblem) unentscheidbar. Ich glaube jedoch, dass Sie nach praktischen Möglichkeiten fragen, um die Zufälligkeit einer Sammlung von Bits zu messen.

Die Standardpraxis besteht darin, die Daten einer Reihe von Zufälligkeitstests wie dem Chi-Quadrat-Test zu unterziehen.

$i_p$$(i_1/n,\ldots,i_k/n)$

In der Praxis gibt es keinen universellen Test für die Zufälligkeit von Streams, sondern eine Reihe von Tests. Wenn Ihr Stream k der besten Tests versucht und alle besteht, können wir ziemlich sicher sein, dass es zufällig ist ... bis jemand k + 1 erfindet. ' st Test, der es bricht.

Hier ist, was Knuth darüber in "Art of Computer Algorithms, Vol 2" sagt.

"Wenn sich eine Sequenz in Bezug auf die Tests T1, T2, ..., Tn zufällig verhält, können wir im Allgemeinen nicht sicher sein, dass es kein miserabler Fehler ist, wenn sie einem weiteren Test T (n + 1) unterzogen wird Jeder Test gibt uns immer mehr Vertrauen in die Zufälligkeit der Sequenz. In der Praxis wenden wir ungefähr ein halbes Dutzend verschiedene Arten von statistischen Tests auf eine Sequenz an, und wenn sie diese zufriedenstellend besteht, betrachten wir sie als zufällig - es wird dann angenommen unschuldig bis zum Beweis der Schuld."

Ich würde empfehlen, Knuths Abschnitt 3.1 "Kunst der Computeralgorithmen" zu lesen, um eine allgemeine Einführung in die Pseudozufälligkeit zu erhalten, und 3.3 über statistische Tests für Streams.

Ich habe eine ziemlich schwache Reihe von Tests durchgeführt, die für mich dennoch sehr nützlich waren und auf die Art der Zufälligkeitstests im Allgemeinen hinweisen:

1. Generieren einer Statistik für "bekannte gute Zufallsdaten" (entweder mathematisch oder empirisch)
2. Generieren Sie dieselbe Statistik für Ihre Probendaten (hoffentlich haben Sie mindestens 30 Proben oder so).
3. Holen Sie sich einen ap-Wert für die Differenz (Hypothesen: Diese stammen aus verschiedenen Verteilungen)
4. Wiederholen Sie dies für N Statistiken
5. bonferonni korrigiert die Ergebnisse (dividiert durch N)

Quelle ist hier: https://github.com/earonesty/dotfiles/blob/master/randbytestest.py