# Understanding solution to the secretary problem

I am trying to understand the solution to the Secretary Problem (see, e.g., Wikipedia: https://en.wikipedia.org/wiki/Secretary_problem).

As I see it, it is usually solved in the following way: (1) It is clear that the optimal solution is: Reject the first $$r$$ applicants (for some $$r$$), then take the next candidate which is better than all of them. (2) Compute $$r$$.

I do understand (2), but how about (1)? Why is the best solution of this form? On Wikipedia, I only found [reference needed]. So, could somebody explain the solution of the Secretary Problem to me?

• Please state the question, or at least embed the link. People should not have to google the question you are asking. Commented Feb 20, 2019 at 20:52
• Ok, sorry. I thought this was one of the most well-known problems so nobody would have to google. Sorry. Commented Feb 20, 2019 at 20:54
• this may help: math.stackexchange.com/questions/45266/… Commented Feb 20, 2019 at 21:26
• This is an easier explanation of the process...datagenetics.com/blog/december32012/index.html Commented Feb 20, 2019 at 21:46
• That is a good question indeed. I guess a more convincing approach is to "believe" in the answer generated from the solution approach using Linear Programming. In fact there is a lemma stating that "No mechanism can hire the best candidate with probability better than 1/e." in this paper: Dynkin, E. B. 1963. The Optimum Choice of the Instant for Stopping a Markov Process. Sov. Math. Dokl. 4. - However, I am not sure if you can freely access it online. Commented Feb 20, 2019 at 22:04

Partial answer but hopefully this may address one possible confusion (which, I'm guessing, is goal (A) vs goal (B) below).

You have to be very careful about the goal, or optimality criterion. The goal of the problem is to (A) maximize the chance of selecting the very best candidate. The goal is not to (B) select as good a candidate as possible.

Just to divert for a moment: if your goal is to (B) select as good a candidate as possible, and suppose for whatever reason you are down to the last 2 candidates, and the 2nd-last candidate X ranks higher than median, then you should take X, because on average the last (unseen) candidate will rank median. However, if the goal is to (A) select the very best, then you should reject X even if X ranks 2nd-best so far, because if you select X you have failed, whereas if you reject X there is still a $$1/n$$ chance that the last unseen candidate is the very best.

Given goal (A), it is clear that at no stage should you accept a candidate who is not the very best seen so far.

So any best strategy must be of the form: at stage $$t \in [1, n-1]$$, do you accept/reject the current candidate if he/she is the best?

Technically, your strategy can make the accept/reject decision based on what you have seen so far, i.e. the order of the appearance of the previous candidates. E.g. your strategy could in stage 7 make different decisions depending on whether the 1st-appearing candidate is better or worse than the 4th-appearing one. However, given the random initial ordering of the pool, it makes no sense for the best strategy to use that information. I can't really call this a "proof" :) but I hope it's "obvious".

So any best strategy must be of the form: at stage $$t \in [1,n-1]$$, do you accept/reject the current candidate if he/she is the best, as a function of only $$t$$? In other words, the best strategy can be described as an $$(n-1)$$-bit vector, where the $$t$$-th bit describes whether to accept if the $$t$$-th round current candidate is the best seen so far.

It remains to show some form of monotonicity, i.e. there exists some $$r$$ s.t. the best strategy is to reject if $$t \le r$$ and accept if $$t > r$$, and that such a vector (of the form $$[0,0,...,0,1,1,...1]$$) beats any other vector (w.r.t. the goal of maximizing chance of selecting the very best). This part I cannot prove easily. I imagine the proof is that if you have a vector like $$[0, 0, 1, 0, 1,...,1]$$ you will need to show that it is worse than either $$[0,0,1,...1]$$ or $$[0,0,0,0,1...1]$$. Some of the dynamic programming references might help...?

• For the last part, my intuition is the following. So we know that the decision function only depends on two factors, whether the current item is the best so far, and how many items we have not seen. Commented Jun 24, 2019 at 3:51