Überprüfen Sie, ob eine Zeichenfolge nicht zufällig ist

8

Hintergrund
Nehmen wir an, wir haben ein Alphabet von A,B, C, D, dann schauen wir uns einige Daten an und finden ein "Wort", bei dem DDDDDDDDCDDDDDDdie Wahrscheinlichkeit, diesen Zufall zu finden, für mich gering erscheint, während das Finden BABDCABCDACDBACDweniger zufällig erscheint.

Frage
Wie soll ich überprüfen, ob die Zeichenfolgen, auf die ich stoße, nicht zufällig sind?

Ich habe einige Dinge in R ausprobiert, z. B. die Buchstaben numerisch codiert und diese dann mit Permutationen verglichen. Die vorherige Codierung ist jedoch ziemlich umständlich, wahrscheinlich gibt es dafür einen direkteren Ansatz.

CodeNoob
quelle
12
Was genau meinst du in diesem Zusammenhang mit "zufällig"?
Gung - Reinstate Monica
3
Sie könnten eine n-Bit-Zustandsmaschine erstellen und dann aufzeichnen, wie viele Fehlvorhersagen sie macht. So ähnlich wie der Verzweigungsprädiktor einer CPU.
Alexyorke
1
Sie können die Wahrscheinlichkeit berechnen, dass eine Zeichenfolge durch einen bestimmten bekannten Prozess generiert wurde. Ob es "zufällig" ist, kann nicht bekannt sein (und ist wahrscheinlich keine aussagekräftige Frage).
OrangeDog
2
Sie könnten mit der Buchhaltung überprüfen .
Hlovdal
2
Wenn Sie sich eher auf Buchstabenfrequenzen als auf Sequenzen konzentrieren, ist der Chi-Quadrat-Test der tatsächlichen und der erwarteten Häufigkeit üblich. Das heißt, wenn Ihr erstes Beispiel "ungerade" ist, weil es viel zu viele "D" hat, während Ihr zweites eine ziemlich gleiche Anzahl von "A", "B", "C" und "D" hat, dann sind Sie ' Ich möchte die Anzahl von A, B, C und D mit den erwarteten Werten vergleichen. (Vielleicht ungefähr die gleiche Anzahl von A, B, C, D oder vielleicht doppelt so viele A wie B und doppelt so viele B wie C oder D.)
Wayne

Antworten:

19

Die Chance, diesen Zufall zu finden, scheint mir gering, während die Suche nach BABDCABCDACDBACD weniger zufällig erscheint.

Warum sollte das so sein? Wenn der Gesamtanteil der Buchstaben A ... D für jeden Buchstaben gleich 0,25 ist und jeder Buchstabe unabhängig vom anderen ist, sind beide Wörter genau gleich wahrscheinlich. Wenn sich die Verteilung der Buchstaben unterscheidet, können die Wahrscheinlichkeiten für die Erzeugung beider Wörter natürlich unterschiedlich sein.

Sie können versuchen, Wörter mit "geringer Komplexität" zu finden, beispielsweise Wörter mit einem besonders hohen Anteil eines Buchstabens (Sie könnten die Shannon-Informationen verwenden, wie in der anderen Antwort vorgeschlagen, und bei der Analyse biologischer Sequenzen gibt es viele andere Ansätze), aber es gibt sie ist kein Test für "Zufälligkeit", da der Begriff "Zufälligkeit" ohne weitere Annahmen oder Kenntnisse darüber, was Sie tatsächlich analysieren, keinen Sinn ergibt.

Januar
quelle
10
"beide Wörter sind genau gleich wahrscheinlich" wäre ein großartiger Ort für kühne Betonung.
Tashus
1
"Wenn der Gesamtanteil der Buchstaben A ... D für jeden Buchstaben gleich 0,25 ist ...". Nein, tatsächlich ist jedes mögliche Wort so wahrscheinlich wie jedes andere, unabhängig davon, wie viele Buchstaben im Wort enthalten sind.
DJClayworth
6
@DJClayworth Ich glaube, die Absicht dieser Zeile ist zu sagen, dass wir anstelle von A: .25 B: .25 C: .25 D.25 A: .5, B: .25, C: .125, D haben : .125 ist die Wahrscheinlichkeit, das Wort ABAA zu erhalten, im zweiten Fall weitaus wahrscheinlicher als im ersten, und CDBD ist im ersten Szenario genauso wahrscheinlich wie ABAA, im zweiten jedoch weniger wahrscheinlich als ABAA. Die Wahrscheinlichkeit eines bestimmten Wortes hängt also vom Verhältnis der Buchstaben zu anderen möglichen Anteilen ab.
Ale10ander
17

