A conjecture of Ross for a search problem (Q1191788): Difference between revisions

This paper deals with a search problem in which a target moves between each of two locations. A searcher may search location \(i\), at a cost \(C_ i\), and with a probability \(\alpha_ i\) of finding the target if it is in that location, \(i=1,2\). If the search is unsuccessful, the target moves from location \(i\) to location \(j\) with probability \(P_{ij}\), \(i,j=1,2\), and the search process continues until the target is located. It is required to find a search strategy, as a function of the probability, \(p\), that the target is in location 1, which minimises the expected cost to termination. If \(V(p)\) is the minimal expected cost, given \(p\), to termination, then \(V(.)\) is the unique solution to (E): \(V(p)=\min[C_ 1+(1-\alpha_ 1 p)V(T_ 1 p)\), \(C_ 2+(1-\alpha_ 2(1-p))V(T_ 2 p)]\), where \(T_ i p\) is the posterior probability of the target being in location 1 given \(p\) and an unsuccessful search of location \(i\), \(i=1,2\). Ross' conjecture is that there exists a \(p^*\in(-\infty,\infty)\) such that it is optimal to search location 1 if \(p\geq p^*\), and to search location 2 if \(p<p^*\). The paper gives a series of results for equation \(E\), and its associated \(n\)-step finite horizon equation, and derives some conditions on the parameters of the problem for which the conjecture holds. It is also shown that if the conjecture holds for the \(n\)-step problem for all integers \(n\geq 1\), then it holds for the original search problem.