How information can confuse you — the secretary problem

I always found the secretary problem baffling. The solution never made sense to me. With most of the articles presenting the problem and the solution (mostly) incorrectly, it confused me more. So I decided to flush every bit of the knowledge I had about it and start from scratch.

**I am assuming you all have a grasp on total probability theorem, random variables, conditional expectation — the basic stuff as this goes beyond the original question

Revisiting the original question, as quoted from wikipedia:

Imagine an administrator who wants to hire the best secretary out of 100 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 problem that I have found in various explainers is the way they ‘rank’ the candidates (even veritasium does this — great video otherwise). Giving them a rating on some five star scale. The thing is, and is mentioned in the problem very specifically, the comparison can only be made among the candidates themselves. Using a ‘scale’ contradicts that. And it’s not easy to get these ideas out of my head. Let me try to reframe the question so as to get a fresher perspective for solving this.

Imagine you are a thief wanting to steal the most expensive painting in a museum gallery. The 100 pieces are arranged along a long corridor with their price tags attached to the bottom of the frame. There is only one entry point at the start and the exit is at the other end of the corridor. With no prior knowledge about artworks, you want to enter and exit with the most expensive one. Since time is short, you cannot put back the one that is already taken or swap with some other one nor can you turn back and risk getting caught.

That looks better. More interesting.

It is pretty clear about the stuff that is known (or rather unknown). It is easier to understand comparison in terms of price of the painting instead of ‘ratings’. The price can be anything like $10,000 or $1,000,000 or even more or less, you don’t know! When rating a candidate, the mind automatically drifts towards some scale like from 1–5 stars. If you already rate some candidate a 4.5 will you be willing to move on to the next one? How likely is that the next candidate will be able to beat that 4.5? This leads to incorrect understanding of the problem at hand by limiting the minimum and maximum rating one can get (will come back to this later though).

**I do not condone robbery of precious art pieces however enticing they might look

Now to solve the problem it helps to actually construct what you want in terms of language and simplifying it. That’s what I find brilliant about probability as a whole. The basic blocks of conditional arguments and total probability and other stuff are important. The magic lies in twisting the language into the information that you can actually use!

For simplicity, I can say that there are N(=100) paintings such that there are no same values that can occur. And each order is equally likely. Constructing the probability argument as follows using total probability theorem.

Now to finding the most expensive painting, let it be Ta. Suppose you look through the paintings from 1 to r (some arbitrary number) and reject taking all of them. The information you have is the relative price with respect to each other, one with being the most expensive of them all, name it Tb. Now you do not have ANY IDEA regarding the values that lie ahead compared to what you have already seen. So at any point you reach, the only metric of comparison is the set of paintings that you previously saw.

So the only way to decide on taking the most expensive one is to construct an ‘information set’ first rejecting a set number of paintings. And then selecting the first one that is more valuable than Tb, let this be Tc. Note that this does not guarantee that Ta is not same as Tb, nor that Ta will come after Tb. We need to maximise the chances of getting hold of Ta by optimising for the r we choose.

Solving for above to obtain the optimal value of r. Just plug in different values of r to obtain the best possible probability of success. Beautifully shown by the graph in desmos by taking N=100. The r comes out to be 37.

Note that I haven’t provided a more rigorous method of translating the series into integral, but that is not really the purpose of this article. The result is fascinating though, with a whopping ~37% probability of getting the best value!

I wasn’t completely satisfied stopping here. I had so many questions in my head. Will you follow the same strategy if you had some extra information? Like if the highest value is known beforehand, you will be able to steal the best painting with absolute certainty.

If you knew a range say the prices lie within $1M and $10M, how would the strategy change? Think about the information you have now. You come across a $9M painting at the first try. Would you take it or expect a more expensive one to be present somewhere at the end of the aisle? The problem itself changes as you don’t really want to get the best one (which you can assume to be $10M but not necessarily present) but maximising the value you can obtain.

It is difficult to construct a probability problem in real life with such information available (though I hope you do not come across as an art thief), let alone solving for it. It helps to make assumptions and be very clear about its implications. Like do the paintings have any relationship wrt each other? Probably not and can be considered independent to each other. What about the values they take? Can we approximate the kind of distribution it follows? There is no information on that. We can lay another assumption of it taking a uniform distribution with [1,10], which seems reasonable.

Now what should your strategy look like? Suppose you end up at ith painting with some value x. How to decide if you should take it or not? Logically speaking if x ≥ E[max painting value we can get in [j+1,..,N]] then it makes sense to take it and run. Since each is independent of the other, only variable here is the number of remaining paintings. Let this expected value be denoted as E[Zi], for the remaining i paintings.

Suppose there was only one painting in the room, N=1. The expected value comes out to be $5.5M. E[Z1] = 5.5. Now if there were only two, you come across the value of the first. If it turns out to have a value more than 5.5, then it makes sense to take it. Otherwise move on to the next (final) one. This is the strategy that is to be repeated. Take if Xj > E[Zi-1]. Else move onto the next and get the value E[Zi-1]. This whole thing can be constructed as follows:

This gives a recursive formula. Solving for various components:

Plotting using desmos, it can be seen that it converges to 10 as N grows larger and larger. It is highly likely to get a painting of ~$9.83M in an aisle of 100 paintings.

Of course this is true only when the assumptions are true. The paintings may not even follow a uniform distribution. Though I would end it here for now and let you guys imagine about other information that can carry this into some completely different direction!

CONCLUSION

The point of this article was not only to give a clear understanding of the secretary problem — this can be found in various sources — but to structure a way to using information to construct probability arguments. It is important to understand what we want to find out in terms of the mathematical knowledge we have. Many such non-deterministic problems can be figured out of limited details and educated assumptions. Gaining such insights out of (so much) data today is an important skill to learn.