When is it best to follow the leader?

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:130

Article

Ernst, Philip¹  Rogers, L. C. G.²  Zhou, Quan³ 

[1] Rice Univ, Dept Stat, Houston, TX 77005 USA

[2] Ctr Math Sci, Stat Lab, Cambridge CBS 0WB, England

[3] Texas A&M Univ, Dept Stat, College Stn, TX 77843 USA

关键词: Follow the leader;    Optimal scanning;    Quickest search;    Tanaka's stochastic differential equation;    First exit time;   

DOI  :  10.1016/j.spa.2019.09.017

来源: Elsevier

【 摘 要 】

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 >= 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 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 not always optimal; for uniform prior, the question remains open. (C) 2019 The Authors. Published by Elsevier B.V.

【 授权许可】

Free