Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T06:02:38.364Z Has data issue: false hasContentIssue false
  • English
  • Français

The rendezvous problem on discrete locations

Published online by Cambridge University Press:  14 July 2016

E. J. Anderson  and
R. R. Weber
E. J. Anderson
Affiliation:
University of Cambridge
R. R. Weber*
Affiliation:
University of Cambridge
*
∗ Postal address for both authors: University of Cambridge, Department of Engineering, Management Studies Group, Mill Lane, Cambridge CB2 1RX, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

Two friends have become separated in a building or shopping mall and and wish to meet as quickly as possible. There are n possible locations where they might meet. However, the locations are identical and there has been no prior agreement where to meet or how to search. Hence they must use identical strategies and must treat all locations in a symmetrical fashion. Suppose their search proceeds in discrete time. Since they wish to avoid the possibility of never meeting, they will wish to use some randomizing strategy. If each person searches one of the n locations at random at each step, then rendezvous will require n steps on average. It is possible to do better than this: although the optimal strategy is difficult to characterize for general n, there is a strategy with an expected time until rendezvous of less than 0.829 n for large enough n. For n = 2 and 3 the optimal strategy can be established and on average 2 and 8/3 steps are required respectively. There are many tantalizing variations on this problem, which we discuss with some conjectures.

Keywords

DYNAMIC PROGRAMMINGSEARCH PROBLEMS
Type
Research Papers
Information
Journal of Applied Probability , Volume 27 , Issue 4 , December 1990 , pp. 839 - 851
Copyright
Copyright © Applied Probability Trust 1990 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramson, N. (1973) Packet switching with satellites. Proc. NCC, 695–702.Google Scholar
Alpern, S. and Asic, M. (1986) Ambush strategies in search games on graphs. SIAM J. Control Optim. 24, 66–75.Google Scholar
Anantharam, V. and Varaiya, P. (1986) An optimal strategy for a conflict resolution problem. Syst. Control Lett. 6, 329–332.Google Scholar
Foreman, J. G. (1977) Differential search games with mobile hider. SIAM J. Control Optim. 15, 841–856.Google Scholar
Gal, S. (1980) Search Games. Academic Press, San Francisco.Google Scholar
Mosteller, F. (1963) Fifty Challenging Problems in Probability with Solutions. Addison-Wesley, New York.Google Scholar
Ross, S. M. (1988) A simple proof of instability of a random-access communication channel. Prob. Eng. Inf. Sci. 2, 383–385.CrossRefGoogle Scholar
Schelling, T. C. (1960) The Strategy of Conflict. Oxford University Press.Google Scholar
Tobagi, F. A. (1980) Multi-access protocols in packet-communications systems. IEEE Trans. Commun. 28, 468–488.Google Scholar
Weber, R. R. (1986) Optimal search for a randomly moving object. J. Appl. Prob. 23, 708–717.CrossRefGoogle Scholar