A proof of Ross's conjecture for two-site moving-target search

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.

Disclosure

“ch two Bellman histories satisfy a bounded-width lattice condition analogous to (4.1); the same bubble-and-separator principle may then provide threshold results outside the standard one-step supermodularity framework. Acknowledgements OpenAI’s ChatGPT (GPT-5.6 Sol) was used to assist with brainstorming proof strategies, literature searching, symbolic and computational sanity checks, and preparation of an initial draft. The author independently verified the mathematical arguments and ref”

PDF page 28

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:07:25.909637Z

Structural counts