When is it best to follow the leader?

Abstract

An object is hidden in one of $N$ boxes. Initially, the probability that it is in box $i$ is ${\pi }_i(0)$. You then search in continuous time, observing box $J_t$ at time $t$, and receiving a signal as you observe: if the box you are observing does not contain the object, your signal is a Brownian motion, but if it does contain the object your signal is a Brownian motion with positive drift $\mu$. It is straightforward to derive the evolution of the posterior distribution $\pi (t)$ for the location of the object. If $T$ denotes the first time that one of the ${\pi }_j(t)$ reaches a desired threshold $1-\epsilon$, then the goal is to find a search policy $(J_t{)}_{t\ge 0}$ which minimizes the mean of $T$. This problem was studied by Posner and Rumsey (1966) and by Zigangirov (1966), who derive an expression for the mean time of a conjectured optimal policy, which we call {\em follow the leader} (FTL); at all times, observe the box with the highest posterior probability. Posner and Rumsey assert without proof that this is optimal, and Zigangirov offers a proof that if the prior distribution is uniform then FTL is optimal. In this paper, we show that if the prior is not uniform, then FTL is {\em not} always optimal; for uniform prior, the question remains open.

21 pages