The maximum entropy principle in search theory

A. N. Prokaev

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 19 (2023) no. 1, pp. 27-42

Résumé

The paper considers the relationship between search theory and information theory. The traditional problem of search theory is to develop a search plan for a physical object in the sea or on land. The search plan has to develop the distribution of available search resources in such a way that the probability of detection the search object is to be maximum. The optimal solution is traditionally considered as so-called "uniformly optimal search plan’’, which provides a uniform distribution of the posterior probability of the location of the object as the search is conducted. At the same time, optimality simultaneously according to the criteria of maximum detection probability and equality of a posteriori probability is possible only for the exponential detection function, which is used most often in search theory. For other kinds of detection functions, the optimal solutions according to the specified criteria do not match. In this paper, the approach to this problem is considered on the basis of the maximum entropy principle. For a situation of discrete distribution, it is shown that, within the framework of information theory, the search problem has a simpler solution that does not depend on the kind of the detection function.

Détail

Keywords: information theory, search theory, uniformly optimal search plan, detection function, maximum entropy principle.

Bibliographie

[1] Ackoff R. L., Sasieni M. W., Fundamentals of operations research, John Wiley Sons, Inc, New York, USA, 1967, 455 pp. | MR

[2] Mela D. F., “Letter to the editor — information theory and search theory as special cases of decision theory”, Operations Research, 9:6 (1961), 907–909 | DOI | Zbl

[3] Koopman B. O., Search and information theory, Part of final report on stochastic processes in certain naval operations, Columbia University, New York, USA, 1967, 126–134

[4] Barker W. H., “Information theory and the optimal detection search”, Operations Research, 25:2 (1977), 304–314 | DOI | MR | Zbl

[5] Pierce J. G., “A new look at the relation between information theory and search theory”, The maximum entropy formalism, MIT Press, Cambridge, USA, 1978, 339–402 | MR

[6] Jaynes E. T., “Entropy and search theory. Maximum-entropy and Bayesian methods in inverse problems”, Fundamental theories of physics, 14, Springer, Dordrecht, Netherlands, 1985, 1–8 | MR

[7] Shannon C. E., “A mathematical theory of communication”, Bell System Techn. Journal, 27:4 (1948), 623–656 | DOI | MR | Zbl

[8] Ahlswede R., Wegener I., Suchprobleme, Eng. Search Problems, Teubner Verlag, Stuttgart, Germany, 1979, 273 pp. | MR | Zbl

[9] H. Aydinian, F. Cicalese, C. Deppe (eds.), Information theory, combinatorics, and search theory: in memory of Rudolf Ahlswede, Lecture Notes in Computer Science, 7777, Springer, Cambrige, 2013, 773 pp. | DOI | MR | Zbl

[10] Stone L. D., Theory of optimal search, Academic Press, New York, USA, 1975, 260 pp. | MR | Zbl

[11] Stone L. D., Royset J. O., Washburn A.R., Optimal search for moving targets, International Series in Operations Research Management Science, 237, Springer, Switzerland, 2016, 312 pp. | DOI | MR | Zbl

[12] Koopman B. O., Search and screening, Operations evaluation group report No 56, Center for Naval Analyses Publ, Alexandria, 1946, 176 pp. | MR

[13] Koopman B. O., “The theory of search. The optimum distribution of searching effort”, Operations Research, 5 (1957), 613–626 | DOI | MR | Zbl

[14] De Guenin J., “Optimum distribution of effort: An extension of the Koopman basic theory”, Operations Research, 9 (1961), 1–7 | DOI | MR