The Advantage of a Window
I already wrote about the sliding-window variation of the Secretary Problem. In this variation, after interviewing a candidate for the job, you can pick him or any out of w − 1 candidates directly before him. In this case we say that we have a sliding window of size w. The strategy is to skip the first s candidates, then pick the person who is better than anyone else at the very last moment. I suggested this project to RSI and it was picked up by Abijith Krishnan and his mentor Shan-Yuan Ho. They did a good job that resulted in a paper posted at the arXiv.
In the paper they found a recursive formula for the probability of winning. The formula is very complicated and not explicit. They do not discuss the most interesting question for me: what is the advantage of a sliding window? How much better the probability of winning with the window as opposed to the classical case without the window?
Let us start with a window of size 2, and n applicants. We compare two problems with the same stopping point. Consider the moment after the stopping point when we see a candidate who is better than everyone else before. Suppose this happens in position b. Then in the classic problem we chose this candidate. What is the advantage of a window? When will we be better off with the window? We will be better if the candidate at index b is not the best, and the window allows us to actually reach the best. This depends on where the best secretary is, and what happens in between.
If the best secretary is the next, in position b + 1, then the window gives us an advantage. The probability of that is 1/n. Suppose the best candidate is the one after next, in position b + 2. The window gives us an advantage only if the person in position b + 1 is better than the person in position b. What is the probability of that? It is less than 1/2. From a random person the probability of the next one being better is 1/2. But the person in position b is not random, he is better than random, so the probability of getting a person who is even better decreases and is not more than 1/2. That means the sliding window wins in this case with probability not more than 1/2n.
Similarly, if the best candidate is in position b + k, then the sliding window allows us to win if every candidate between b and b + k is better than the previous one. The probability of the candidate being better at every step is not more than 1/2. That means, the total probability of getting to the candidate in position b + k is 1/2k-1. So our chances to win when the best candidate is at position b + k are not more than 1/2k-1n. Summing everything up we get an advantage that is at least 1/n and not more than 2/n.
The probability of winning in the classical case is very close to 1/e. Therefore, the probability of winning in the sliding window case, given that the size of the window is 2, is also close to 1/e.
Let us do the same for a window of any small size w. Suppose the best secretary is in the same window as the stopping candidate and after him, that is, the best candidate is among the next w − 1 people. The probability of this is (w − 1)/n. In this case the sliding window always leads to the best person and gives an advantage over the classical case. When else does the sliding window help? Let us divide the rest of the applicants into chunks of size w − 1. Suppose the best applicant is in the chunk number k. For the sliding window to allow us to get to him, the best candidate in every chunk has to be better than the best one in the previous chunk. The probability of that is not more than 1/2k-1. The probability that we get to this winner is not more that (w-1)/2k-1n. Summing it all up we get that the advantage of the window of size w is between (w − 1)/n and 2(w − 1)/n.
Share:
Leave a comment