TOPICS
Search

Sultan's Dowry Problem


A sultan has granted a commoner a chance to marry one of his n daughters. The commoner will be presented with the daughters one at a time and, when each daughter is presented, the commoner will be told the daughter's dowry (which is fixed in advance). Upon being presented with a daughter, the commoner must immediately decide whether to accept or reject her (he is not allowed to return to a previously rejected daughter). However, the sultan will allow the marriage to take place only if the commoner picks the daughter with the overall highest dowry. Then what is the commoner's best strategy, assuming he knows nothing about the distribution of dowries (Mosteller 1987)?

SultansDowryProblem

Since the commoner knows nothing about the distribution of the dowries, the best strategy is to wait until a certain number x of daughters have been presented, then pick the highest dowry thereafter (Havil 2003, p. 134). The exact number to skip is determined by the condition that the odds that the highest dowry has already been seen is just greater than the odds that it remains to be seen and that if it is seen it will be picked. This amounts to finding the smallest x such that

 x/n>=x/n(1/(x+1)+...+1/n).
(1)

More specifically, the probability of obtaining the maximum dowry after waiting for x out of n daughters is

 P(n,x)=(1+x(H_(n-1)-H_x))/n,
(2)

where H_n is a harmonic number (Havil 2003, p. 137), plotted above for a number of specific values of n as a function of x (left figure above) and as a surface plot in n and x (right figure).

The solution is therefore the smallest x such that

 H_x>=H_n-1.
(3)

Solving,

 H_x=H_n-1
(4)

numerically and taking the ceiling function [x] then gives the solutions 0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, ... (OEIS A054404) for n=1, 2, ... daughters.

Surprisingly, the convergents for the continued fraction of 1/e, given by 0, 1/2, 1/3, 3/8, 4/11, 7/19, 32/87, 39/106, 71/193, 465/1264, ... (OEIS A007676 and A007677), correspond exactly to pairs (x,n), where x is the optimal value for n daughters (Havil 2003, p. 137).

An approximate solution can be obtained by using a series expansion for H_x about infinity,

 H_x∼gamma+1/(2x)+...+lnx,
(5)

where gamma is the Euler-Mascheroni constant, and plugging this approximation into (4), giving

 1/(2x)+lnx=1/(2n)+lnn-1.
(6)

This can be solved in closed form to give an approximate solution to x,

 x^^_1=-1/(2W(-(e^(1-1/(2n)))/(2n))),
(7)

where W(x) is the Lambert W-function. In fact, taking [x^^_1] gives the correct result for n>3.

Another approximation can be obtained by taking a series expansion of P(n,x) to obtain

 P(n,x) approx (n-r+2rnln(n/r))/(2n^2).
(8)

Taking the derivative and setting equal to 0 then gives

 x^^_2=ne^(-[1+1/(2n)]),
(9)

which is within 1 of the correct answer for all n.

SultansDowryApproximations

The plot above illustrates these two approximations (red and blue curves) together with the actual values (black dots). Both approximations have series expansions of the form

 x^^∼a_0+n/e+(a_(-1))/n+...,
(10)

where a_0 and a_(-1) are small constants.

The problem is most commonly stated with n=100 daughters, which gives the result that the commoner should wait until he has seen 37 of the daughters, then pick the first daughter with a dowry that is bigger than any preceding one. With this strategy, his odds of choosing the daughter with the highest dowry are surprisingly high: about 37.10% (Honsberger 1979, pp. 104-110, Mosteller 1987; Havil 2003, p. 136). As the number of daughters increases, this tends towards 1/e approx 36.787...% (OEIS A068985).


See also

Birthday Problem

Explore with Wolfram|Alpha

References

Havil, J. "Optimal Choice." §13.13 in Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 34-138, 2003.Honsberger, R. "Some Surprises in Probability." Ch. 5 in Mathematical Plums (Ed. R. Honsberger). Washington, DC: Math. Assoc. Amer., pp. 104-110, 1979.Mosteller, F. "Choosing the Largest Dowry." Problem 47 in Fifty Challenging Problems in Probability with Solutions. New York: Dover, pp. 73-77, 1987.Sloane, N. J. A. Sequences A007676/M0869, A007677/M2343, A054404 and A068985 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Sultan's Dowry Problem

Cite this as:

Weisstein, Eric W. "Sultan's Dowry Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SultansDowryProblem.html

Subject classifications