Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 2 / 30K / a

At a given time write $p_i=P_i^t$ and $q_i={\alpha }_i{p}_i$, the conditional probability that the next search succeeds if box $i$ is chosen. Compare two consecutive searches $i,j$, keeping the continuation after two failures fixed. Their expected costs up to that common continuation areThe probability of reaching the common continuation is the same in either order. Moreover,Repeated adjacent interchanges move a box with maximal index to the front without increasing expected cost; applying the same argument after every failure proves the optimal index for Bayesian box search policyFor completeness, after an unsuccessful search of box $i$, Bayes theorem gives the posterior in the Bayesian box search problem: