Optimal index for Bayesian box search
= Optimal index for Bayesian box search
{title2=$\alpha_i p_i/c_i$}
When search continues until discovery, expected search cost is minimized by searching at each step a box maximizing $\alpha_i p_i/c_i$. An adjacent-interchange argument compares two searches: placing $i$ before $j$ costs less exactly when $\alpha_ip_i/c_i\geq\alpha_jp_j/c_j$.