### Tests of randomness of a bit stream

Given a sequence of *n* bits, we can calculate
the following statistics:
**Frequency:** Let *n*_{0}
be the number of zeroes and *n*_{1} be the
number of ones in the sequence, then the quantity (*n*_{0}
- *n*_{1})^{2}/*n* has a chi-square
distribution with one degree of freedom
**Pair frequency:** Let *n*_{00}
be the number of 00 pairs in the sequence and define
*n*_{01}, *n*_{10}, and *n*_{11}
similarly. (The pairs can overlap.) The quantity
4*(*n*_{00}^{2}
+ *n*_{01}^{2} + *n*_{10}^{2}
+ *n*_{11}^{2})/
(*n*-1) - 2*(*n*_{0}^{2} +
*n*_{1}^{2})/*n* + 1
has a chi-square distribution with two degrees of freedom
*m*-gram: An *m*-gram is
a subsequence of *m* consecutive bits. Let *k* =
floor(*n*/*m*) and split the sequence into *k*
non-overlapping *m*-grams. Let *n*_{i}
be the number of occurrences of the *i*th *m*-gram
and assume *k* is at least 5*2^{m}, then calculate
2^{m}/*k* times the sum of the squares of
all the *n*_{i} and subtract *k*.
This quantity has a chi-square distribution with 2^{m}-1
degrees of freedom.
**Runs:** Let *B*_{i} be the number
of runs of *i* ones and *G*_{i} be the number
of runs of *i* zeroes. Let *e*_{i} =
(*n* - *i* + 3)/2^{i+2}, calculate
(*B*_{i} - *e*_{i})^{2}/
*e*_{i} + (*G*_{i} -
*e*_{i})^{2}/*e*_{i}
and sum these over run lengths from 1 to *k*, where
*k* is the largest *i* with *e*_{i}
at least 5. The resulting quantity has a chi-square distribution
with 2*k* - 2 degrees of freedom.
**Autocorrelation:** Shift the bit sequence by *d*
bits and XOR it with the original sequence, ignoring the *d* bits at the
beginning of the original sequence and those at the end of the shifted
sequence that don't have a second bit for the XOR. Subtract (*n* -
*d*)/2 from the number of XORs that are 1 and normalize by
multiplying by 2/sqrt(*n* - *d*). The resulting
quantity has a normal distribution with mean 0 and variance 1.