Rendezvous Search on the Labeled Line

The rendezvous search problem is the problem of finding optimal search strategies for two people who are placed randomly on a known search region and want to meet each other in minimal expected time. We focus on initial location distributions that are centrally symmetric and nonincreasing as one moves away from the center, including the discretized and/or truncated Gaussian densities. When the search region is a discrete or a continuous interval, and the interval is labeled so that the searchers know their own location at all times, we prove that the optimal strategy for both searchers is to go directly to the center and wait there. The same result also holds for rendezvous search on the infinite line.