Abstract:
This paper proposes an algorithm for randomness testing. It is a variant of an
algorithm presented earlier by the author for the construction of random sequences.
The algorithm exploits two facts: Firstly, given a complete finite prefix code Ci over
an alphabet A, every semi-infinite sequence s of symbols x0, x1, x2, ... from A starts with a codeword wi ∈ Ci, and if one presumes that s is random, one can compute
the expected length hi of wi. Secondly, wi can be used to extend Ci to yield a larger
code Ci+1. In this case, the actual length |wi| of wi determines the growth in the
expected codeword length hi+1 for the codeword wi+1 ∈ Ci+1 that follows in s after
the end of wi. If |wi| > hi, then hi+1 grows less compared to hi than if |wi| ≤ hi. By
comparing expected codeword lengths and actual codeword lengths cumulatively,
one may assess the randomness of s: If the hypothesis that s is random holds, then
the cumulative values should closely mirror each other.