Sie können Shannon-Informationen ausprobieren: wobei , ist die Anzahl der Buchstaben im Wort und.

H=i=0nPilog2(Pi)
Pi=cincicn=|word|

Für das erste Wort hast du . Im zweiten Wort hast du .H=0.35H=2

Wenn die Entropie hoch ist, können Sie sie sich als zufälliger gegenüber einem anderen Wort mit niedrigerer Entropie vorstellen.

Edvrsoft
quelle
Dies ist eine gute Möglichkeit zum Erfassen einer Zeichenfolge Unberechenbarkeit zu gehen, und ich upvoted, aber Ihr Kriterium würde die gleichen Ergebnisse für beide geben bababbaabbund aaaabbbbbb. Der zugegebenermaßen sehr lockere Begriff der "Zufälligkeit", der von OP verwendet wird, würde den ersteren wahrscheinlich als "zufälliger" als den letzteren betrachten.
ymbirtt
8

Andere Antworten hier haben sich auf das allgemeine Auftreten verschiedener Buchstaben in der Sequenz konzentriert, was ein Aspekt der erwarteten "Zufälligkeit" sein kann. Ein weiterer interessanter Aspekt ist jedoch die offensichtliche Zufälligkeit in der Reihenfolge der Buchstaben in der Sequenz. Zumindest würde ich denken, dass "Zufälligkeit" die Austauschbarkeit des Buchstabenvektors beinhaltet, die mit einem "Lauftest" getestet werden kann. Der Lauftest zählt die Anzahl der "Läufe" in der Sequenz und vergleicht die Gesamtzahl der Läufe mit ihrer Nullverteilung unter der Nullhypothese der Austauschbarkeit für einen Vektor mit denselben Buchstaben. Die genaue Definition eines "Laufs" hängt vom jeweiligen Test ab (siehe z. B. eine ähnliche Antwort hier)), aber in diesem Fall besteht die natürliche Definition bei nominalen Kategorien darin, jede aufeinanderfolgende Sequenz, die nur aus einem Buchstaben besteht, als einen einzigen "Lauf" zu zählen.

Zum Beispiel Ihre Sequenz BABD-CABC-DACD-BACDsieht prima facie nicht zufällig zu mir (kein Brief erscheint mit sich, die für eine Folge dieses lange wahrscheinlich ungewöhnlich ist). Um dies formal zu testen, können wir einen Lauftest auf Austauschbarkeit durchführen. In dieser Sequenz haben wir Buchstaben (vier von jedem Buchstaben) und es gibt Läufe, die jeweils aus einer einzelnen Instanz eines Buchstabens bestehen. Die beobachtete Anzahl von Läufen kann unter der Hypothese der Austauschbarkeit mit ihrer Nullverteilung verglichen werden. Wir können dies über eine Simulation tun, die eine simulierte Nullverteilung und einen p-Wert für den Test ergibt. Das Ergebnis für diese Zeichenfolge ist in der folgenden Grafik dargestellt.n=16r=16

Geben Sie hier die Bildbeschreibung ein

Für diese Sequenz beträgt der p-Wert für den (unter der Nullhypothese der Austauschbarkeit) . Dies ist bei einem Signifikanzniveau von 10% signifikant, jedoch nicht bei einem Signifikanzniveau von 5%. Es gibt einige Hinweise auf eine nicht austauschbare Reihe (dh nicht zufällige Reihenfolge), aber die Hinweise sind nicht besonders stark. Bei einer länger beobachteten Zeichenfolge hätte der Lauftest eine größere Leistung, um eine austauschbare Zeichenfolge von einer nicht austauschbaren Zeichenfolge zu unterscheiden. (Wie Sie sehen können, kann mein anfängliches Anscheinsurteil, dass diese Zeichenfolge nicht zufällig ist, falsch sein - der p-Wert ist tatsächlich nicht so niedrig, wie ich es erwartet hatte.)p=0.0537

