pith. sign in

arxiv: 1804.05479 · v1 · pith:O2D2WIMQnew · submitted 2018-04-16 · 🧮 math.OC

When is it best to follow the leader?

classification 🧮 math.OC
keywords objectoptimalthentimepriorsignaluniformbrownian
0
0 comments X
read the original 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-\varepsilon$, then the goal is to find a search policy $(J_t)_{t \geq 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.