Wie testen, ob einige Zahlen gleichmäßig in einem Intervall verteilt sind?

Question

Ich bin auf der Suche nach einem Algorithmus (vorzugsweise mit einer Bibliothek in C++) oder eine Idee, um mir zu sagen, ob bestimmte Zahlen in einem Intervall gleichmäßig verteilt sind oder nicht. Stellen Sie sich vor, ich habe zwei Strings: der erste ist fehlerfrei und der zweite hat an einigen Stellen einige Fehler. Ich möchte überprüfen, ob die Position von Fehlern in der Zeichenfolge statistisch sinnvoll ist oder nicht.

betrachten Sie das folgende Beispiel. Im ersten Fall sind die Fehler gleichmäßig verteilt und im zweiten Fall sind sie alle am Ende des Strings, was mein Algorithmus einige Alarme darüber geben sollte.

error-free string: 0110110101010110101 (3 errors occur at pos:5,12,15) 
erroneous string : 0110010101000100101 

sedond Beispiel:

error-free string: 0110110101010110101 (3 errors occur at pos:17,18,19) 
erroneous string : 0110110101010110010 

kann ich sagen, die Fehler in den ersten Daten sind normal, aber nicht in dem zweiten.

Bisher bin ich zu dieser Idee gekommen: Ich möchte die Zeichenfolge in gleiche Bins aufteilen, nehme an, dass die Zeichenfolge Länge 100 ist. Ich wähle 10 bin Größe 10. Dann schaue ich auf die Gesamtzahl der Fehler in der String, von dem wir annehmen können, dass er 10 ist. Ich erwarte einen Fehler in jedem Fach. Jetzt berechne ich, wie weit meine Beobachtung statistisch von meiner Erwartung entfernt ist. Hat jemand eine Idee, ob diese Methode korrekt ist oder nicht? Und wenn es funktioniert, wie groß sollte jeder Behälter sein. Kommt es auf die Anzahl der Fehler an?

Answer 1

Der Ansatz, den Sie vorschlagen, in dem Sie die Zeichenfolge in Bins aufteilen, um die Anzahl der mehr oder weniger gleichmäßig unter den Bins verteilten Fehler zu sehen, ist blind für Muster wie "jede zehnte Position hat einen Fehler". Ich glaube, dass Sie einen allgemeineren Weg brauchen, um den Fall zu unterscheiden, in dem das Auftreten von Fehlern gleichgültig ist gegenüber den Positionen von dem Fall, in dem es ein Muster gibt, zu den Positionen, an denen Fehler auftreten.

Mit anderen Worten, ich denke, dass Sie tatsächlich nach einer Möglichkeit suchen, das Ausmaß zu messen, in dem eine binäre Zeichenfolge zufällig oder genauer musterfrei ist. Die ultimative mathematische Definition von String Patternlessness ist die Kolmogorov complexity der Zeichenkette, definiert als die Länge des kürzesten Programms, das die Zeichenkette ausgibt. Leider ist die Kolmogorov-Komplexität nicht berechenbar.

Eine Möglichkeit, die Musterlosigkeit einer binären Zeichenfolge zu berechnen, ist die Verwendung der Linear Hadamard Spectral Test. Der Test kann unter Verwendung der Fast Fourier Transform implementiert werden, um in Zeit O(n logn) zu laufen, wobei n die Länge der Zeichenfolge ist. Es scheint mir jedoch so, als ob es keine fertige Implementierung des Tests in C++ gibt.

Angenommen, Sie sind bereit, ein wenig Kompromisse bei der Robustheit des Tests einzugehen, um die Implementierung zu erleichtern, können Sie den folgenden Ansatz verwenden: Um die Patternlessness der Zeichenfolge zu messen, einfach gzip eine Datei deren Inhalt ist die Zeichenfolge, und überprüfen Sie dann das Komprimierungsverhältnis. Je schlechter die Komprimierung, desto mehr Patternless ist die Saite. Der Ansatz beruht auf der Tatsache, dass gzip einige Aspekte der Kolmogorov-Komplexität umfasst. Insbesondere verbessert das Vorhandensein etwas leicht zu erfassender Muster das Kompressionsverhältnis.