### Tests of randomness of a bit stream

Given a sequence of n bits, we can calculate the following statistics:
1. Frequency: Let n0 be the number of zeroes and n1 be the number of ones in the sequence, then the quantity (n0 - n1)2/n has a chi-square distribution with one degree of freedom
2. Pair frequency: Let n00 be the number of 00 pairs in the sequence and define n01, n10, and n11 similarly. (The pairs can overlap.) The quantity 4*(n002 + n012 + n102 + n112)/ (n-1) - 2*(n02 + n12)/n + 1 has a chi-square distribution with two degrees of freedom
3. 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 ni be the number of occurrences of the ith m-gram and assume k is at least 5*2m, then calculate 2m/k times the sum of the squares of all the ni and subtract k. This quantity has a chi-square distribution with 2m-1 degrees of freedom.
4. Runs: Let Bi be the number of runs of i ones and Gi be the number of runs of i zeroes. Let ei = (n - i + 3)/2i+2, calculate (Bi - ei)2/ ei + (Gi - ei)2/ei and sum these over run lengths from 1 to k, where k is the largest i with ei at least 5. The resulting quantity has a chi-square distribution with 2k - 2 degrees of freedom.
5. 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.