Diehard-Tests – Wikipedia

Das eingefleischte 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.^[1]

Testübersicht[edit]

• Geburtstagsabstände: Wählen Sie zufällige Punkte in einem großen Intervall. Die Abstände zwischen den Punkten sollten asymptotisch exponentiell verteilt sein.^[2] Der Name basiert auf dem Geburtstagsparadoxon.
• Überlappende Permutationen: Analysieren Sie Sequenzen von fünf aufeinanderfolgenden Zufallszahlen. Die 120 möglichen Ordnungen sollten mit statistisch gleicher Wahrscheinlichkeit erfolgen.
• Reihen von Matrizen: Wählen Sie eine Anzahl von Bits aus einer Anzahl von Zufallszahlen aus, um eine Matrix über {0,1} zu bilden, und bestimmen Sie dann den Rang der Matrix. Zähle die Reihen.
• Affentests: Behandle Sequenzen einer bestimmten Anzahl von Bits als “Wörter”. Zählen Sie die überlappenden Wörter in einem Stream. Die Anzahl der “Wörter”, die nicht erscheinen, sollte einer bekannten Verteilung folgen. Der Name basiert auf dem unendlichen Affensatz.
• Zähle die 1s: Zählen Sie die 1 Bits in jedem der aufeinanderfolgenden oder ausgewählten Bytes. Konvertieren Sie die Anzahl in “Buchstaben” und zählen Sie das Vorkommen von “Wörtern” mit fünf Buchstaben.
• Parkplatztest: Platziere zufällig Einheitskreise in einem 100 × 100-Quadrat. Ein Kreis wird erfolgreich geparkt, wenn er einen vorhandenen erfolgreich geparkten Kreis nicht überlappt. Nach 12.000 Versuchen sollte die Anzahl der erfolgreich geparkten Kreise einer bestimmten Normalverteilung folgen.
• Mindestabstandstest: Platzieren Sie zufällig 8000 Punkte auf einem Quadrat von 10000 × 10000 und ermitteln Sie dann den Mindestabstand zwischen den Paaren. Das Quadrat dieser Entfernung sollte mit einem bestimmten Mittelwert exponentiell verteilt sein.
• Test mit zufälligen Kugeln: Wählen Sie nach dem Zufallsprinzip 4000 Punkte in einem Würfel der Kante 1000 aus. Zentrieren Sie auf jedem Punkt eine Kugel, deren Radius der Mindestabstand zu einem anderen Punkt ist. Das Volumen der kleinsten Kugel sollte mit einem bestimmten Mittelwert exponentiell verteilt sein.
• Der Quetschtest: Multiplizieren Sie 2³¹ mit zufälligen Floats auf (0,1), bis Sie 1 erreichen. Wiederholen Sie dies 100000 Mal. Die Anzahl der Schwimmer, die benötigt werden, um 1 zu erreichen, sollte einer bestimmten Verteilung folgen.
• Überlappender Summentest: Generiere eine lange Folge von zufälligen Floats auf (0,1). Fügen Sie Sequenzen von 100 aufeinanderfolgenden Floats hinzu. Die Summen sollten normal mit charakteristischem Mittelwert und Varianz verteilt sein.
• Führt den Test aus: Generiere eine lange Folge von zufälligen Floats auf (0,1). Zählen Sie aufsteigende und absteigende Läufe. Die Zählungen sollten einer bestimmten Verteilung folgen.
• Der Craps-Test: Spielen Sie 200000 Craps-Spiele und zählen Sie die Gewinne und die Anzahl der Würfe pro Spiel. Jede Zählung sollte einer bestimmten Verteilung folgen.

Testbeschreibungen[edit]

