Tests of randomness of a bit stream

1. Frequency: Let n₀ be the number of zeroes and n₁ be the number of ones in the sequence, then the quantity (n₀ - n₁)²/n has a chi-square distribution with one degree of freedom
2. Pair frequency: Let n₀₀ be the number of 00 pairs in the sequence and define n₀₁, n₁₀, and n₁₁ similarly. (The pairs can overlap.) The quantity 4*(n₀₀² + n₀₁² + n₁₀² + n₁₁²)/ (n-1) - 2*(n₀² + n₁²)/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 n_i be the number of occurrences of the ith 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.
4. 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ⁱ⁺², calculate (B_i - e_i)²/ e_i + (G_i - e_i)²/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 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.