Optimal versus randomized search of fixed length binary words
We consider the search problem in which one rinds 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(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 approximate 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.
search problem huffman code generating functions patricia trie shannon source coding theorem tries