A forward-parsing randomness test based on the expected codeword length of T-codes

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 C_i over an alphabet A, every semi-infinite sequence s of symbols x₀, x₁, x₂, ... from A starts with a codeword w_i ∈ C_i, and if one presumes that s is random, one can compute the expected length h_i of w_i. Secondly, w_i can be used to extend C_i to yield a larger code C_i+1. In this case, the actual length |_Wi| of w_i determines the growth in the expected codeword length h_i+1 for the codeword w_i+1 ∈ C_i+1 that follows in s after the end of w_i. If |w_i| >; h_i then h_i+1 grows less compared to h_i, than if |_Wi| ≤ h_i. 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.