The rendezvous problem on discrete locations
E.J. Anderson and R.R. Weber,
J. Appl. Prob. 27 839-851, 1990.
Abstract
Two friends have become separated in a building or shopping mall 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.829n$ 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 tantilizing variations on this
problem, which we discuss with some conjectures.
back to list of papers
DISCUSSION
Here is a problem which I and a colleague formulated a few years ago. It
occurred to me that it may be the sort of thing that people who read this
newsgroup would enjoy thinking about.
THE RENDEZVOUS PROBLEM
Two people are lost from each other a maze of n rooms. How should they move
around in order to minimize the expected time it will take for them to find
one another? This is roughly the problem you face if you go to a shopping
mall with a friend, become separated, and then wonder how to find your friend
in minimal time, knowing that he may also be hunting for you.
The problem arose through modelling issues that arise in synchonizing or
de-sychonizing parallel processors performing a calculation.
Suppose the n rooms are identical, unlabelled and there is no map that allows
the players to break the symmetry of the set up. The travelling time between
any two rooms is the same. Therefore, until such times as they meet, each of
the two players must simply choose a room to visit at time t, as a function of
the rooms he has visited at times 0,1,...,t-1, (this being information he can
remember). Each player has his own personal labelling of the rooms.
If one player stays still and the other tours the the rooms one by one in
random order then the expected time is clearly n/2. But the two persons have
no way of deciding which of them should stay still while the other searches.
If they both search rooms at random, the expected meeting time is n. But is
there some algorithm they can follow, which is symmetric with respect to the
two people - (perhaps an algorithm which they both read in their copies of the
Hitchhiker's Guide to the Galaxy) -, that guarantees an expected meeting time
less than n? The rules of this problem are that the algorithm is not allowed
to break symmetry by referring to some external information, such as saying
`the older person should do X, while the younger does Y.' (The HHGTTG cannot
rely on readers knowing such facts about one another.)
Here is what is known an unknown about this problem:
1. The optimal algorithm for n=2 is known. The expected meeting time
is 2.
2. The above paper claimed to have the optimal strategy for n=3, but
an error was later found. It has taken 15 years to find a proof for
n=3. See now
weber-k3.pdf
The optimal algorithm for n=4 and higher is not known.
3. There are algorithms that guarantee meeting in about 0.8n, but no
knowledge of what is best, or whether something less than linear growth
in n is possible.
4. Surprisingly, it has not been proved that the minimal expected
meeting time is an increasing function of n. This appears harder to
prove than you would first think!
5. If the players are allowed to leave complicated messages for each
other behind in the rooms, they still cannot manage to meet in
expected time less than a constant times sqrt(n). If they can leave
messages behind, these message need be no more complicated that to
simply say, "I was here", in order to realise an expected meeting time
less than a constant time sqrt(n).
6. If the problem is modified so that players are not symmetric and
they are therefore allowed to follow different algorithms, i.e., one
is a child and the other a parent, then the optimal solution is for
the child to stay still while the parent looks for her (taking n/2
steps on average). This is obvious, but a proof of optimality is
harder than you might think.
(I didn't intend to write so much about this problem, but I got
carried away, thinking this might be an interesting problem for
rec.puzzles or math.research, where I may post it.)
Reference:
Anderson, E.J. and Weber, R.R. (1990) The rendezvous problem on discrete
locations", Journal of Applied Probability, 28, 839-851.
+-------------------------+---------------------------------------------+
| Prof Richard R. Weber | Email: rrw1@statslab.cam.ac.uk |
| Statistical Laboratory | Post: 16 Mill Lane, Cambridge, UK, CB2 1SB |
| University of Cambridge | Tel: +44 223 337953 Fax: +44 223 337956 |
+-------------------------+---------------------------------------------+