Runs-Test (Menü Analyse \ Zufallsanalyse)

Beim Aufruf dieses Menüeintrags öffnet sich der Dialog für den Runs-Test.

Mit dem klassischen Runs-Test untersucht man monoton steigend bzw. fallende Teilsequenzen einer Zahlenfolge. Unter einem "Run - up" der Länge k versteht man eine Teilfolge Xi; ... ; X(i + k – 1) mit X(i + r) <= X(i + r + 1) für alle r, 0 <= r <= k - 1. Analog werden "Run-downs" der Länge k definiert. Schlechte Generatoren erzeugen tendenziell zu lange Runs.

Der Runs Test vergleicht nun die beobachteten Häufigkeiten unterschiedlicher Run - Längen mit den erwarteten Häufigkeiten. Für die erwartete Häufigkeit eines Run - up' s der Länge k in einer Folge der Länge n gilt:

Ek = [(k ^ 2 + k + 1) * (n - k - 1)] / (k + 2)!

Da hintereinander folgende Runs nicht voneinander unabhängig sind (auf einen langen Run folgt mit größerer Wahrscheinlichkeit ein kurzer Run als ein langer Run und umgekehrt), darf der chi^2 -Test nicht ohne weiteres zum Vergleich der beobachteten Runs mit den erwarteten Häufigkeiten herangezogen werden. Knuth schlägt als einfache Problemlösung vor, jede Zahl, die unmittelbar auf das Ende eines Runs folgt, zu verwerfen. Dadurch erhält man voneinander unabhängige Runs, die mit dem chi^2 -Test mit k - 1 Freiheitsgraden auf ihre Verteilung überprüft werden können. Die Häufigkeitsverteilung wird in k Klassen eingeteilt, wobei die i-te Klasse,0 <= i <= k - 1, Runs mit der Länge i und die Klasse k - 1 Runs der Länge >= k enthält. Die Wahrscheinlichkeiten für Runs der Länge k ist gegeben durch

P(Run hat Länge k) = k / (k + 1)!

Im Falle der Überprüfung von binären Folgen vereinfacht sich die Betrachtung der Runs – up / Runs - Down auf die Länge der zu beobachtenden Lücken und Blöcke. Der Zweck des Runs-Tests - angewendet auf Binärfolgen - ist es, zu bestimmen, ob die Anzahl der binären Runs verschiedener Längen in der Folge s sich wie bei einer echten Zufallsfolge verhält.

Die in einer n-Bit Zufallsfolge erwartete Anzahl an Lücken (bzw. Blöcken) der Länge i ist gegeben durch

Ei = (n - i + 3) / 2 ^ (i + 2)

Sei k gleich der größten Zahl i, für die gilt E5, und seien Bi; Gi die Anzahl der Blöcke und Lücken der Länge i in s für alle i, 1 <= i <= k. Die verwendete Teststatistik ist gegeben durch

X4 =sum[i = 1; i = k] (Bi – Ei) ^ 2 / Ei + sum[i = 1; i = k] (Gi – Ei) ^ 2 / Ei

wobei X4 annähernd einer chi^2-Verteilung mit 2k - 2 Freiheitsgraden gehorcht.

Ein Runs-Test-Beispiel:

Im folgenden werden beispielhaft an der kurzen Binärfolge

s =
00010111 01101101 01111101 11110011 00101111 
00001111 10100100 11001111 11000011 11010001
11010001 00101110 11010100 11000011 01010001
11010110 00110010 10001111 00000111 01000111

mit der Länge n = 160 (20 Byte) klassischen Runs-Test durchgeführt. Das Signifikanzniveau wird mit alpha = 0.05 festgelegt.

Durch absolute(s) = 160 gilt in unserem konkreten Runs-Test für s: k = 3. Die erwartete Anzahl von Runs der Länge i = 1, 2, 3 in einer 160 - Bit Folge beträgt Ei = (160 – i + 3) / 2 ^ (i + 2), 1 <= i <= 3.

E1 = 20.25
E2 = 10.0625
E3 = 5

In der Sequenz s gibt es die folgende Anzahl von Blöcke Bi bzw. Lücken Gi der Längen i = 1, 2, 3:

B1 = 17
G1 = 20
B2 = 9
G2 = 8
B3 = 6
G3 = 7

Bestimmen wir nun die Prüfgröße für den Runs-Test:

X4= [(17 – 20.25) ^ 2 / 20.25] + [(9 – 10.0625) ^ 2 / 10.0625] + [(6 – 5) ^ 2 / 5] +
  [(20 – 20.25) ^ 2 / 20.25] + [(8 – 10.0625) ^ 2 / 10.0625] + [(7 – 5) ^ 2 / 5]
= 2.0596

Für ein Signifikanzniveau von alpha = 0.05 gibt bei 2 * 3 - 2 = 4 Freiheitsgraden einen kritischen Bereich über 9.488 an. Mit X4 = 2.0596 <= 9.488 besteht die Folge s den Runs-Test.

Literatur:

Christian Schiestl, Pseudozufallszahlen in der Kryptographie, Klagenfurt, 1999.