Using maths to optimally renew my passport

I recently had to renew my passort. For this, I needed a recent headshot of myself. As I didn’t have one at home, I went to a photo booth. For the 5€ that I paid, I could have up to three shoots taken. However, I (crucially) had to decide whether I wanted to use one before having the next taken.

At the time, I was reading the book ‘Algorithms to live by’, which spent quite a lot of time discussing optimal stopping problems. One of this problems is known as the Secretary problem, and I realised that I was facing (almost) precisely a particular case of it (the case n=3).

Quoting Wikipedia, the general problem is as follows:

Imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant.

Clearly, if the decision can be deferred to the end, this can be trivially solved. Luckily, in real life that is often the case. However, we are assumming that here it has to be made immediately (as was the case for the photo booth), which makes it much harder.

The problem is solvable, and the optimal solution is known.

In the limit of large n (where n is the number of applicants), one should interview the first 1/e % of canditates (which is about 37%) without making any offer. After this threshold is passed, one should hire a candidate only if it is the best candidate yet seen (or if it is the last one!). This gives a probability of success that is also asymptotic to 37%.

When I was in the photo booth, the ‘number of applicants’ (i.e., the number of shoots) was 3, which wasn’t large enough for the above to apply (although in general, the solution converges quite fast, so the probabilities of success when there are 100 or 100 million applicants is virtually indistinguisable).

When n=3, the algorithm also follows a ‘explore-exploit’ structure.

One should always reject the first candidate, no matter how good she is. Then, one should choose the second candidate only if it is better than the first one, and reject otherwise. In the latter case, one is obligued to get the third candidate.

The probability of success can be easily calculated to be 50%:

P(success)= P(2nd is best)+ P(3rd is best)P(2nd worst than 1st) = 1/3 + (1/3)(1/2)=(1/3)(3/2)=1/2

I think that’s quite good!

I did use the algorithm (I’m a big fan of optimising my life). It’s true that I just didn’t like the first picture, so it was easy to reject it. When I saw the second picture, which was better than the first one, I hesitated, but I trusted the algorithm. Of course, I’ll never know how the third photograph would have been.

I was very surprised to see this problem appearing in my ‘real’ life, but nonetheless I have still simplified things a bit. For example:

• For my passport picture, I may not want to optimise my chance of getting the best of the 3. Rather, I was probably maximizing my chances of ending up with an okay picture. (And in this case, had the first one been okay, I should have taken it.)
• I have some prior knowledge about the quality of the photographs. I know that, while I like my self-image, I tend not appear that great in close headshots. Had the first one been the best picture of myself ever taken, I should have really taken it!
• I could have been risk-averse (maximizing the chances of a decent photo) but I could also have afforded to take a more risky approach. After all, if I didn’t like the third and final picture, I could have paid another five euros for another round of up to three pictures.

Anyways, enough of that.

To conclude, I think optimal stopping problems are both very interesting mathematically and very applicable to real life.

More examples that I like (some discussed in the book):

• Finding a flat (very hard at the moment!)
• Selling a house
• Dating or marrying someone (Warning: I think this is probably taking it to far, but read on what Kepler did…)
• Choosing a career

---