The sultan's dowry problem asks for an optimal selection strategy in the following scenario. A sultan has granted a commoner a chance to marry one of his 
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 the dowries are distinct
and the daughters are presented in a uniformly random order, but he knows nothing
else about the dowries (Mosteller 1987)?
The optimal strategy rejects the first 
daughters and then selects the first subsequent daughter whose
dowry exceeds every dowry seen so far (Havil 2003, p. 134). For 
and 
, the probability
of selecting the maximum dowry is
 |
(1)
|
where 
is a harmonic number (Havil 2003, p. 135).
For 
,
the first daughter is selected and 
. The probability
is illustrated above as a function of 
and as a surface in 
and 
.
For 
,
the difference between successive probabilities is
 |
(2)
|
Thus, for 
,
an optimal cutoff is the smallest positive integer 
such that
 |
(3)
|
For 
,
the cutoff is 0. At 
, cutoffs 0 and 1 tie, and the convention here selects 1.
Solving
 |
(4)
|
for real 
and taking ![max(1,[x])](/images/equations/SultansDowryProblem/Inline17.svg)
,
where ![[x]](/images/equations/SultansDowryProblem/Inline18.svg)
is the ceiling function, gives the cutoffs for
.
For 
,
2, ..., the cutoffs are 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, ... (OEIS A054404).
The listed convergents for the continued fraction of 
,
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),
give pairs 
with an optimal cutoff 
for 
daughters (Havil 2003, p. 137).
An approximate solution can be obtained by using a series expansion for 
about infinity,
 |
(5)
|
where 
is the Euler-Mascheroni constant, and
using it for 
and 
in (1), giving
 |
(6)
|
This can be solved in closed form to give an approximate solution to 
,
 |
(7)
|
where 
is the principal branch of the Lambert
W-function. This expression is real for integers 
. It approximates the continuous
threshold, and rounding it up is not a substitute for the exact harmonic
number inequality.
Another approximation can be obtained by taking a series expansion of 
to obtain
 |
(8)
|
Taking the derivative and setting equal to 0 then gives
![x^^_2=ne^(-[1+1/(2n)]),](/images/equations/SultansDowryProblem/NumberedEquation9.svg) |
(9)
|
which approximates the continuous maximizer of 
.
Both approximations have series expansions of the form
 |
(10)
|
where 
and 
are small constants.
The problem is most commonly stated with 
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 
(Honsberger 1979, pp. 104-110; Mosteller 1987; Havil
2003, p. 136). As the number of daughters increases, this tends towards 
(OEIS A068985).
