Generalization of the Sultan's dowry problem

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?

-
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
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
@joriki: The paragraph at Wikipedia just before TOC mentions 'the $n/e$ solution' and doesn't qualify it or attach any asterisk or strings to it. I vaguely recall this as being given in '50 Challenges in Probability' by Mosteller. I am beginning to think that maybe it is Mathworld's that is an approximation to the answer? – Vandermonde May 11 at 23:25
Oh, but down there in the actual solution, Wikipedia then passes from the solution to an approximation thereof. And Mathworld seems sound here. If this understanding is correct, that feels dirty and I feel cheated that Wiki initially advertised theirs as exact. I've got to track down Masteller's book now; I'm dying (a little) (to know) (on the) inside. – Vandermonde May 11 at 23:33

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.

-
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

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).

-