Some best choice problems with uncertain recall

Abstract

This thesis investigates an extension of the classical best choice problem which permits attempts at recall of any item passed over at an earlier stage. Three variations of the problem of finding a policy which maximises the probability of obtaining the best of N rankable items for given probability distributions over the availabilities of items from stage to stage, are considered. One variation permits only one attempt to obtain any item, even if that attempt is unsuccessful. Another allows any number of unsuccessful attempts at obtaining an item, while the third variation assumes that, at each stage, all the information about the availabilities of items already inspected is known before a decision whether or not to obtain an item is made. The general solutions of all three problems are given in terms of the optimal control of a Markov chain through at most N steps. Analyses of the problems are carried out under additional simplifying assumptions about the probability distribution on the order of presentation and availabilities of the items. These analyses include sufficient conditions for the optimal policies to have certain simple forms and also the derivation of some asymptotic properties. In particular, asymptotes for the maximum probability of obtaining the best item are given and the asymptotic optimality of sequences of policies of a simple closed form is proved.