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 started in at time 0, and
those he has visited at times 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. It must be applicable to all life forms.) Very little is
known about this problem.
The problem dates from 1976, when it was proposed by
Steve Alpern as the Telephone Problem: In each of two rooms there are
n telephones randomly stewn around. They are cinnected in a pairwise
fashion by wires. At discrete times t=0,1,2,... players in each room
pick up a phone and say "hello". They wish to minimize the time t
until they first pick up paired phones and can communicate.
A reasonable strategy has been proposed by Anderson-Weber.
This is
one in which, in each block of n-1 successive steps a person either
stays put at his present location (with probability p), or tours the
other n-1 locations in random order (with probability 1-p), repeating
this until meeting occurs. When n is large, the best choice of p is
about 0.2475, and the expected time to meet is about 0.8289n
steps. There might be a better strategy - no one knows. The principal
results that are now known are
1. The Anderson-Weber strategy is optimal for n=2, with p=1/2.
The expected meeting time is 2. Proved in 1990.
2. The Anderson-Weber strategy is optimal for n=3, with p=1/3.
The expected meeting time is 5/2. Proved in 2006. See
weber-k3.pdf