Optimal versus randomized search of fixed length binary words

We consider the search problem in which one finds a binary word among m words chosen randomly from the set of all words of fixed length n. It is well known that the optimal search is equivalent to the Huffman coding that requires on average log₂ m bits to be checked plus a small additional cost called the average redundancy. The latter is an oscillating function of m and is bounded between zero and 1-(1+lnln2)/In2≈0.0860713320. As a matter of fact, it is known that finding the optimal strategy for this problem is NP-hard. We propose here several simple randomized search strategies leading, respectively, to the following average redundancies: 1.332746177, 0.6113986565,0.4310617764, and 0.332746177, plus some small oscillations that we precisely characterize. These results should be compared to the optimal, but NP-hard, search algorithm. Our findings extend and make more precise results of Fedotov and Ryabko (2001).