Runtest zurück
Quellen:
Eine Zufallssequenz oder Zufallsfolge entsteht durch die wiederholte Anwendung eines statistischen Experiments. Eine Zufallssequenz ist im Allgemeinen eine Abfolge von Realisationen einer Zufallsvariablen. Der Begriff wird meistens im Sinne einer Abfolge von zufällig aus einem bestimmten Alphabet oder Zahlenvorrat ausgewählten Zeichen gebraucht.
Die einfachste Zufallssequenz gewinnt man durch einen wiederholten Münzwurf, wenn man einer Seite der Münze die 0 und der anderen die 1 zuordnet. Man kann andere Zufallssequenzen so in eine einfache 0-1-Sequenz umcodieren (dichotomisieren), ohne dass der Zufallscharakter verloren geht.
Beispiel: 101101101010100111001011001110000001111001010000111101010001001101111011000010001010100011101110010101110111111100000100110100001101110111101010110000010001110110001000000100111110000011111010010001101111001010100000101101000011000110100011001111011111000110111001001100000011111001000000110000100000011010101000001100010110000111001111001000011011111111001001010100111110010001001000010010010000100010100111001111011000001010011111110010111110111011000111011010110000011101100111101011001110
Diese Folge wurde durch wiederholten Münzwurf gewonnen. Auffällig ist, wie oft längere zusammenhängende Sequenzen von 0 oder 1 zu finden sind.
Eine Zufallssequenz ist durch eine verschwindende serielle Korrelation oder auch Autokorrelation gekennzeichnet, d.h. der Korrelationskoeffizient zwischen aufeinander folgenden Werten in der Sequenz ist nicht signifikant von Null verschieden.
Viele natürlich vorkommenden zeit- bzw. ortsdiskreten Signale (z.B. DNA, siehe auch DNA-Sequenzanalyse) werden statistisch analysiert, indem man zunächst die Nullhypothese eines zugrunde liegenden Zufallsprozesses postuliert. Kann man diese Hypothese widerlegen, liegen also Korrelationen in der Sequenz vor, weisen diese unter Umständen auf in der Sequenz verborgene Nutzinformation hin. Speziell bei dichtomen Folgen kann man die Sequenzen mit Hilfe des Run-Tests auf Zufälligkeit überprüfen, wobei mit "Run" eine Folge gleicher Ausprägungen in der Sequenz bezeichnet wird. Der Test führt zur Ablehnung, wenn zu wenig, aber auch zu viel Runs in einer Sequenz sind.
MEDIAN:
Der Median oder Zentralwert bezeichnet eine Grenze zwischen zwei gleich großen Hälften. Er kann mit dem Mittelwert zusammenfallen, kann aber auch unterschiedlich sein.
Median einer Stichprobe
Bei einer sortierten Zahl von Messwerten ist der Median der Wert der in der Mitte liegt. (Bei einer geraden Anzahl das arithmetische Mittel der beiden mittleren Werte)
Der Median einer geordneten Stichprobe mit n Messwerten berechnet sich wie folgt:
Für eine ungerade Anzahl n:
xmedian = x(n+1)/2
Beispiel 1,2,3,4,5 ==> 3 ist der Median . Er steht an Stelle (5+1)/2 = 3ter Stelle
Beispiel Ungerade Zahl n von Meßwerten
1,2,2,3,4,4,5
>> 3 ist der Median . Er steht an Stelle (7+1)/2 = 4. Stelle
Für eine gerade Anzahl n:
xmedian = ½ ( xn/2 + xn/2+1)
Beispiel 1,2,3,4,5,6 ==> 3,5 ist der Median . Er berechnet sich aus ½ ( 3 + 4)
Im Gegensatz zum arithmetischen Mittelwert, auch Durchschnitt genannt, verändert sich der Median durch einzelne Extremwerte kaum. So ist der Median der Werte 1,2,3,4,5 und 1,2,3,4,100 jeweils 3; Der Mittelwert der ersten Werte ist ebenfalls 3, im zweiten Fall 22.
RUNTEST
Der Run- oder Runs-Test (auch Wald-Wolfowitz-Test) ist ein nichtparametrischer Test auf Stationarität bzw. Nicht-Korrelation in einer Zeitreihe oder anderen Sequenz. Die abzulehnende Nullhypothese ist hier, dass aufeinanderfolgende Werte unkorreliert sind. Ein run oder "Lauf" ist definiert als eine Folge von gleichen Symbolen in einer Symbolsequenz mit endlichem Alphabet.
Aus einer Symbolsequenz muss zunächst eine numerische Reihe erzeugt werden
Zunächst wird der Median der Reihe berechnet und von allen Werten abgezogen. In der resultierenden Reihe werden negative Zahlen durch ein '-' und positive durch ein '+' ersetzt.
Für Stichprobenumfänge n1,n2 > 10 (mit n1,n2 gleich der Anzahl der "plus" und der "minus") ist die Wahrscheinlichkeitsverteilung der runs ungefähr normal mit Mittelwert
UM = 2 * n1*n2 /(n1+n2) + 1
und Varianz
varianz = 2*n1*n2*(2*n1*n2 – n1 – n2) / (n1 + n2) / (n1 + n2) / (n1 + n2 – 1)
Die Testgröße z berechnet sich nun nach:
z = ( U – UM ) / Wurzel aus Varianz
wobei U die gemessene Anzahl der "runs" von '-' und '+' in der Reihe ist. z ist ungefähr standardnormalverteilt.
Der Run-Test ist nicht so mächtig wie der Kolmogorov-Test oder der Chi-Quadrat Test, kann aber mit letzterem kombiniert werden, da beide asymptotisch unabhängig voneinander sind.
Beispiel
13 3 14 14 1 14 3 8 14 17 9 14 13 2 16 1 3 12 13 14
Median 13
0 -10 1 1 -12 1 -10 -5 1 4 -4 1 0 -11 3 -12 -10 -1 0 1
+ - + + - + - - + + - + + - + - - - + +
1 2 3 4 5 6 7 8 9 10 11 12 13
U ist die Zahl der Runs
U = 13 runs bzw U: 13
n1 = Pluszeichen '+': 11
n2 = Minuszeichen '-': 9
= (2*11*9)/(11+9) + 1 = 10,9
= ... = 4,6
σU = 2,1
z = (13 - 10,9) / 2,1 = 1.0
Entscheidung: Die Hypothese wird nicht abgelehnt. Die Elemente der Stichprobe sind vermutlich zufällig entnommen worden.
Siehe auch: http://www.itl.nist.gov/div898/handbook/eda/section3/eda35d.htm
http://www.wu-wien.ac.at/usr/stat2/melichar/spsspu1/spssk3-9.htm
Bradley, (1968). Distribution-Free Statistical Tests, Chapter 12.
Run-Test
Zunächst wird der Median berechnet
Wir klassifizieren als + die Zahlen yi, die größ er sind als die Voraussage f(xi) der Hypothese und als - die anderen. Die entsprechenden Anzahlen seien N+ und N- mit
N = Nplus + Nminus
(13)
Bei großem N und gleichen s für alle Messungen erwarten wir N+ » N- » N/2. Wir definieren ferner als `Run' eine maximale Sequenz von Datenpunkten die zur gleichen Klasse gehören.
Die Näherungen gelten jeweils für groß e N. Nur dann sind die Fehler gauß isch. Im Fall N = 12 (Abb. 9) (Vorsicht: keine groß e Zahl!) erwartet man
NR = 7 sR = 1.65
Nur drei Runs sind also selten!
Beispiel Datensatz 1. Es gibt 5 Runs, das ist ok.
Beispiel: Datensatz 1:
yi = -0.74, -1.87, 0.25, 0.50, 0.67, 1.38, -0.10, -0.52, 1.24, 1.99, 0.24,-1.13
Median 0.245
1: Minus, da -0.74 < 0.245
2.Minus
3.Plus da 0.25 > 0.245
4.Plus
5.Plus
6.Plus
7.Minus
8.Minus , da -0.52 < 0.245
9.Plus,
10.Plus
11.Minus , da 0,24 < 0,245
12.Minus
--------------------------------------------
>> U = Zahl der Runs 5
UM = 2 * n1*n2 /(n1+n2) + 1
n1 = 3 zahl der Minusruns
n2 = 2 Zahl der Plusruns
UM = 2 * 3 * 2 / 5 + 1 = 12/5 + 1 = 2,4 + 1 = 3,4
varianz = 2*n1*n2*(2*n1*n2 – n1 – n2) / (n1 + n2) / (n1 + n2) / (n1 + n2 – 1)
varianz = 2*3*2*(2*3*2 – 3 – 2) / (3 + 2) / (3 + 2) / (3 + 2 – 1)
= 12*( 12-3-2) / 5 / 5 / 4
= 12 * 7 / 100 = 84 / 100 = 0,84
z = (U – UM) / varianz
z = (5 – 3,4) / 0,84 = 1,6 / 0,84 = 1.904761904761905
Beispiel Datensatz 2. Es gibt nur einen Run, das ist ganz sicher nicht akzeptabel, die Hypothese m = 0 ist falsch.
Beispiel: Betrachten wir jetzt den Datensatz 2:
yi = 0.74, 1.87, 0.25, 0.50, 0.67, 1.38, 0.10, 0.52, 1.24, 1.99, 0.24,1.13
Beispiel Datensatz 3.
Beispiel: Schließlich betrachten wir Datensatz 3:
yi =
-1.87,-1.13, -0.74, -0.52, -0.10, 0.24,0.25, 0.50, 0.67, 1.24, 1.38, 1.99
Medianwert 0.245
Es gibt zwei Runs, das ist auch nicht akzeptabel, denn die Abweichung von 7 beträgt mehr als drei Standardabweichungen. Die Wahrscheinlichkeit für eine solche Konstellation ist für die betrachtete Hypothese (Gauß , m = 0, ...) also deutlich kleiner als 1%.
Der Run-Test `funktioniert' also in allen drei Beispielen!
Auch der Run-Test kann nur angewandt werden, wenn keine Parameter gefittet wurden.
Runs Test for Detecting Non-randomness
http://www.itl.nist.gov/div898/handbook/eda/section3/eda35d.htm
Background and Data
Generation
This data set was collected by H. S. Lew of NIST in 1969 to measure steel-concrete beam deflections. The response variable is the deflection of a beam from the center point.
The motivation for studying this data set is to show how the underlying assumptions are affected by periodic data.
Resulting Data
The following are the data used for this case study.
-213
-564
-35
-15
141
115
-420
-360
203
-338
-431
194
-220
-513
154
-125
-559
92
-21
-579
-52
99
-543
-175
162
-457
-346
204
-300
-474
164
-107
-572
-8
83
-541
-224
180
-420
-374
201
-236
-531
83
27
-564
-112
131
-507
-254
199
-311
-495
143
-46
-579
-90
136
-472
-338
202
-287
-477
169
-124
-568
17
48
-568
-135
162
-430
-422
172
-74
-577
-13
92
-534
-243
194
-355
-465
156
-81
-578
-64
139
-449
-384
193
-198
-538
110
-44
-577
-6
66
-552
-164
161
-460
-344
205
-281
-504
134
-28
-576
-118
156
-437
-381
200
-220
-540
83
11
-568
-160
172
-414
-408
188
-125
-572
-32
139
-492
-321
205
-262
-504
142
-83
-574
0
48
-571
-106
137
-501
-266
190
-391
-406
194
-186
-553
83
-13
-577
-49
103
-515
-280
201
300
-506
131
-45
-578
-80
138
-462
-361
201
-211
-554
32
74
-533
-235
187
-372
-442
182
-147
-566
25
68
-535
-244
194
-351
-463
174
-125
-570
15
72
-550
-190
172
-424
-385
198
-218
-536
96
Purpose:
Detect Non-Randomness
The runs test ( Bradley, 1968) can be used to decide if a data set is from a random process.
A run is defined as a series of increasing values or a series of decreasing values. The number of increasing, or decreasing, values is the length of the run. In a random data set, the probability that the (I+1)th value is larger or smaller than the Ith value follows a binomial distribution, which forms the basis of the runs test.
Typical Analysis and Test Statistics
The first step in the runs test is to compute the sequential differences (Yi - Yi-1). Positive values indicate an increasing value and negative values indicate a decreasing value. A runs test should include information such as the output shown below from Dataplot for the LEW.DAT data set. The output shows a table of:
runs of length exactly I for I = 1, 2, ..., 10
number of runs of length I
expected number of runs of length I
standard deviation of the number of runs of length I
a z-score where the z-score is defined to be
zi = (yi – ymittel ) / s
where ymittel is the sample mean and
s is the sample standard deviation.
The z-score column is compared to a standard normal table. That is, at the 5% significance level, a z-score with an absolute value greater than 1.96 indicates non-randomness.
There are several alternative formulations of the runs test in the literature. For example, a series of coin tosses would record a series of heads and tails. A run of length r is r consecutive heads or r consecutive tails. To use the Dataplot RUNS command, you could code a sequence of the N = 10 coin tosses HHHHTTHTHH as
1 2 3 4 3 2 3 2 3 4
that is, a heads is coded as an increasing value and a tails is coded as a decreasing value.
Another alternative is to code values above the median as positive and values below the median as negative. There are other formulations as well. All of them can be converted to the Dataplot formulation. Just remember that it ultimately reduces to 2 choices. To use the Dataplot runs test, simply code one choice as an increasing value and the other as a decreasing value as in the heads/tails example above. If you are using other statistical software, you need to check the conventions used by that program.
Sample Output
Dataplot generated the following runs test output using the LEW.DAT data set:
RUNS UP
STATISTIC = NUMBER OF RUNS UP
OF LENGTH EXACTLY I
I STAT EXP(STAT) SD(STAT) Z
1 18.0 41.7083 6.4900 -3.65
2 40.0 18.2167 3.3444 6.51
3 2.0 5.2125 2.0355 -1.58
4 0.0 1.1302 1.0286 -1.10
5 0.0 0.1986 0.4424 -0.45
6 0.0 0.0294 0.1714 -0.17
7 0.0 0.0038 0.0615 -0.06
8 0.0 0.0004 0.0207 -0.02
9 0.0 0.0000 0.0066 -0.01
10 0.0 0.0000 0.0020 0.00
STATISTIC = NUMBER OF RUNS UP
OF LENGTH I OR MORE
I STAT EXP(STAT) SD(STAT) Z
1 60.0 66.5000 4.1972 -1.55
2 42.0 24.7917 2.8083 6.13
3 2.0 6.5750 2.1639 -2.11
4 0.0 1.3625 1.1186 -1.22
5 0.0 0.2323 0.4777 -0.49
6 0.0 0.0337 0.1833 -0.18
7 0.0 0.0043 0.0652 -0.07
8 0.0 0.0005 0.0218 -0.02
9 0.0 0.0000 0.0069 -0.01
10 0.0 0.0000 0.0021 0.00
RUNS DOWN
STATISTIC = NUMBER OF RUNS DOWN
OF LENGTH EXACTLY I
I STAT EXP(STAT) SD(STAT) Z
1 25.0 41.7083 6.4900 -2.57
2 35.0 18.2167 3.3444 5.02
3 0.0 5.2125 2.0355 -2.56
4 0.0 1.1302 1.0286 -1.10
5 0.0 0.1986 0.4424 -0.45
6 0.0 0.0294 0.1714 -0.17
7 0.0 0.0038 0.0615 -0.06
8 0.0 0.0004 0.0207 -0.02
9 0.0 0.0000 0.0066 -0.01
10 0.0 0.0000 0.0020 0.00
STATISTIC = NUMBER OF RUNS DOWN
OF LENGTH I OR MORE
I STAT EXP(STAT) SD(STAT) Z
1 60.0 66.5000 4.1972 -1.55
2 35.0 24.7917 2.8083 3.63
3 0.0 6.5750 2.1639 -3.04
4 0.0 1.3625 1.1186 -1.22
5 0.0 0.2323 0.4777 -0.49
6 0.0 0.0337 0.1833 -0.18
7 0.0 0.0043 0.0652 -0.07
8 0.0 0.0005 0.0218 -0.02
9 0.0 0.0000 0.0069 -0.01
10 0.0 0.0000 0.0021 0.00
RUNS TOTAL = RUNS UP + RUNS DOWN
STATISTIC = NUMBER OF RUNS TOTAL
OF LENGTH EXACTLY I
I STAT EXP(STAT) SD(STAT) Z
1 43.0 83.4167 9.1783 -4.40
2 75.0 36.4333 4.7298 8.15
3 2.0 10.4250 2.8786 -2.93
4 0.0 2.2603 1.4547 -1.55
5 0.0 0.3973 0.6257 -0.63
6 0.0 0.0589 0.2424 -0.24
7 0.0 0.0076 0.0869 -0.09
8 0.0 0.0009 0.0293 -0.03
9 0.0 0.0001 0.0093 -0.01
10 0.0 0.0000 0.0028 0.00
STATISTIC = NUMBER OF RUNS TOTAL
OF LENGTH I OR MORE
I STAT EXP(STAT) SD(STAT) Z
1 120.0 133.0000 5.9358 -2.19
2 77.0 49.5833 3.9716 6.90
3 2.0 13.1500 3.0602 -3.64
4 0.0 2.7250 1.5820 -1.72
5 0.0 0.4647 0.6756 -0.69
6 0.0 0.0674 0.2592 -0.26
7 0.0 0.0085 0.0923 -0.09
8 0.0 0.0010 0.0309 -0.03
9 0.0 0.0001 0.0098 -0.01
10 0.0 0.0000 0.0030 0.00
LENGTH OF THE LONGEST RUN UP = 3
LENGTH OF THE LONGEST RUN DOWN = 2
LENGTH OF THE LONGEST RUN UP OR DOWN = 3
NUMBER OF POSITIVE DIFFERENCES = 104
NUMBER OF NEGATIVE DIFFERENCES = 95
NUMBER OF ZERO DIFFERENCES = 0
Interpretation of Sample Output
Scanning the last column labeled "Z", we note that most of the z-scores for run lengths 1, 2, and 3 have an absolute value greater than 1.96. This is strong evidence that these data are in fact not random.
Output from other statistical software may look somewhat different from the above output.
Question
The runs test can be used to answer the following question:
Were these sample data generated from a random process?
Importance
Randomness is one of the key assumptions in determining if a univariate statistical process is in control. If the assumptions of constant location and scale, randomness, and fixed distribution are reasonable, then the univariate process can be modeled as:
yi = Ao + Ei
where Ei is an error term.
If the randomness assumption is not valid, then a different model needs to be used. This will typically be either a times series model or a non-linear model (with time as the independent variable).
Related Techniques
Autocorrelation
Run Sequence Plot
Lag Plot
Case Study
Heat flow meter data
Software
Most general purpose statistical software programs, including Dataplot, support a runs test.
----------------------------------------------------------------------------------------------------------------------
Der Run – Test
http://www-user.tu-chemnitz.de/~jflo/Simulation/ZZ/runtest.html
Die von einem beliebigen Zufallszahlen-Generator erzeugte Folge von Elementen x[i], i=1,2,... wird gemäß folgendem Algorithmus in aufsteigend (oder absteigend) geordnete Teilmengen R[k], k=1,2,... -die sogenannten 'RUNS'- zerlegt:
Initialisierung:
i := 1 {Index der Zahlenfolge}
k := 1 {Index der Teilmenge, des Runs}
H[r] := 0 für r=1,2,...,25
{Feld zur Erfassung des Histogrammes der Run-Längen}
Erzeuge x[i] und ordne x[i] dem Run R[k] als 1.Element zu
Inkrementiere i und erzeuge das nächste x[i]
Gilt x[i] > x[i-1], dann wird auch x[i] dem Run R[k] zugeordnet;
anschließend Fortsetzung bei Schritt 3
Gilt x[i] <= x[i-1] , dann wird x[i] keinem Run zugeordnet
Ermittle die Anzahl r der Elemente der Menge R[k] (die "Run-Länge")
und inkrementiere H[r]
Inkrementiere i, inkrementiere k und setze fort mit Schritt 2
Beispiel (zweistellige Zufallszahlen):
29 88 65 87 08 13 50 63 04 23 25 47 57 91 13 52 62 24 19 94 01 ...
[---] X [] X [------] X [------------] X [---] X [---] X ...
R[1] = {29,88} --> r = 2
R[2] = {87} --> r = 1
R[3] = {13,50,63} --> r = 3
R[4] = {23,25,47,57,91} --> r = 5
R[5] = {52,62} --> r = 2
R[6] = {19,94} --> r = 2
Wäre {x[i]} eine Folge "echter" Zufallszahlen (also eine Folge unabhängiger, im Intervall (0,1) gleichverteilter Realisierungen), dann würde die Run-Länge r exakt mit der Wahrscheinlichkeit
p[r] = r / ( r + 1 )!
vorkommen, d.h. im Mittel werden p[r] · 100% der beobachteten Runs genau r Elemente beinhalten.
Daß Runs der Länge 1 mit Wkt. œ auftreten müssen, kann leicht nachgewiesen werden: Die Chancen für ein absteigendes Paar (ergibt r=1) und für ein aufsteigendes Paar (ergibt r>1) sind bei "echten" Zufallszahlen offensichtlich gleich groß !
Lange Runs sind sehr selten; unter 40 000 Runs ist im Mittel nur einer mit r>=8 Elementen. Runs mit mehr als 20 Elementen treten praktisch nie auf!
Von einem Zufallszahlengenerator wird nun gefordert, daß die gelieferte Zahlenfolge bezüglich der Run-Längen das gleiche Verteilungsgesetz wie bei echten Zufallszahlen aufweist.
Der Vergleich der theoretischen Häufigkeiten h[r] := N · p[r] mit den "beobachteten" Häufigkeiten H[r] des Auftretens der einzelnen Run-Längen erfolgt mittels Chiquadrat-Anpassungstest. Hierzu sollten die relativ selten beobachteten "langen" Runs, z.Bsp. alle Runs mit r >= 8 , zu einer Klasse zusammengefaßt werden (Es sollten mindestens 5 Beobachtungen je Klasse vorliegen).
Anmerkungen:
Schritt 5 ist erforderlich, da dasjenige x[i], welches das Ende einer aufsteigenden Folge signalisiert, kein 'gerechter' Anfangswert für den nächsten Run wäre.
Man kann sogar ohne die theoretischen Werte p[r] auskommen, wenn man die Folge x[i] zweimal analysiert: nach aufsteigenden Runs R_up[k] und absteigenden Runs R_down[k]! Dann Test auf Gleichheit beider Verteilungsgesetze.
(Siehe auch Demo-Programm 'runtest.pas' ).