University of Cambridge > Mathematics > Statistical Laboratory > Richard Weber > Unsolved problems >

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