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.sub.2] 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 + ln ln 2)/ln 2 [approximately equal to] 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 recent results of Fedotov and Ryabko. Index Terms--Generating functions, Huffman code, PATRICIA trie, search problem, Shannon source coding theorem, tries.