Having never been to London before, two friends agree to meet at the entrance to Green Park. Upon arrival, they both realise they've made an elementary mistake - the park has several entrances, and neither has a clue which one the other will be waiting at. Each friend has the binary choice¹ of either staying put in the hope that the other will come and find them, or heading off in search of the other. If both end up waiting for the other they will never meet, while if both leave their starting positions in search for the other there is only a limited chance that their paths will coincide.

A Binary Choice

The simplest layer of the problem is that which we just looked at, with each person making the choice to either stay put or move around. This can be summarised in a table in a similar way to the Prisoner's Dilemma, another binary choice problem.

• Player 1 Moves, and...

  • Player 2 Moves: Both players head off in search of the other.
  • Player 2 Stays: Player 2 waits while Player 1 comes to find them.

• Player 1 Stays, and...

  • Player 2 Moves: Player 1 waits while Player 2 comes to find them.
  • Player 2 Stays: Neither player moves, and they never meet.

We can therefore break the problem up into three different scenarios, and ask how long on average it would take for the two players to meet up. Naturally, it would take until infinity for the players to meet if they both remain stationary, but the other two possibilities require further investigation.

Defining the Problem

Mathematically, the problem of how long it will take for the two friends to find each other if both move can be defined thus:

Two players are randomly placed at different locations in an area Q which contains n different locations to which each player might travel. The players do not know each other's locations. During each turn, a player may either move to an adjacent location or may remain at their existing location. The result of interest is the average number of turns (R) it takes for the two players to occupy the same location.

This situation comes in two varieties. In the first, both players start in exactly the same situation, with no knowledge of what the other player will do, and is known as the symmetrical rendezvous problem. This represents the scenario in which both players do the same thing, going off in search of the other. The opposite is the asymmetrical rendezvous problem, in which the players each adopt a different strategy due to some form of common knowledge, such as a child knowing to stay put while its mother searches for it. This second variety can represent the situation where one friend stays put while the other searches for them.

Asymmetrical Problems

The number of turns taken on average to find the other player is generally smaller for asymmetrical problems than for symmetrical ones. In an asymmetrical problem in which one player remains stationary², the maximum number of turns taken for the players to meet in a given Q will be n-1, provided that the moving player uses a sensible route which visits each location in turn without revisiting old locations. The average number of moves required to meet up in an asymmetrical problem is known as R^A, and can found quite easily provided the player once again sticks to a method, or 'algorithm', which involves visiting a new location each turn.

Number the locations in Q from 1 to n in such a way that the player can visit them in ascending order. Assuming the player is at their starting position at turn number t = 0, they will visit location 2 at t = 1, location 3 at t = 2, right up to location n at turn t = n-1. Since the other player could be waiting at any location, the number of turns taken to meet up ranges from zero to n-1, with each of these numbers of turns having an equal probability. We can therefore find the average number of turns it will take by adding up all these different possibilities and dividing by n, thus giving the surprisingly simple formula³:

R^A = (n - 1)/2

Symmetrical Problems

Assuming that our two players are essentially identical, they will both use the same algorithm when trying to find their friend. As each player will follow the same algorithm, a reasonably useful algorithm should incorporate the following points:

• Each player must search for the other - since the players are both following the same rules, sitting still and waiting for the other player to arrive is not an option.

• The movement should be random - lest the players enter an endless loop. Imagine that Q has only four locations (ie n = 4), as modelled by the corners of a square. If both players start at separate locations and move clockwise around the square each turn, they will never meet. However, if the players move randomly each turn, there is a good chance they will meet.

• Each player must utilise the entirety of Q - if both players were to restrict themselves to nearby locations only, it is possible that they would never meet, depending on how far apart they started in the first place.

The following is a basic algorithm for solving the symmetrical problem, which includes the assumption that the user has a memory of locations already visited:

1. Choose a previously unvisited adjacent location at random and move to it. If this is not possible, move on to step 2. Otherwise, repeat step 1.

2. Move to a location which will bring you adjacent to an unvisited location in the least number of turns.

3. Repeat steps 1 and 2 until all locations have been visited. If the search does not prove successful, repeat the entire process using a new set of random movements.

This isn't the best algorithm available, but it follows the basic rules set out above and therefore gives the players a reasonable chance of meeting up. The average number of turns required to solve a symmetrical problem with a certain algorithm is labelled R^S, but there is no formula that covers all situations and all values of n. For small values of n the best algorithms are known, with n = 2 giving a minimum R^S of 2, while for n = 3 the minimum R^S = ²/₃. For large values of n, a good strategy will result in the players needing to take an average of around 0.8n turns before meeting.

So What Should I Do?

When confronted with a simple rendezvous problem, it is possible to work out which is the best strategy by looking at the chances of finding your friend depending on which choice you make. To do this, you need to know the probability that your friend is either looking for you or staying put, along with the R^A and R^S for the area Q you are meeting within. Assuming that you stick to the rules set out in the definition of the problem set out above, you can work out R^A easily by finding (n - 1)/2. However, we have already discussed how R^S is more difficult to determine, and so we will assume that we are using a large value of n and that R^S = 0.8n. We will call the probability that your friend is looking for you p, with the probability that they are staying put therefore being (1-p).

If you stay put, the probability that your friend will come and find you will be p. Your friend would then take an average of R^A turns to find you. If you start moving, there is a probability of (1-p) that your friend will stay put so that you can find them in an average of R^A turns. There is a probability of p that you and your friend will both move, meeting after an average of R^S turns.

Let's use an example in which Q has 10 locations and your friend decides what to do by tossing a coin. In this case, the following outcomes are possible:

• You stay put and wait for your friend.

  • 50% of the time, your friend will also stay put, giving R = ∞
  • 50% of the time, your friend will come and find you, giving R = 4.5

• You move off in search of your friend.

  • 50% of the time, your friend will stay put, giving R = 4.5
  • 50% of the time, your friend will come and find you, giving R = 8

These results show that if you think your friend is equally likely to decide to wait or to come looking for you, it is a safer bet to start looking for them. However, if your friend is more likely to move than to stay and wait for you, the problem becomes a little trickier. Also, in reality it is likely that both players will alternate between waiting and moving and may have some idea what the other player might be thinking, thus allowing them to try and predict their moves. The best solution to this classic social version of the problem is to agree a specific meeting place or to have some way in which you can communicate.

Commercial Applications of the Problem

The Rendezvous Problem can be used to represent a variety of scenarios, ranging from the synchronisation of robots with minimal communication to the modelling of the synchronisation and desynchronisation of two computer processors working to solve a problem in parallel. In the robot situations, such as those where robots must meet up to exchange loads or information at one of a number of different landmarks without arranging the meet beforehand, the problem is made more complex by involving other concepts such as which location is the most preferable for the meeting to occur at, and slight differences between capabilities of the players involved. For more information about robot rendezvous problems, see this PDF file. Meanwhile, the application of the problem to parallel processors is used to ensure that the two processors do not each stop and wait for the other to finish part of a problem before continuing, as this would cause the system to crash.