Bound on the cardinality of a covering of an arbitrary randomness test by frequency tests
K. Yu. Gorbunov · Problems of Information Transmission · 2007
We improve a well-known asymptotic bound on the number of monotonic selection rules for covering of an arbitrary randomness test by frequency tests. More precisely, we prove that, for any set S (arbitrary test) of binary sequences of sufficiently large length L , where ∨ S ∨ ≤ 2 L (1− δ ) , for sufficiently small δ there exists a polynomial (in 1/ δ ) set of monotonic selection rules (frequency tests) which guarantee that, for each sequence t ∈ S , a subsequence can be selected such that the product of its length by the squared deviation of the fraction of zeros in it from 1/2 is of the order of at least 0.5 ln 2 L [ δ /ln(1/ δ )](1 − 2 ln ln(1/ δ )/ln(1/ δ )).