SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
Dataplot Vol 1 Vol 2

CUSUM TEST

Name:
    CUSUM TEST
Type:
    Analysis Command
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:
      \( \alpha \) (recommend value is 0.01)
      Critical
      Region:
      The P-value is computed with the following formula:

        \( \begin{array}{ccl} P-value & = & 1 - \sum_{k = ((-n/z) +1)/4}^{((n/z)-1)/4}{\left[ \Phi((4k+1)z) - \Phi((4k-1)z)\right] } + \\ & & \sum_{k = ((-n/z)-1)/4}^{((n/z)-3)/4}{\left[ \Phi((4k+3)z) - \Phi((4k+1)z)\right] } \end{array} \)

      with z denoting the value of the test statistic, n the number of observations, and \( \Phi \) the cumulative distribution function of the standard normal distribution.

      Conclusion: Reject H0 if the p-value is less than \( \alpha \) (the critical value).
Syntax 1:
    CUSUM TEST <y>             <SUBSET/EXCEPT/FOR qualification>
    where <y> is the response variable being tested;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    The response variable can be a matrix.

Syntax 2:
    MULTIPLE CUSUM TEST <y1> ... <yk>
                            <SUBSET/EXCEPT/FOR qualification>
    where <y1> ... <yk> is a list of 1 to 30 response variables;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    The keyword MULTIPLE is optional. The cusum test will be performed on each response variable and these response variables can be matrices. The TO syntax is supported for the variable list.

Syntax 3:
    REPLICATED CUSUM TEST <y> <x1> ... <xk>
                            <SUBSET/EXCEPT/FOR qualification>
    where <y> is the response variable;
    <x1> ... <xk> is a list of 1 to 6 group-id variables;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    This syntax will cross-tabulate the group-id variables and performs the cusum test for each unique combination of cross-tabulated values. For example, if X1 has 3 levels and X2 has 2 levels, there will be 6 cusum tests performed. This syntax does not support matrix arguments and the keyword REPLICATED is required (to distinguish this from the MULTIPLE case). The TO syntax is supported for the variable list.

Examples:
    CUSUM TEST Y
    CUSUM TEST Y1 TO Y10
    REPLICATED CUSUM TEST Y X1 X2
    CUSUM TEST Y SUBSET TAG > 1
Note:
    The recommended minimum sample size is 100.
Note:
    The following statistics are also supported:

      LET A = CUMULATIVE SUM BACKWARD TEST Y
      LET A = CUMULATIVE SUM BACKWARD TEST PVALUE Y
      LET A = CUMULATIVE SUM FORWARD TEST Y
      LET A = CUMULATIVE SUM FORWARD TEST PVALUE Y

    Enter HELP STATISTICS to see what commands can use these statistics.

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:
    None
Synonyms:
    None
Related Commands: 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:
    Testing for Randomness
Implementation Date:
    2004/1
    2011/3: Support for MULTIPLE option
    2011/3: Support for REPLICATION option
    2011/3: Support for matrix arguments and the TO syntax
    2011/3: Output reformatted, added support for RTF output
    2011/3: Support for SET WRITE DECIMALS 2011/3: Added CUMULATIVE SUM statistics
