Sultan's Dowry Problem

The Sultan's Dowry Problem, also known as the Secretary Problem is this, copied from wiki:

The secretary problem is an optimal stopping problem that has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, and the best choice problem. The problem can be stated as follows:

- There is a single secretarial position to fill.
- There are n applicants for the position, and this is known.
- The applicants can be ranked from best to worst with no ties.
- The applicants are interviewed sequentially in a random order, with each order being equally likely.
- After each interview, the applicant is accepted or rejected.
- The decision to accept or reject an applicant can be based only on the relative -ranks of the applicants interviewed so far.
- Rejected applicants cannot be recalled.
- The object is to select the best applicant. The payoff is 1 for the best applicant and zero otherwise.


Suppose we have 100 candidates. It is obvious that choosing the first candidate will only have a 1/100 chance of selecting the best applicant. The same goes for choosing the last candidate and ignoring all other candidates up to that point. Both options rely on the ordering of the candidates so that the best applicant is the first or the last, respectively in those situations. Clearly the best option is somewhere inbetween choosing the first applicant and the last application. We can go through some of the applicants and use that information in order to choose the best applicant out of the rest we have not seen so far. For example, we if look at 10 applicants and see who is the best applicant out of the 10, then we look through the 90 and choose the applicants such that the applicant is better than the 10 we've seen so far, we have at least a better than 1/100 chance of choosing the best applicant.

It turns out that the probability of selecting the best applicant from the pool goes to 1/e - ex. with 100 applicants you would look through about 100/e ~= 37 applicants and then choose the first applicant that is better than the 37 applicants that you have seen so far. The odds of choosing the best applicant is 37%.



What applications does this solution have?


Let's say that you want to eat Japanese food (sushi more specifically). You know that there are 20 restaurants and you have a general feel of the quality of food at these Japanese restaurants by looking at each of the restaurants. Because of soaring gas prices, you decide that you will not go back to any of the restaurants even if they are better than the ones you have seen so far. How many restaurants should you visit to get the best sushi possible?

Well, the Sultan's Dowry solution says that you should visit at least 20/e, or about 1/3*20 = 6 / 7 restaurants, figure out the best of those 7 restaurants and then choose the first best restaurant out of the ones you haven't been to that is better than the best one you have seen so far.