Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We know the solution of the Sultan's dowry problem: To reject the first $n/e$ candidates and then to select the first who exceeds the best of the sample. How to find the best strategy if we want select the 2, or 3, or $k$ best instead of only one?

share|improve this question
5  
While it is good that you included a link to Sultan's dowry problem, considering that the problem is fairly easy to state, it'd be great if you can also include the full problem statement in the question text. In general we should try to aim to make questions as self-contained as possible on this site. –  Willie Wong Apr 3 '11 at 1:58
1  
It's strange that you give a link to the solution but give a different solution. It seems the solution you link to is correct and yours is just an approximation; for instance, the correct solution differs for $n=3$ and $n=4$ and yours doesn't (irrespective of how you round $n/\mathrm{e}$ to an integer). (By the way, I changed the title, because it's not a "probability generalization"; "probability" is a tag that doesn't belong in the title.) –  joriki Apr 3 '11 at 5:45
add comment

2 Answers

up vote 8 down vote accepted

This problem is also called (and may be better known as) the secretary problem.

The $k=2$ case was solved independently by Nikolaev ("On a generalisation of the best choice problem," Theory of Probability and Its Applications 22, 187-190, 1977) and Tamaki ("Recognizing both the maximum and the second maximum of a sequence," Journal of Applied Probability 16, 803-812, 1979). The optimal strategy is the following. Pass over the first $r^*_2-1$ candidates and then use the first choice to accept the next candidate that is the best seen thus far. After that, continue and use the second choice to accept the next candidate that is either 1) the best seen thus far, or 2) the second-best candidate that has been seen after $r^*_1-1$ candidates have been considered. Tamaki gives explicit values for $r^*_1$ and $r^*_2$ as well as the asymptotics $r^*_2/N \to d_2 \approx 0.2291$, where $x$ is the solution to $(1+x)e^{1/2} - \ln x = 7/2$, and $r^*_1/N \to d_1 = e^{-1/2} \approx 0.6065$. The asymptotic probability of selecting the best two is $d_2(2d_1-d_2) \approx 0.2254$.

The $k = 4$ case was apparently solved by Aarni Lehtinen in "Optimal Selection of the Four Best of a Sequence," Mathematical Methods of Operations Research 38, 309-315, 1993. I can't access the paper to see the optimal strategy, but I would assume the structure is similar to the $k=2$ case; one just needs to find the right values of the four $r^*$s. The abstract says the asymptotic probability of selecting the best four is approximately $0.12706$.

Lehtinen also appears to have solved the $k=5$ case and considered the general $k$ case in "Optimal Selection of the $k$ Best of a Sequence with $k$ Stops," Mathematical Methods of Operations Research 46, 251-261, 1997. Again, I can't access the paper, but the abstract says that the asymptotic probability of selecting the best five is approximately $0.104305$. The abstract also says about the case for general $k$, "Using [a] suboptimal solution, we find an approximation for the optimal probability values $P_k$ of the form $$P_k \approx \frac{1}{(e-1)k+1}."$$

It sounds like an exact solution for the general $k$ case is unknown. A search on "$k$-best secretary problem" seems to turn up some additional approximate solutions, although I haven't looked through them all.

share|improve this answer
    
Thank you very much for your very comprehensive reply and for the useful references. –  Jean-Pierre Apr 8 '11 at 18:05
    
@Jean-Pierre: You're welcome. You asked an interesting question that I wanted to know the answers to as well, so I did some digging. :) –  Mike Spivey Apr 8 '11 at 22:59
add comment

The asymptotic solution of getting one of the k best can be found in the paper "On an optimal stopping problem of Gusein-Zade"by A.Frank and S. Samuels in the journal Stochastic Processes and Applications, Vol. 10 (1980). Another highly recommended paper is T.P. Hill, "Knowing When to Stop: how to gamble if you must -the mathematics of optimal stopping", American Scientist, Vol. 97 (2009).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.