Search (Q1194277)

This paper reviews the theory of search. The viewpoint is mainly statistical but connections with other fields such as logic and optimization are explored also. Within statistics, screening and group- testing are areas where search methodologies have been employed directly. The dominating ideas of the basic theory are consistency, entropy and Bayes methods. The links between search methods, logic (true, false) and coding theory are shown in depth but the more profound relationships such as between search, packing information and computability are briefly discussed. A broad separation in the area of such methods is between sequential and nonsequential procedures. Most of the review is taken up by sequential procedures. However, some basic work on nonsequential procedures which provide bench-marks for the optimality of sequential procedures, is also explored.