• Der Geburtstagsabstandstest: Wählen m Geburtstage in einem Jahr von n Tage. Listen Sie die Abstände zwischen den Geburtstagen auf. Wenn j ist die Anzahl der Werte, die dann in dieser Liste mehr als einmal vorkommen j ist asymptotisch Poisson mit Mittelwert verteilt m³ ÷ (4n). Erfahrungsgemäß muss n beispielsweise ziemlich groß sein n ≥ 2¹⁸zum Vergleichen der Ergebnisse mit der Poisson-Verteilung mit diesem Mittelwert. Dieser Test verwendet n = 2²⁴ und m = 2⁹, so dass die zugrunde liegende Verteilung für j wird als Poisson mit λ = 2 angenommen²⁷ ÷ 2²⁶ = 2. Eine Stichprobe von 500 js wird genommen und ein Chi-Quadrat-Anpassungstest liefert a p Wert. Der erste Test verwendet die Bits 1–24 (von links gezählt) aus Ganzzahlen in der angegebenen Datei. Dann wird die Datei geschlossen und erneut geöffnet. Als nächstes werden die Bits 2–25 verwendet, um Geburtstage anzugeben, dann 3–26 und so weiter bis zu den Bits 9–32. Jeder Satz von Bits liefert a p-Wert und die neun p-Werte liefern ein Beispiel für einen KSTEST.
• Der überlappende 5-Permutationstest: Dies ist der OPERM5-Test. Es wird eine Folge von einer Million 32-Bit-Zufallszahlen betrachtet. Jeder Satz von fünf aufeinanderfolgenden ganzen Zahlen kann sich für die 5 in einem von 120 Zuständen befinden! mögliche Reihenfolge von fünf Zahlen. Somit liefern die Zahlen 5, 6, 7, … jeweils einen Zustand. Da viele tausend Zustandsübergänge beobachtet werden, wird die Anzahl der Vorkommen jedes Zustands kumulativ gezählt. Dann ergibt die quadratische Form in der schwachen Inversen der 120 × 120-Kovarianzmatrix einen Test, der dem Likelihood-Ratio-Test entspricht, dass die 120 Zellzahlen aus der angegebenen (asymptotisch) Normalverteilung mit der angegebenen 120 × 120-Kovarianzmatrix (mit Rang 99) stammen ). Diese Version verwendet zweimal 1000000 Ganzzahlen. Dieser Test kann ungelöste Fehler aufweisen, die zu konstant schlechten p-Werten führen.^[3]
• Der binäre Rangtest für 31 × 31 Matrizen: Die am weitesten links stehenden 31 Bits von 31 zufälligen Ganzzahlen aus der Testsequenz werden verwendet, um eine 31 × 31-Binärmatrix über dem Feld {0,1} zu bilden. Der Rang wird bestimmt. Dieser Rang kann zwischen 0 und 31 liegen, aber Ränge <28 sind selten, und ihre Zählungen werden mit denen für Rang 28 zusammengefasst. Für 40000 solcher Zufallsmatrizen werden Ränge gefunden, und für die Ränge 31, 30 wird ein Chi-Quadrat-Test durchgeführt 29 und ≤ 28.
• Der binäre Rangtest für 32 × 32 Matrizen: Eine zufällige 32 × 32-Binärmatrix wird gebildet, wobei jede Zeile eine zufällige 32-Bit-Ganzzahl ist. Der Rang wird bestimmt. Dieser Rang kann zwischen 0 und 32 liegen, Ränge unter 29 sind selten und ihre Zählungen werden mit denen für Rang 29 zusammengefasst. Für 40000 solcher Zufallsmatrizen werden Ränge gefunden, und für die Ränge 32, 31, wird ein Chi-Quadrat-Test durchgeführt. 30 und ≤ 29.
• Der binäre Rangtest für 6 × 8-Matrizen: Aus jeder der sechs zufälligen 32-Bit-Ganzzahlen des zu testenden Generators wird ein bestimmtes Byte ausgewählt, und die resultierenden sechs Bytes bilden eine 6 × 8-Binärmatrix, deren Rang bestimmt wird. Dieser Rang kann zwischen 0 und 6 liegen, aber die Ränge 0, 1, 2, 3 sind selten. Ihre Zählungen werden mit denen für Rang 4 zusammengefasst. Für 100000 Zufallsmatrizen werden Ränge gefunden, und ein Chi-Quadrat-Test wird für Zählungen für die Ränge 6, 5 und ≤ 4 durchgeführt.
• Der Bitstream-Test: Die zu testende Datei wird als Bitstrom angezeigt. Nenne sie b₁b₂,…. Stellen Sie sich ein Alphabet mit zwei “Buchstaben”, 0 und 1, vor und stellen Sie sich den Bitstrom als eine Folge von überlappenden “Wörtern” mit 20 Buchstaben vor. Somit ist das erste Wort b₁b₂… B.₂₀, der zweite ist b₂b₃… B.₂₁, und so weiter. Der Bitstream-Test zählt die Anzahl der fehlenden Wörter mit 20 Buchstaben (20 Bit) in einer Zeichenfolge von 2²¹ überlappende Wörter mit 20 Buchstaben. Da sind 2²⁰ mögliche Wörter mit 20 Buchstaben. Für eine wirklich zufällige Folge von 2²¹ + 19 Bit, die Anzahl der fehlenden Wörter j sollte (sehr nahe an) normalverteilt sein mit Mittelwert 141.909 und Sigma 428. Also (j-141909) ÷ 428 sollte eine normale Standardvariable sein (z Punktzahl), die zu einer Uniform führt [0,1) p value. The test is repeated twenty times.
• The tests OPSO, OQSO and DNA: OPSO means overlapping-pairs-sparse-occupancy. The OPSO test considers 2-letter words from an alphabet of 1024 letters. Each letter is determined by a specified ten bits from a 32-bit integer in the sequence to be tested. OPSO generates 2²¹ (overlapping) 2-letter words (from 2²¹ + 1 “keystrokes”) and counts the number of missing words – that is 2-letter words which do not appear in the entire sequence. That count should be very close to normally distributed with mean 141909, sigma 290. Thus (missingwrds-141909) ÷ 290 should be a standard normal variable. The OPSO test takes 32 bits at a time from the test file and uses a designated set of ten consecutive bits. It then restarts the file for the next designated 10 bits, and so on. OQSO means overlapping-quadruples-sparse-occupancy. The test OQSO is similar, except that it considers 4-letter words from an alphabet of 32 letters, each letter determined by a designated string of 5 consecutive bits from the test file, elements of which are assumed 32-bit random integers. The mean number of missing words in a sequence of 2²¹ four-letter words, (2²¹ + 3 “keystrokes”), is again 141909, with sigma = 295. The mean is based on theory; sigma comes from extensive simulation. The DNA test considers an alphabet of 4 letters C,G,A,T, determined by two designated bits in the sequence of random integers being tested. It considers 10-letter words, so that as in OPSO and OQSO, there are 2²⁸ possible words, and the mean number of missing words from a string of 2²¹ (overlapping) 10-letter words (2²¹ + 9 “keystrokes”) is 141909. The standard deviation sigma = 339 was determined as for OQSO by simulation. (Sigma for OPSO, 290, is the true value (to three places), not determined by simulation.
• The count-the-1’s test on a stream of bytes: Consider the file under test as a stream of bytes (four per 32-bit integer). Each byte can contain from none to eight 1s, with probabilities 1, 8, 28, 56, 70, 56, 28, 8, 1 over 256. Now let the stream of bytes provide a string of overlapping 5-letter words, each “letter” taking values A, B, C, D, E. The letters are determined by the number of 1s in a byte 0, 1, or 2 yield A, 3 yields B, 4 yields C, 5 yields D and 6, 7 or 8 yield E. Thus we have a monkey at a typewriter hitting five keys with various probabilities (37, 56, 70, 56, 37 over 256). There are 5⁵ possible 5-letter words, and from a string of 256000 (overlapping) 5-letter words, counts are made on the frequencies for each word. The quadratic form in the weak inverse of the covariance matrix of the cell counts provides a chisquare test Q5–Q4, the difference of the naive Pearson sums of (OBS-EXP)² ÷ EXP on counts for 5- and 4-letter cell counts.
• The count-the-1’s test for specific bytes: Consider the file under test as a stream of 32-bit integers. From each integer, a specific byte is chosen, say the leftmost bits 1 to 8. Each byte can contain from 0 to 8 1s, with probabilities 1, 8, 28, 56, 70, 56, 28, 8, 1 over 256. Now let the specified bytes from successive integers provide a string of (overlapping) 5-letter words, each “letter” taking values A, B, C, D, E. The letters are determined by the number of 1s, in that byte 0, 1, or 2 → A, 3 → B, 4 → C, 5 → D, and 6, 7 or 8 → E. Thus we have a monkey at a typewriter hitting five keys with various probabilities 37, 56, 70, 56, 37 over 256. There are 5⁵ possible 5-letter words, and from a string of 256000 (overlapping) 5-letter words, counts are made on the frequencies for each word. The quadratic form in the weak inverse of the covariance matrix of the cell counts provides a chisquare test Q5 – Q4, the difference of the naive Pearson sums of (OBS − EXP)² ÷ EXP on counts for 5- and 4-letter cell counts.
• The parking lot test: In a square of side 100, randomly “park” a car – a circle of radius 1. Then try to park a 2nd, a 3rd, and so on, each time parking “by ear”. That is, if an attempt to park a car causes a crash with one already parked, try again at a new random location. (To avoid path problems, consider parking helicopters rather than cars.) Each attempt leads to either a crash or a success, the latter followed by an increment to the list of cars already parked. If we plot n: the number of attempts, versus k the number successfully parked, we get a curve that should be similar to those provided by a perfect random number generator. Theory for the behavior of such a random curve seems beyond reach, and as graphics displays are not available for this battery of tests, a simple characterization of the random experiment is used: k, the number of cars successfully parked after n = 12000 attempts. Simulation shows that k should average 3523 with sigma 21.9 and is very close to normally distributed. Thus (k − 3523) ÷ 21.9 should be a standard normal variable, which, converted to a uniform variable, provides input to a KSTEST based on a sample of 10.
• The minimum distance test: It does this 100 times choose n = 8000 random points in a square of side 10000. Find d, the minimum distance between the (n² − n) ÷ 2 pairs of points. If the points are truly independent uniform, then d², the square of the minimum distance should be (very close to) exponentially distributed with mean 0.995. Thus 1 − exp(−d² ÷ 0.995) should be uniform on [0,1) and a KSTEST on the resulting 100 values serves as a test of uniformity for random points in the square. Test numbers = 0 mod 5 are printed but the KSTEST is based on the full set of 100 random choices of 8000 points in the 10000×10000 square.
• The 3D spheres test: Choose 4000 random points in a cube of edge 1000. At each point, center a sphere large enough to reach the next closest point. Then the volume of the smallest such sphere is (very close to) exponentially distributed with mean 120π ÷ 3. Thus the radius cubed is exponential with mean 30. (The mean is obtained by extensive simulation). The 3D spheres test generates 4000 such spheres 20 times. Each min radius cubed leads to a uniform variable by means of 1 − exp(−r³ ÷ 30), then a KSTEST is done on the 20 p-values.
• The squeeze test: Random integers are floated to get uniforms on [0,1). Starting with k = 2³¹ = 2147483648, the test finds j, the number of iterations necessary to reduce k to 1, using the reduction k = ceiling(k×U), with U provided by floating integers from the file being tested. Such js are found 100000 times, then counts for the number of times j was ≤ 6, 7, …, 47, ≥ 48 are used to provide a chi-square test for cell frequencies.
• The overlapping sums test: Integers are floated to get a sequence U(1), U(2), … of uniform [0,1) variables. Then overlapping sums, S(1) = U(1) + … + U(100), S(2) = U(2) + … + U(101), … are formed. The Ss are virtually normal with a certain covariance matrix. A linear transformation of the Ss converts them to a sequence of independent standard normals, which are converted to uniform variables for a KSTEST. The p-values from ten KSTESTs are given still another KSTEST.
• The runs test: It counts runs up, and runs down, in a sequence of uniform [0,1) variables, obtained by floating the 32-bit integers in the specified file. This example shows how runs are counted: 0.123, 0.357, 0.789, 0.425, 0.224, 0.416, 0.95 contains an up-run of length 3, a down-run of length 2 and an up-run of (at least) 2, depending on the next values. The covariance matrices for the runs-up and runs-down are well known, leading to chi-square tests for quadratic forms in the weak inverses of the covariance matrices. Runs are counted for sequences of length 10000. This is done ten times. Then repeated.
• The craps test: It plays 200000 games of craps, finds the number of wins and the number of throws necessary to end each game. The number of wins should be (very close to) a normal with mean 200000p and variance 200000p(1 − p), with p = 244 ÷ 495. Throws necessary to complete the game can vary from 1 to infinity, but counts for all > 21 are lumped with 21. A chi-square test is made on the no.-of-throws cell counts. Each 32-bit integer from the test file provides the value for the throw of a die, by floating to [0,1), multiplying by 6 and taking 1 plus the integer part of the result.

Most of the tests in DIEHARD return a p-value, which should be uniform on [0,1) if the input file contains truly independent random bits. Those p-values are obtained by p = F(X), where F is the assumed distribution of the sample random variable X – often normal. But that assumed F is just an asymptotic approximation, for which the fit will be worst in the tails. Thus you should not be surprised with occasional p-values near 0 or 1, such as 0.0012 or 0.9983. When a bit stream really FAILS BIG, you will get ps of 0 or 1 to six or more places. Since there are many tests, it is not unlikely that a p < 0.025 or p > 0.975 means that the RNG has “failed the test at the 0.05 level”. We expect a number of such events ps happen among the hundreds of events DIEHARD produces, even conditioned on the random number generator being perfect.

See also[edit]

Externe Links[edit]