Schließlich ist zu beachten, dass bei diesem Test nur die Zufälligkeit der Reihenfolge der Buchstaben in der Zeichenfolge berücksichtigt wird. Dabei wird die Anzahl der Buchstaben jedes Typs als feste Eingabe verwendet. Dieser Test wird nicht Zufälligkeit im Sinne von nicht erkennen Austauschbarkeit der Buchstaben in der Zeichenkette, aber es wird nicht testen „Zufälligkeit“ im Sinne der Gesamtwahrscheinlichkeiten der verschiedenen Buchstaben. Wenn letzteres auch Teil der angegebenen Bedeutung von "Zufälligkeit" ist, könnte dieser Lauftest durch einen anderen Test ergänzt werden, der die Gesamtzahl der Buchstaben betrachtet und diese mit einer hypothetischen Nullverteilung vergleicht.


R-Code: Das obige Diagramm und der p-Wert wurden unter Verwendung des folgenden RCodes erzeugt:

#Define the character string vector (as factors)
x <- factor(c(2,1,2,4, 3,1,2,3, 4,1,3,4, 2,1,3,4), 
            labels = c('A', 'B', 'C', 'D'))

#Define a function to calculate the runs for an input vector
RUNS <- function(x) { n <- length(x);
                      R <- 1;
                      for (i in 2:n) { R <- R + (x[i] != x[i-1]) }
                      R; }

#Simulate the runs statistic for k permutations
k <- 10^5;
set.seed(12345);
RR <- rep(0, k);
for (i in 1:k) { x_perm <- sample(x, length(x), replace = FALSE);
                 RR[i] <- RUNS(x_perm); }

#Generate the frequency table for the simulated runs
FREQS <- as.data.frame(table(RR));

#Calculate the p-value of the runs test
R      <- RUNS(x);
R_FREQ <- FREQS$Freq[match(R, FREQS$RR)];
p      <- sum(FREQS$Freq*(FREQS$Freq <= R_FREQ))/k;

#Plot estimated distribution of runs with test
library(ggplot2);
ggplot(data = FREQS, aes(x = RR, y = Freq/k, fill = (Freq <= R_FREQ))) +
geom_bar(stat = 'identity') +
geom_vline(xintercept = match(R, FREQS$RR)) +
scale_fill_manual(values = c('Grey', 'Red')) +
theme(legend.position = 'none',
      plot.title      = element_text(hjust = 0.5, face = 'bold'),
      plot.subtitle   = element_text(hjust = 0.5),
      axis.title.y    = element_text(margin = margin(t = 0, r = 10, b = 0, l = 0))) +
labs(title    = 'Runs Test - Plot of Distribution of Runs under Exchangeability',
     subtitle = paste0('(Observed runs is black line, p-value = ', p, ')'),
     x = 'Runs', y = 'Estimated Probability'); 

Ich habe die Sequenz nur mit Bindestrichen aufgebrochen, um das Lesen zu erleichtern. Die Striche haben für die Analyse keine Bedeutung.

Ben - Monica wieder einsetzen
quelle
1
Interessant!
Ich
1

Angenommen, die Buchstabenfolge ist lang genug, können Sie Zufälligkeitstests auf die Daten anwenden .

Ein Satz solcher Tests wird als eingefleischte Tests bezeichnet :

Die eingefleischten Tests sind eine Reihe statistischer Tests zur Messung der Qualität eines Zufallszahlengenerators. Sie wurden von George Marsaglia über mehrere Jahre entwickelt und erstmals 1995 auf einer CD-ROM mit Zufallszahlen veröffentlicht.

Sie beinhalten eine möglicherweise willkürliche Reihe von Tests wie:

  • Geburtstagsabstände
  • Überlappende Permutationen
  • Reihen von Matrizen
  • Affentests
  • Zähle die 1s
  • Parkplatztest
  • Mindestabstandstest
  • Test mit zufälligen Kugeln
  • Der Quetschtest
  • Überlappender Summentest
  • Führt den Test aus
  • Der Craps-Test

Eine gute Folge von Zufallsdaten sollte diese Tests bestehen.

Das Bestehen dieser Tests reicht jedoch nicht aus, um zu beweisen, dass die Zahlen kein echtes Signal codieren. Sie könnten die Ausgabe einer hochwertigen Verschlüsselungsroutine sein.

Seltsames Denken
quelle