As seems to be case whenever you start somewhere new, I’ve needed an almost infinite supply of passport-sized photographs recently. The university, my college, my department and of course the Chinese immigration authorities all wanted a record of my beautiful features. Anyway, as a result of all of this interest, I was in the do-it-yourself photo booth WHSmiths in Wandsworth getting some more the other day. The first attempt looked fine, but the machine offered me the possibility of trying again, up to twice if I wanted. This seemed like a win-win situation, so I said yes, not realising that the one I already had would not be kept ‘in the bag’. The second attempt looked somewhat startled, a pose that runs in my family, but not wanting to risk the possibility of a disastrous third attempt (and the financial penalty of having to do the whole operation again) I confirmed that I was happy and made do with the result. Naturally, the question that struck me: what is the optimal strategy for such a situation? (Assuming that, unlike me, you knew the rules from the beginning)
Mathematical model and choices
Let’s formulate this mathematically. Suppose there are possible trials, corresponding to iid random variables . (Note that this assumes that your ‘performance’ does not improve or otherwise change during the process. Perhaps not a reasonable assumption in some contexts?) After trials have been observed, you have to choose whether to accept the value as your ‘final answer’, or whether to continue.
The first key decision is: what distribution should the s have? Since in the original problem there isn’t a natural metric for quality, let’s assume that the s represent some well-defined quantitative utility, distributed as a uniform [0,1] random variable. Perhaps a normal random variable might be a more realistic model, but I can solve it in this case, so let’s stick to this for now. In addition, for the sake of making the eventual answer more simple, let’s say that 0 is the best quality and 1 is the worst. That is, we are looking for a strategy that stops the process at a time T so as to minimise .
Finding an optimal strategy
The key observation is the following. In words, if we reject , we can forget about its value as that is independent of which is now all that remains to base future judgments on. We return to the original problem with one fewer trial. In more mathematical notation, conditional on , is independent of .
The following argument assumes that an optimal strategy exists, which is not ideal, but can easily be justified. For now though, we proceed relatively informally by induction on .
Let be the stopping time for the optimal strategy on which we assume exists by induction. It is ‘obvious’ that the optimal strategy for should be the following:
- iff , where this is a deterministic quality with dependence only on .
- Conditional on , take .
From this alone, we can calculate .
This is minimised precisely when . We conclude that the optimal strategy, as of course we might well expect, is to take precisely if is less than the expected result of applying the optimal strategy to the remaining random variables.
By extension, we have , and so
The first few values are:
Behaviour of a(n)
The first question is: as grows large, does ? Well this isn’t too hard: the recursive definition (*) confirms that the sequence $a(1),a(2),\ldots$ is (strictly) decreasing, and so has a limit, which must be a fixed point of the equation (*). The only such fixed point is 0.
The second question is: what is the asymptotic behaviour of for large ? A quick run on MATLAB, or examination of the equation (*) suggests that
should describe the behaviour well for large . My basic attempts to verify this were initially unsuccessful, but I felt fairly sure that this should be true in some metric sense because of the following highly non-rigorous but nonetheless convincing idea.
Claim: satisfies (*).
Why? Well, then:
This proves the claim, but none of the = signs are really especially meaningful here. Perhaps there is a really slick way to tie this up that I’ve missed? In any case, I will save my own slightly involved method for a new post.
- Walking, Rain, and False Positive Chemotaxis (eletik.wordpress.com)
- The Delta Method: Applications (maikolsolis.wordpress.com)
Pingback: The Secretary Problem | Eventually Almost Everywhere