On the theory of random search
A. Rényi · Bulletin of the American Mathematical Society · 1965
Introduction.The problems of search dealt with in this paper can be described by the following simple model.Let S n be a finite set having n^2 distinguishable elements-called points-and suppose that we want to find an unknown point x of the set S n ; the set S n itself is supposed to be known to us.Let us suppose further that it is not possible to observe x directly, however we may choose some functions fiy f 2 , • • • , ƒ# from a given set F of functions defined on S n , and observe the values fi(x), fcix), • • • , JN(X) taken on by these functions at the unknown point x.Of course if F would contain a function ƒ which takes on different values at different points, a single observation of this function would be sufficient.We suppose however that all functions ƒ belonging to the class F axe such that the number of different values taken on by ƒ is much smaller than n.(We shall be especially interested in the case when each ƒ £ F takes on only the two values 0 and 1 and n is a large number.)In such a case of course it is necessary to observe the value of a large number of functions ƒ at the point x.Each such observation gives us only partial information on x (namely it specifies a subset A of S n to which x must belong), but after making a fairly large number of such observations the information obtained accumulates and enables us to determine x.We want to find x by a not too large number of observations.We may e.g.suppose that each observation is connected with a certain cost (or that it requires a definite amount of time) and we want to keep the cost (or duration) of the whole procedure of search relatively low.We shall call a method for the successive choice of the functions /i> • • • i IN, which leads in the end to the determination of the unknown x, a strategy of search.Obviously one usually tries to choose a strategy with N (the number of functions to be observed) as small as possible.Of two search procedures the one which has a smaller (average) duration is the better one, however there may be other requirements.For instance a simple strategy which can e.g.be easily programmed on a computer is usually preferable to a complicated strategy.If A and B are two strategies such that A requires (in the average) the observation of a somewhat smaller number of functions than B (i.e.A is "better" than B) but the effective carrying out of A An elaboration of an address delivered before the Chicago meeting of the Society on April 25,1964, by invitation of the Committee to Select Hour Speakers for Western Sectional Meetings; received by the editors June 18,1965.