CUSUM TEST
Name:
Type:
Purpose:
Perform a cumulative sum test for randomness.
Description:
The cuulative sum test is used to test the randomness of a
sequence of zeroes and ones (Dataplot will covert a data set
with exactly two distinct values to a sequence of zeroes and
ones).
For this test, the zeros are converted to negative ones.
This test is based on the maximum distance from zero of a
random walk defined by the cumulative sum of the sequence.
A large enough distance is indicative of non-randomness.
This test is discussed in detail in SP 800-22 (see Reference
below).
The cumulative sums test is defined as follows.
|
H0:
|
The data are random.
|
|
Ha:
|
The data are not random.
|
Test
Statistic:
|
Compute the partial sums in the forward direction:
S1 = X1
S2 = X1 +
X2
S3 = X1 +
X2 +
X3
...
Sk = X1 +
X2 +
X3 + ... +
Xk
...
Sn = X1 +
X2 +
X3 + ... +
Xn
Similarly, compute the partial sums in the backward
direction:
S1 = Xn
S2 = Xn +
Xn-1
S3 = Xn +
Xn-1 +
Xn-2
...
Sk = Xn +
Xn-1 +
Xn-2 +
Xn-k+1
...
Sn = Xn +
Xn-1 +
Xn-2 +
X1
The test statistic is the absolute value of the
maximum partial sum divided by the square root of
the sample size.
Note that separate test statistics are computed
for the forward and backward directions.
|
Significance
Level:
|
(recommend value is 0.01)
|
|
|
|
Critical
Region:
|
The P-value is computed with the following formula:
with z denoting the value of the test statistic,
n the number of observations, and
the cumulative distribution function of the standard
normal distribution.
|
|
Conclusion:
|
Reject H0 if the p-value is less than
.
the critical value.
|
Syntax:
CUSUM TEST <y>
<SUBSET/EXCEPT/FOR qualification>
where <y> is the response variable being tested;
and where the <SUBSET/EXCEPT/FOR qualification> is optional.
Examples:
CUSUM TEST Y
CUSUM TEST Y SUBSET TAG > 1
Note:
The recommended minimum sample size is 100.
Note:
If you want to test a uniform random number generator,
you can use this test by converting the uniform random
numbers to binomial random numbers. For example,
LET N = 1
LET P = 0.5
LET Y = BINOMIAL RANDOM NUMBERS FOR I = 1 1 1000
CUSUM TEST Y
Default:
Synonyms:
Related Commands:
|
FREQUENCY TEST
|
= Perform a frequency test for randomness.
|
|
RUNS TEST
|
= Perform a runs test for randomness.
|
|
ANDERSON-DARLING TEST
|
= Peform an Anderson-Darling test for randomness.
|
|
UNIFORM PROBABILITY PLOT
|
= Generate a uniform probability plot.
|
Reference:
"A Statistical Test Suite for Random and Psuedorandom Number
Generators for Cryptographic Applications", Andrew Rukhin,
Juan Soto, James Nechvatal, Miles Smid, Elaine Barker,
Stefan Leigh, Mark Levenson, Mark Vangel, David Banks,
Alan Heckert, James Dray, San Vo, NIST SP 800-22, October, 2000.
Applications:
Implementation Date:
Program:
LET N = 1
LET P = 0.5
LET Y = BINOMIAL RANDOM NUMBERS FOR I = 1 1 200
.
CUSUM TEST Y
The following output is generated:
********************
** CUSUM TEST Y **
********************
CUMULATIVE SUM TEST FOR RANDOMNESS
1. HYPOTHESIS:
H0: THE DATA ARE RANDOM
HA: THE DATA ARE NOT RANDOM
2. STATISTICS:
NUMBER OF OBSERVATIONS = 200
CUMULATIVE SUM TEST STATISTIC = 0.8485281
(FORWARD DIRECTION)
CUMULATIVE SUM TEST STATISTIC = 0.6363961
(BACKWARD DIRECTION)
3. P-VALUE OF STATISTIC = 0.7705130
(FORWARD DIRECTION)
P-VALUE OF STATISTIC = 0.7705130
(BACKWARD DIRECTION)
(REJECT HYPOTHESIS OF RANDOMNESS IF P-VALUE IS LESS THAN ALPHA)
4. CONCLUSION (AT THE 5% LEVEL):
THE DATA ARE RANDOM (FORWARD DIRECTION).
THE DATA ARE RANDOM (BACKWARD DIRECTION).
Date created: 2/3/2004
Last updated: 2/3/2004
Please email comments on this WWW page to
alan.heckert@nist.gov.
|
![1 - SUM{k = (-n/z + 1)/4 to (n/z -1)/4}
{NORCDF[(4*k+1)*z] - NORCDF[(4*k-1)*z]} +
SUM{k = (-n/z - 1)/4 to (n/z -3)/4}
{NORCDF[(4*k+3)*z] - NORCDF[(4*k+1)*z]}](eqns/cusumcv.gif)