Program:
     
    LET N = 1
    LET P = 0.5
    LET Y1 = BINOMIAL RANDOM NUMBERS FOR I = 1 1 200
    LET P = 0.58
    LET Y2 = BINOMIAL RANDOM NUMBERS FOR I = 1 1 200
    LET P = 0.65
    LET Y3 = BINOMIAL RANDOM NUMBERS FOR I = 1 1 200
    LET P = 0.85
    LET Y4 = BINOMIAL RANDOM NUMBERS FOR I = 1 1 200
    SET WRITE DECIMALS 4
    .
    CUMULATIVE SUM TEST Y1
    .
    CUMULATIVE SUM TEST Y1 TO Y4
        
    The following output is generated:
          ******************************
          **  CUMULATIVE SUM TEST Y1  **
          ******************************
     
     
                Cumulative Sum Test for Randomness
     
    Response Variable: Y1
     
    H0: The Data Are Random
    Ha: The Data Are Not Random
     
    Summary Statistics:
    Number of Observations:                                      200
     
    Forward Direction Cumulative Sum Test Statistic:          0.8485
    Forward Direction P-Value:                                0.7705
     
    Backward Direction Cumulative Sum Test Statistic:         0.6363
    Backward Direction P-Value:                               0.9394
     
     
     
                Conclusions for Forward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.7705         ACCEPT
          Random          75.0%         0.7705         ACCEPT
          Random          90.0%         0.7705         ACCEPT
          Random          95.0%         0.7705         ACCEPT
          Random          97.5%         0.7705         ACCEPT
          Random          99.0%         0.7705         ACCEPT
          Random          99.9%         0.7705         ACCEPT
     
     
                Conclusions for Backward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.9394         ACCEPT
          Random          75.0%         0.9394         ACCEPT
          Random          90.0%         0.9394         ACCEPT
          Random          95.0%         0.9394         ACCEPT
          Random          97.5%         0.9394         ACCEPT
          Random          99.0%         0.9394         ACCEPT
          Random          99.9%         0.9394         ACCEPT
     
     
          ************************************
          **  CUMULATIVE SUM TEST Y1 TO Y4  **
          ************************************
     
     
                Cumulative Sum Test for Randomness
     
    Response Variable: Y1
     
    H0: The Data Are Random
    Ha: The Data Are Not Random
     
    Summary Statistics:
    Number of Observations:                                      200
     
    Forward Direction Cumulative Sum Test Statistic:          0.8485
    Forward Direction P-Value:                                0.7705
     
    Backward Direction Cumulative Sum Test Statistic:         0.6363
    Backward Direction P-Value:                               0.9394
     
     
     
                Conclusions for Forward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.7705         ACCEPT
          Random          75.0%         0.7705         ACCEPT
          Random          90.0%         0.7705         ACCEPT
          Random          95.0%         0.7705         ACCEPT
          Random          97.5%         0.7705         ACCEPT
          Random          99.0%         0.7705         ACCEPT
          Random          99.9%         0.7705         ACCEPT
     
     
                Conclusions for Backward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.9394         ACCEPT
          Random          75.0%         0.9394         ACCEPT
          Random          90.0%         0.9394         ACCEPT
          Random          95.0%         0.9394         ACCEPT
          Random          97.5%         0.9394         ACCEPT
          Random          99.0%         0.9394         ACCEPT
          Random          99.9%         0.9394         ACCEPT
     
     
                Cumulative Sum Test for Randomness
     
    Response Variable: Y2
     
    H0: The Data Are Random
    Ha: The Data Are Not Random
     
    Summary Statistics:
    Number of Observations:                                      200
     
    Forward Direction Cumulative Sum Test Statistic:          2.1920
    Forward Direction P-Value:                                0.0567
     
    Backward Direction Cumulative Sum Test Statistic:         2.2627
    Backward Direction P-Value:                               0.0473
     
     
     
                Conclusions for Forward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.0567         REJECT
          Random          75.0%         0.0567         REJECT
          Random          90.0%         0.0567         REJECT
          Random          95.0%         0.0567         ACCEPT
          Random          97.5%         0.0567         ACCEPT
          Random          99.0%         0.0567         ACCEPT
          Random          99.9%         0.0567         ACCEPT
     
     
                Conclusions for Backward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.0473         REJECT
          Random          75.0%         0.0473         REJECT
          Random          90.0%         0.0473         REJECT
          Random          95.0%         0.0473         REJECT
          Random          97.5%         0.0473         ACCEPT
          Random          99.0%         0.0473         ACCEPT
          Random          99.9%         0.0473         ACCEPT
     
     
                Cumulative Sum Test for Randomness
     
    Response Variable: Y3
     
    H0: The Data Are Random
    Ha: The Data Are Not Random
     
    Summary Statistics:
    Number of Observations:                                      200
     
    Forward Direction Cumulative Sum Test Statistic:          4.4547
    Forward Direction P-Value:                                0.0000
     
    Backward Direction Cumulative Sum Test Statistic:         4.1012
    Backward Direction P-Value:                               0.0000
     
     
     
                Conclusions for Forward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.0000         REJECT
          Random          75.0%         0.0000         REJECT
          Random          90.0%         0.0000         REJECT
          Random          95.0%         0.0000         REJECT
          Random          97.5%         0.0000         REJECT
          Random          99.0%         0.0000         REJECT
          Random          99.9%         0.0000         REJECT
     
     
                Conclusions for Backward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.0000         REJECT
          Random          75.0%         0.0000         REJECT
          Random          90.0%         0.0000         REJECT
          Random          95.0%         0.0000         REJECT
          Random          97.5%         0.0000         REJECT
          Random          99.0%         0.0000         REJECT
          Random          99.9%         0.0000         REJECT
     
     
                Cumulative Sum Test for Randomness
     
    Response Variable: Y4
     
    H0: The Data Are Random
    Ha: The Data Are Not Random
     
    Summary Statistics:
    Number of Observations:                                      200
     
    Forward Direction Cumulative Sum Test Statistic:         10.8187
    Forward Direction P-Value:                                0.0000
     
    Backward Direction Cumulative Sum Test Statistic:        10.7480
    Backward Direction P-Value:                               0.0000
     
     
     
                Conclusions for Forward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.0000         REJECT
          Random          75.0%         0.0000         REJECT
          Random          90.0%         0.0000         REJECT
          Random          95.0%         0.0000         REJECT
          Random          97.5%         0.0000         REJECT
          Random          99.0%         0.0000         REJECT
          Random          99.9%         0.0000         REJECT
     
     
                Conclusions for Backward Direction Test
     
    ---------------------------------------------------------
                                                         Null
            Null     Confidence                    Hypothesis
      Hypothesis          Level        P-Value     Conclusion
    ---------------------------------------------------------
          Random          50.0%         0.0000         REJECT
          Random          75.0%         0.0000         REJECT
          Random          90.0%         0.0000         REJECT
          Random          95.0%         0.0000         REJECT
          Random          97.5%         0.0000         REJECT
          Random          99.0%         0.0000         REJECT
          Random          99.9%         0.0000         REJECT
        

Privacy Policy/Security Notice
Disclaimer | FOIA

NIST is an agency of the U.S. Commerce Department.

Date created: 2/3/2004
Last updated: 10/13/2015

Please email comments on this WWW page to alan.heckert@nist.gov.