A proof of Ross's conjecture for two-site moving-target search
2026-08-10 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a problem where a target moves between two locations according to certain probabilities, and one tries to find it by searching these sites, but searches can fail even if the target is present. They build on prior work by Ross, MacPhee, and Jordan, who suggested and partially proved that an optimal search strategy depends on whether the probability the target is at site 1 crosses a certain threshold. The authors complete the proof for all cases where the transition matrix determinant is positive, showing that the best search policy follows this threshold rule. They also analyze special cases where searches always miss the target and extend the results accordingly.
Markov chaintransition matrixthreshold policyposterior probabilityBellman equationMarkov decision processdiscounted and undiscounted costslog-oddssearch theory
Authors
Yunpeng Li
Abstract
A target moves between two sites according to a discrete-time Markov chain with transition matrix $M$. At each epoch one site is searched at positive cost, and a search of site $i$ misses a target that is present there with probability $α_i$. In the classical range $α_i<1$, Ross conjectured that an optimal policy is threshold in the posterior probability that the target is at site 1. MacPhee and Jordan proved the conjecture throughout the nonpositive-determinant regime for interior transition matrices, and for many additional transition laws, but left part of the regime $\det M>0$ unresolved. We prove threshold optimality throughout $\det M>0$. In unnormalised survivor coordinates, finite search words have affine costs. The two Bellman branches generate word pairs with a two-level prefix-count constraint; a nested sequence of local swaps and nested projective intervals then yield a common separator that rules out reverse crossing. A log-odds contraction closes the finite-horizon induction, and a uniform $O(1/n)$ truncation bound passes the result to the undiscounted infinite horizon. Combined with MacPhee--Jordan and boundary continuity, this proves Ross's conjecture for every two-site transition matrix when $α_i<1$. We also classify the endpoint cases $α_i=1$ under the extended-real expected-cost criterion.