Optimal versus randomized search of fixed length words

A combinatorial search problem can be defined as follows: Given a set W={w _1, w₂,..., w_m} of m words over a (binary) alphabet Σ, design a sequence of tests that successfully find the word w* ∈ W being sought. The prime goal of the optimal search is to find the sought word w* with the smallest maximum or average search time. Here, we deal with a randomly selected set W of m binary words of fixed length n, that is, the set W={w₁,... w_m} is chosen with equal probability among all possible subsets of size m.