The Mozart Cafe

Two acquaintances travelling independently to Vienna wish to meet for a coffee on the afternoon they arrive. Neither has been to Vienna before, but they guess it must have a Mozart Cafe. So in an email exchange they agree to meet at the Mozart Cafe. Unfortunately, upon arrival they each discover that there are in fact m>1 Mozart Cafes in Vienna. Assuming they have no way to communicate, what should they do?

Suppose that each does one of the following. He/She either (a) chooses one cafe at random and stays there all afternoon, or (b) visits all m cafes in random order spending equal time in each. On average, the best outcome is achieved when one does (a) and the other does (b); on average they will meet half way through the afternoon. However, this cannot be guaranteed since they have no way to agree who should do (a) and who (b). The worst outcome is when both do (a) (unless they are fortunate and choose the same cafe).

Suppose each acquaintance decides to choose his/her strategy randomly, doing (a) with probability p and (b) with probability 1−p. If they fail to meet then they repeat the same strategy on subsequent afternoons, with new random choices, until they meet.

They wish to minimize the expected time until they meet. It turns out that for m=3, the optimal strategy is with p=1/3. As m→∞ the optimal p→≈0.24749.