SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Contacts SED Projects SED Products and Publications Search SED Pages
Dataplot Vol 1 Auxiliary Chapter

FREQUENCY TEST

Name:
    FREQUENCY TEST
Type:
    Analysis Command
Purpose:
    Perform a frequency or frequency within a block test for randomness.
Description:
    The frequency (or frequency within a block) 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). The test is based on the proportion of zeroes and ones. Specifically, it tests the closeness of the proportion of ones to 0.5. The frequency within a block test is a refinement that tests the proportion of ones within M-value blocks.

    The frequency test is defined as follows.

      H0: The data are random.
      Ha: The data are not random.
      Test
      Statistic:       		The test statistic is

        s(obs) = |S(n)|/SQRT(n)

      with n denoting the number of observations in the sequence and Sn = X1 + X2 + ... + Xn. The Xi are the data values where the zero values have been converted to negative ones.

      Significance
      Level:       		alpha (typically set to 0.01 for this test)
      Critical
      Region:       		sobs > NORPPF (1-alpha/2)

      with NORPPF denoting the percent point function of the standard normal distribution.

      Conclusion: Reject H0 if the test statistic is greater than the critical value.

    For the frequency within a block test, we partition the input values into N=[n/m] non-overlapping blocks with n denoting the number of observations and m the number of observations within a block. Any unused observations are discarded. The frequency within a block test is then defined as follows.

      H0: The data are random.
      Ha: The data are not random.
      Test
      Statistic:       		Compute the proportion, pi(i), of ones in each block (i.e., the number of ones in the block divided by m). The test statistic is

        chi-square(obs) = 4*m*SUM[i=1 to N][(pi(i) - 0.5)**2]

      Significance
      Level:       		alpha (typically set to 0.01 for this test)
      Critical
      Region:       		Compute the p-value

        IGAMC(N/2,chi-square(N/2,chi0square(obs)/2)

      with IGAMC denoting the incomplete gamma function (enter HELP GAMIP for details).

      Conclusion: Reject H0 if the p-value < alpha.
Syntax 1:
    FREQUENCY TEST <y>             <SUBSET/EXCEPT/FOR qualification>
    where <y> is the response variable being tested;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.
Syntax 2:
    FREQUENCY BLOCK TEST <y>
                            <SUBSET/EXCEPT/FOR qualification>
    where <y> is the response variable being tested;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    The length of the block is set by entering the command

      LET M = <value>

    before entering the FREQUENCY BLOCK TEST command.

Examples:
    FREQUENCY TEST Y

    LET M = 20
    FREQUENCY BLOCK TEST Y SUBSET TAG > 1

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
      FREQUENCY TEST Y
Note:
    The recommended minimum sample size for both the frequency test and for the frequency within a block test is 100.

    For the frequency within a block test, it is additionally recommended that the block size should be at least 20 and it should also be greater than or equal to 0.01 times the sample size. It is recommended that the number of samples within a block be less than 100.

Default:
    None
Synonyms:
    FREQUENCY WITHIN A BLOCK TEST and FREQUENCY WITHIN BLOCK TEST are synonyms for FREQUENCY BLOCK TEST.
Related Commands:
    CUSUM TEST = Perform a cumulative sum 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:
    Testing for Randomness
Implementation Date:
    2004/1
Program: 
     
LET N = 1
LET P = 0.5
LET Y = BINOMIAL RANDOM NUMBERS FOR I = 1 1 200
.
FREQUENCY TEST Y
.
LET M = 10
FREQUENCY BLOCK TEST Y
    The following output is generated: 
           ************************
       **  FREQUENCY TEST Y  **
       ************************
  
  
               FREQUENCY TEST FOR RANDOMNESS
  
 1. HYPOTHESIS:
    H0: THE DATA ARE RANDOM
    HA: THE DATA ARE NOT RANDOM
  
 2. STATISTICS:
    NUMBER OF OBSERVATIONS      =      200
    SUM OF +1 AND -1 VALUES     =   -6.000000
  
    FREQUENCY TEST STATISTIC    =   0.4242641
  
  
 3. P-VALUE OF STATISTIC  =   0.6713735
    (REJECT HYPOTHESIS OF RANDOMNESS IF P-VALUE IS LESS THAN ALPHA)
  
 4. CONCLUSION (AT THE 5% LEVEL):
    THE DATA ARE RANDOM.
  
  
       ******************************
       **  FREQUENCY BLOCK TEST Y  **
       ******************************
  
  
               FREQUENCY WITHIN A BLOCK TEST FOR RANDOMNESS
  
 1. HYPOTHESIS:
    H0: THE DATA ARE RANDOM
    HA: THE DATA ARE NOT RANDOM
  
 2. STATISTICS:
    NUMBER OF OBSERVATIONS                  =      200
    BLOCK SIZE                              =       20
    NUMBER OF OBSERVATIONS WITHIN A BLOCK   =       10
  
    FREQUENCY WITHIN A BLOCK TEST STATISTIC  =    8.600000
  
  
 3. P-VALUE OF STATISTIC  =   0.5704381
    (REJECT HYPOTHESIS OF RANDOMNESS IF P-VALUE IS LESS THAN ALPHA)
  
 4. CONCLUSION (AT THE 5% LEVEL):
    THE DATA ARE RANDOM.

Date created: 2/3/2004
Last updated: 2/3/2004
Please email comments on this WWW page to alan.heckert@nist.gov.