Abstract
I wish to find something which is located on a certain road. I start at a point on the road, but I do not know in which direction the object sought is to be found. Somehow, I must incorporate in my way of searching the possibility that it is either to the right or to the left. Thus, I must search first to the right, and then to the left, and then to the right again until it is found. What is a good way of conducting this search, and what is a bad way?
This general problem can be phrased in many ways mathematically, some of which are answered in the papers in the bibliography. In this paper, we consider three well-known assumptions concerning thea priori guesses for the probability distribution on where the object is located. These concern uniform distribution on an interval, triangular distribution around the original point, and normal distribution about that point. The uniform distribution has a simple answer. For the triangular distribution, we obtain qualitative results and calculate approximate values for the turning points.
Similar content being viewed by others
References
Anatole Beck,On the linear search problem, Isr. J. Math.2 (1964), 221–228.
Anatole Beck,More on the linear search problem, Isr. J. Math.3 (1965), 61–70.
Anatole Beck and D. J. Newman,Yet more on the linear search problem, Isr. J. Math.8 (1970), 419–429.
Anatole Beck and Peter Warren,The return of the linear search problem, Isr. J. Math.14 (1973), 169–183.
Wallace Franck,An optimal search problem, SIAM Rev.7 (1965), 503–512.
Peter J. Rousseeuw,Optimal search paths for random variables, J. Comput. Appl. Math.9 (1983), 279–286.
Author information
Authors and Affiliations
Additional information
The research of the senior author into this subject has been supported, from time to time, by the National Science Foundation, the Wisconsin Alumni Research Foundation, and the German Academic Exchange Service (DAAD).
The research of the junior author into this subject constituted his honors thesis for a BS with Honors in Mathematics and Computer Science at the University of Wisconsin 1979. The author thanks Prof. Joel Robbin for his help in preparing the thesis.
Rights and permissions
About this article
Cite this article
Beck, A., Beck, M. Son of the linear search problem. Israel J. Math. 48, 109–122 (1984). https://doi.org/10.1007/BF02761156
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02761156