Estimation of the Number of Elements in a Covering of an Arbitrary Randomness Test by Frequency Tests

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|\le2^{L(1-\delta)}$, for sufficiently small $\delta$ there exists a polynomial (in $1/\delta$) set of monotonic selection rules (frequency tests) which guarantee that, for each sequence $\boldsymbol t\in 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\ln2\,L[\delta/\ln(1/\delta)](1-2\ln\ln(1/\delta)/\ln(1/\delta))$.