Sultan's Dowry
decision/dowry Added material
Problem
Sultan's Dowry A sultan has granted a commoner a chance to marry one of his hundred daughters. The commoner will be presented the daughters one at a time. When a daughter is presented, the commoner will be told the daughter's dowry. The commoner has only one chance to accept or reject each daughter; he cannot return to a previously rejected daughter. The sultan's catch is that the commoner may only marry the daughter with the highest dowry. What is the commoner's best strategy assuming he knows nothing about the distribution of dowries?
Show solution
Solution
Since the commoner knows nothing about the distribution of the dowries,
the best strategy is to wait until a certain number of daughters have
been presented then pick the highest dowry thereafter. 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)).
Working out the math for n=100 and calculating the probability gives:
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 dowry. With this strategy, his odds of choosing the daughter
with the highest dowry are surprisingly high: about 37%.
(cf. F. Mosteller, "Fifty Challenging Problems in Probability with Solutions",
Addison-Wesley, 1965, #47; "Mathematical Plums", edited by Ross Honsberger,
pp. 104-110)
The above formulation of the problem known variously as the
secretary problem or the sultan's dowry problem is flawed.
In particular, we cannot leave completely unspecified the
distribution of the dowries. Suppose that instead of 100 daughters
there are only two. The values of the dowries are two reals drawn
from an arbitrary distribution. It can be shown that even if we
know only one of them, we can determine whether it is higher or
lower than the other, with probability greater than 1/2 (see
decision/high.or.low).
Therefore, we should make the following emendation. Instead of
inspecting the value of the dowry, the suitor is only told how
it ranks with the ones he has previously seen. In fact, he only
needs to know if it is greater than all previous dowries or not,
because the order of previously seen dowries has no effect on
the distribution of the dowries to be seen.
In that case, the usual solution (to skip the first 37 dowries,
then pick the first one after that which is better than all
previous) is correct, and yields a winning probability of about
37 percent.
Almost all solutions of this problem have a flaw as well, in that
they make an explicit assumption which is almost never justified
in the text. This assumption is that (*) the best strategy for the
suitor is to skip some number of dowries, and then choose the next
dowry which is better than all previous. It is not obvious that
this is the case at all. Mosteller apparently does demonstrate
that this is true (thanks to Chris Cole for mentioning this).
Then, quite a while ago, I posted to rec.puzzles the following
extension to the dowry version of the problem:
There's a long line of suitors outside the sultan's palace,
and one by one they come in. If a suitor gets the right girl,
he marries her, as before. Unfortunately (for the suitor, at
least), if he doesn't, he gets his head lopped off, and the
next suitor comes in.
Anyway, the first few dozen guys all know their probability
theory, so they know that the best strategy is to skip the
first 37 girls, and then pick the first girl who is the [better
than all others] up to that point. Alas, each one assumes that
he's the only one who knows that strategy, so one by one, these
few dozen guys get their heads lopped off.
After the 49th head has just rolled down the hill, and the
sultan's vizier has just cried out, "Next!" the next guy in
line says, "This isn't working out. We might all be doing the
same thing. It doesn't hurt any of us to tell the rest what
strategy we'll be using, so that none of us sets out to pick
the same girl over and over again. I might as well just tell
you, though, that I'm going to get her! I know this great
strategy where you skip the first 37 blah blah blah..."
Naturally, a few moments later, head number 50 comes rolling
down.
"Next!" cries the vizier.
Well, suitor number 51 is in a quandary. He's all set to skip
37, etc, etc, except now he knows that's not the right strategy.
But he doesn't know if the last guy skipped the right girl
because she was in the first 37, or if he didn't meet her yet
because he stopped too early.
At this point, I asked, "What is his best strategy?" Now, the
solution I presented had the right flavor:
Skip the first 14. Take the first girl in [15,37] who is better
than the first 14. If there isn't one, take the SECOND girl
in [38,100] who is the best up to that point.
I believe the solution is essentially correct, except for that number
14 (and its neighbor, 15). The strategy essentially tries both
possibilities (that the 50th suitor skipped the right girl, or
that he hadn't got to her yet). I (incorrectly) assumed that the
same 1/e factor would apply to the subdividing the first interval
[1,37], so I calculated [100/(e^2)] = 14. In fact, I have reason
to believe that the answer is actually [100/(e^(3/2))] = 19. (See
below.) Note that this answer is predicated on an assumption of
similar flavor to the basic one (*).
I then said:
Unfortunately, head number 51 rolls down the hill. "Next!"
cries the vizier, who is getting a little hoarse, and wishes
he didn't have this job.
and asked, "What is the next suitor's best strategy?" I then said
the answer to this question was:
Skip the first 5. Take the first girl in [6,14] who is better
than the first 5. If there isn't one, take the SECOND girl in
[15,37] who is the best up to that point. If there isn't one,
take the THIRD girl in [38,100] who is the best up to that point.
And put my foot even further in my mouth. For, even ignoring the
numbers (note that [100/e^3] = 5 is the wrong number here as well),
I also ignored the possibility that there is only one girl in the
second interval which is a best-so-far. (I define a best-so-far to
be a girl whose dowry exceeds all those before her. I will use this
terminology below.) In that case, the best strategy, I believe (*),
is to take the second best-so-far in [38,100]. This error was
pointed out by Jim Waters recently. What I did was neglect the
triple (0,1,2) (see below for the meaning of this). I had already
resolved the error about a year ago, but didn't realize that it was
in the archive that way.
I further speculated that the maximum number of suitors required
to guarantee selection of the best overall was 100, and was equal
to N in general, where N is the number of daughters. I also
conjectured that the Nth suitor's strategy (where N is counted
from the first suitor to share his strategy) is to pick the last
(Nth) daughter. I know this to be true for N equal to 3, 4, and
5, by exhaustive enumeration. I still hold by these speculations.
Now, I will summarize some of the work I've done on this problem
since then.
Most of my work has been on what I call the continuous dowry
problem. Intuitively, the objective in this problem is to select
the "best" number in the interval [0,1] (or whatever interval you
like), where "goodness" is a complete order on this interval.
That is, for any numbers x, y, z in [0,1],
(a) exactly one of the following is true:
(1) x is better than y
(2) y is better than x
(3) x = y
(b) if x is better than y, and y is better than z, then x is
better than z
However, you can't just rephrase this problem in the form of a
question. No, I mean, you can't just rephrase this problem in
terms of a continuous interval.
Why? Recall that the suitor only needs to be told whether or not
each successive dowry is bigger than all previous. So the exchange
with him might go something like this:
"OK, do you want daughter number 1?"
"No, what do you take me for, a common fool?"
"Well, the next best-so-far is daughter number 5. Want her?"
"No. Keep going."
"OK...the next best-so-far is number 12. It's a keeper, you
know it!"
"Uh uh."
"I don't know...there might not be any more. Oops, you're in
luck. Number 25 is a best-so-far. Want her?"
"Not yet."
"Hey, you don't get a second shot. OK, the next best-so-far
is number 43. Geez, I don't know, she looks a bit straggly.
But she's loaded."
"OK, I'll take her."
(shouts aside) "Executioner! Off with his head!"
Uh, yeah, well. Note that the first option offered to the suitor
is daughter number 1, because she is almost by definition the first
best-so-far. Well, what's the first best-so-far in the continuous
interval [0,1]?
So, the problem has to be couched differently. I choose to do it
the following way, using random variables.
PROBLEM 1.
Let b[0] = 1. For all l>0, let the lth best-so-far be a
random variable b[l] that is uniformly distributed in the
interval (0,b[l-1]). We assume that the player does not
know the {b[l]} before making his choice, which he does
as follows. He first picks a number a[0] in the interval
(0,1). Let L = max{l such that b[l] is in (a[0],1)}.
(That is, b[L] is the lowest of the b[l] greater than
a[0]. This avoids the problem of finding the first
best-so-far, and actually pushes the responsibility for
skipping the first infinity or so of best-so-fars onto
the player.)
For all m, 1<=m<=L+1, let a[m] = b[L+1-m]. We disclose
to the player the value of a[1]. He may either
(a) select a[1] for his final choice, or
(b) if a[1]<1, he may reject a[1]
If he rejects a[1], then we disclose to him the value of
a[2], and offer him the same choice. This process continues
with a[3], a[4], and so forth, until he makes a selection.
Since we do not allow him to reject a[L+1] = b[0] = 1, the
process is guaranteed to terminate. The problem is to find
a strategy which maximizes the player's probability of
choosing a[L] = b[1].
The answer to this problem is, I believe, the usual one, in
which the player selects a[0] = 1/e, then chooses a[1]. Then,
I pose the iterated continuous dowry problem. (Dr Thomas
Ferguson of UCLA has studied this problem to some degree,
and as far as he knows, the iterated discrete and continuous
dowry problems are new to the literature.)
PROBLEM 2.
Suppose a player plays the game described in PROBLEM 1, and
loses. A second player then makes an attempt. He is told
the optimal strategy that the first player used, and he is also
told that the first player failed to find b[1]. What
strategy maximizes the second player's probability of
choosing b[1]?
In general, suppose n-1 players have played this game, used
the best strategy in each case, and failed. What strategy
should the nth player use in order to maximize his probability
of winning?
Following our practice of making assumptions analogous to (*), we
claim that the strategy of the second player should be something
of the form:
Choose a[0] to be some positive constant C[2]<1/e. Select
the first a[m] in the interval (C2,1/e). If there is no
such a[m], then select the second a[m] in (1/e,1), since
the first player would have chosen the first a[m].
I haven't looked at Mosteller, so I'm not sure how one would go
about showing that the above is the correct form of the solution.
However, I have shown that given that the above assumption is
correct, the constant C[2] = e^(-3/2). With this strategy, the
second player's winning probability is also equal to e^(-3/2).
In general, the nth player chooses a[0] = C[n], where C[n]<C[n-1],
and the nth player's winning probability is also equal to C[n].
Therefore, the sum over all n of C[n] must be one. Remember that
the C[n] are the endpoints of the intervals, not the lengths of
the intervals, so that this is the case is not obvious. I haven't
proven this in the general case, but I believe it to be true.
(Read, "I'm more confident about this than I should have been
about my first archive entry.")
(So, back in the iterated discrete version, I basically claimed
(thoughtlessly) that C[2] = e^(-2). This turns out not to be the
case.)
The basic method of attack is to enumerate the possible ways that
the nth player might win, and then calculate the probability of
winning by each one of those ways. It turns out that the strategy
of the nth player can be represented as a set of n-tuples. For
instance, the strategies of the first three players are:
{(1)}
{(1,0), (0,2)}
{(1,0,0), (0,2,0), (0,1,2), (0,0,3)}
The first player's strategy is to skip an interval (of a size which
is later determined to be 1/e), then take the first best-so-far
afterward. This is the 1-tuple (1).
If the first player loses, the second player's strategy is to skip a
smaller interval (of a size which I believe to be e^(-3/2), not e^(-2),
as claimed in the previous version of the archive entry. He then
takes the first best-so-far between e^(-3/2) and 1/e (this is
the tuple (1,0)). If there is none, then he takes the second best
in [1/e, 1] (tuple (0,2)).
If the second player loses, the third player's strategy is to skip a
still smaller interval (which I determine to be e^(-47/24). He
then takes the first best-so-far in [e^(-47/24), e^(-3/2)] (tuple
(1,0,0)). If there is none, he takes the second best-so-far in
[e^(-3/2), 1/e] (tuple (0,2,0)). If there is only one best-so-far
in that interval, he takes the second best-so-far in [1/e, 1] (tuple
(0,1,2) aha!). If there were no best-so-fars in [e^(-3/2), 1/e], he
takes the third best so far in [1/e, 1] (tuple (0,0,3)).
Note how these strategies are represented. If a tuple represents the
actual number of best-so-fars in the given intervals, then the player
wins. If, on the other hand, the tuple is "less than" the actual
number of best-so-fars (in other words, he has not reached the best
overall), then the player loses. The probability that the player wins,
then, is just the sum of the probabilities associated with each n-tuple
in his strategy.
But what about the C[n]? There's no mention of them in this. Well,
the probability associated with each tuple is dependent on the values
of the C[n]. Fortunately, for each player number n, there is only
one tuple in the strategy which contains an entry (which is always
1) for the interval (C[n],C[n-1]). This makes it quite easy to
compute the optimal C[n].
Unfortunately, I don't have a closed form expression for C[n]. I'm
working on it. I do have the values of the first five C[n]. Their
natural logs are, respectively,
-1, -3/2, -47/24, -2761/1152, -4162637/1474560
If anyone has any insights on this problem, I'd be happy to discuss
them.
======end text======
byron elbows
brian@isi.edu
http://info.broker.isi.edu/brian/
byron elbows' two rules of human nature:
* No one is as weird as they think they are.
* Everyone is weirder than others think they are.
Additional material
[ Editor: a November 1997 rec.puzzles thread "Highest in deck of random
numbers" on the second suitor of the iterated problem above. Brian
Tung's own August 1995 posting "dowry problem redux", also in the
collected material, is the earlier form of his text above and is not
repeated. ]
Someone writes random numbers on a deck of N cards and turns them face
down. An astute rec.puzzles subscriber (#1) is asked to turn them over
one at a time and select the highest one in the deck. Once he goes
beyond a given card he cannot go back to a previous card. You do not
observe this, but are told that he failed to select the highest card.
The cards are left in their original order. You are next.
You are certain that #1 observed the first N/e cards (36.79%) and
picked the first card beyond them (if any) that is the highest-so-far
(HSF). You know that this approach did not work in this case. What is
your strategy?
DISCUSSION
This was a subject in a recent string. I have changed locations and
managed to misplace my hard copies. I believe that one person posted
the solution that you (#2) should observe the first e^-(3/2) or about
22.31% of the cards in the deck. Then if you find an HSF between
#.2231N and #.3679N you should select it. If none exists, you should
then pick the 2nd HSF above #N/e, because you know that picking the
first HSF failed.
I agree with this general thinking, but I believe that your initial
cut-off should be 19.55% of the deck instead of 22.31%. Here's my
reasoning and calculations:
KNOWLEDGE FROM #1'S FAILURE
You know that #1's strategy should succeed 1/e (36.79%) of the time
Given c as the cutoff for the initial observations, one will succeed
with a probability of -c*ln(c) [Editor: "c*ln(c)" in the original].
[If you want to verify this, recall that the sum to infinity of x +
x^2/2 + x^3/3 + etc. (x<1) is -ln[1/(1-x)] and that the derivative of
n*ln(n) is 1+ln(n).]
#1 failed for one of two reasons:
(1) The highest card was in the 0-#N/e (36.79%) range, or
(2) The first HSF (highest-so-far) above this point (if any) was not
the highest card.
Looking at (2), there was an original probability that there was only
one card in the N/e to N range higher that the highest before #N/e.
This probability is (1/e)*(1-1/e) = 1/e - 1/e^2 = 23.25%. Subtracting
this from the 36.79% (1/e) for overall success rate leaves 1/e^2
(13.53%) that #1's strategy would work if there were more than one HSF
beyond #N/e and that it happened to be the first such card.
If there is more than one card higher than the highest in the N/e to N
group, there is an equal probability that it is the 2nd HSF as the 1st
HSF. Thus, the 2nd HSF has an original probability of 1/e^2 of being
the highest.
Let's look at your probabilities, remembering that #1's strategy
failed, meaning that only 1-1/e (63.21%) of the possible arrangements of
the deck remain. Dividing possibilities (1) and (2) by this amount
gives the following:
(1) The probability that the highest is in the 0-N/e portion is
1/(e-1) or 58.20%
(2) The probability that the 2nd HSF beyond this point is the
highest is 1/[e(e-1)] or 21.41%
YOUR STRATEGY
Armed with this knowledge, what do you do, knowing that the highest
card is probably in the 0-N/e range but, if not, it is not the first
HSF above that range?
(1) You will observe (not pick) the first r% of the cards in the 0
to N/e range. If you then find a HSF in the r*N to N/e range,
you will select it. Unless you later find a higher card in this
range (you lose)
(2) You will select the 2nd HSF above card #N/e.
Regarding (1), the probability that you will get the highest in the
0-N/e range is -r*ln(r). The probability that this is the highest in
the deck is .5820 * r*-ln(r) or [r*-ln(r)]/[e-1].
Regarding (2), you may not select from the #r*N to N/e group because
the highest in the 0 to N/e group appears before you get to the #r*N
card. This probability is r. Then you must hope that the highest is
2nd HSF after the #N/e card. The probability of winning is 1/e^2
(.1353) divided by .6321 (1-1/e), which is 1/[e(e-1)] or .2141. Thus,
the total probability of succeeding from (2) is r*.2141.
Combining (1) and (2), I got this formula for the probability of
success (P)
P= r/[e(e-1)] - r*ln(r)/(e-1) = [1/(e-1)] * [r/e - r*ln(r)]
Differentiating, I got f'(r) = [1/(e-1)] * [1/e -1 - ln(r)]. This
gives at 0, ln(r) = 1/e - 1.
This sets r at .5314636. Then r * N/e = .1955145*N is the optimum
number of cards to be observed before your selecting. This is
e^-(2-1/e).
Your probability of success is .5314636/(e-1) = .30929944, given that
#1 failed.
I must acknowledge that this runs counter-intuitive in that #2, given
the knowledge of #1's failure, has a smaller chance than if #2 asked for
the deck to be reshuffled before coming to the table!
BTW, according to my calculations, selecting e-(3/2) as the initial
cut-off for #2 yields a probability of success of .30635.
-- Bill Ryan <billryan22@aol.com> (15 November 1997)
[ Editor: Ryan's second posting, of 23 November 1997 (also sent by mail
to Chris Cole), quoted the above and Tim Firman's objection to it: ]
(The original posting made generous use of terms such as N/e, which is
a close approximation for large decks, but not exact.)
>>One person (Monwhea Jeng) posted the solution that you (#2) should
>>observe the first e^-(3/2) or about 22.31% of the cards in the deck.
BTW, the archive solution is to observe the first 13.53%, then proceed
as above. This group is not lacking for solutions!
Tim commented:
>That's only true if there are exactly two cards in N/e to N higher
>than any in 1-N/e.
>Here's where there's a problem. What if there are three cards in the
>range [38-100] which are higher than the 1 to N/e group?
>For the case of 3 higher, there are 6 orders they can fall:
> There is a 1/3 probability the Highest Overall(HOA) is the first
> HSF.
> (HOA, 2nd HOA, 3rd HOA) or (HOA, 3rd, 2nd)
> a 1/2 probability HOA is the second HSF
> (2nd, 3rd, HOA) or (3rd, HOA, 2nd) or (2nd, HOA, 3rd)
> and a 1/6 probability 3 is the third HSF
> (3rd, 2nd, HOA)
My reply to Tim's comments:
I still think that my original posting was correct. Here are two
reasons:
(1) If the three highest cards are in the N/e to N group, separate
them from the deck face down. Any one of the three has an equal
probability of being the HOA, regardless of what strategy you have for
selecting one of them.
(2) Your example includes (2nd, 3rd, HOA) in the second HSF group. It
belongs in the third, resulting in equal probabilities of 1/3 for all
three cards.
The same applies to four or more in the N/e to N group. Separate the
high ones and they all have an equal probability of being HOA,
regardless of your strategy for selecting one of them.
Thus, IF there are two or more of the highest cards in the N/e to N
group, the probability that the HOA is the 2nd is the same as it is of
being the first.
If my posted solution is incorrect, it would have to be for a different
reason.
ABOUT THE ARCHIVE SOLUTION
I agree with Tim's statement that the archive solution does not
adequately consider the possibility that the 2nd HSF in the N/e to N
group could be the HOA, meaning that the cutoff for the initial
observations must be higher than 1/e^2.
Monwhea Jeng just posted a solution of e-(3/2) as the cutoff for the
initial observations, but did not describe how it was determined. I do
not agree with it, but it would be nice to see why it conflicts with my
solution
Again, comments are appreciated. If nothing else, we ought to get this
straightened out for the archives.
-- Bill Ryan (23 November 1997)
Hi everyone. I don't often get a chance to read rec.puzzles anymore,
and Bill Ryan was kind enough to let me know that there was discussion
on my archive entry on the Sultan's Dowry problem.
I thought I had better try to clear up some misconceptions.
Bill wrote:
> One person (Monwhea Jeng) posted the solution that you (#2) should
> observe the first e^-(3/2) or about 22.31% of the cards in the deck.
> Then if you find an HSF between #.2231N and #.3679N you should select
> it. If none exists, you should then pick the 2nd HSF above #N/e,
> because you know that picking the first HSF failed.
This was actually my solution, which Monwhea quoted.
> BTW, the archive solution is to observe the first 13.53%, then
> proceed as above. This group is not lacking for solutions!
This was also me (!). It's possible that you didn't read far enough in
the archive entry, for I say quite a few times that I screwed up in
giving that initial answer.
It's been a while since I've looked at this problem, so I don't recall
many of the things that were much clearer when I was involved in the
plot. But let me see if I can't recreate some of that context and
resolve this discrepancy.
To begin with, this isn't quite the problem I looked at. I looked at
the *continuous* version of this problem, which is defined in the
archive entry. Nevertheless, it should still yield the same answer
asymptotically.
Essentially, my approch to this problem was not to look at a reduced
problem space, but to examine which initial configurations lead to wins
for the second player.
Consider the distribution of the best-so-fars. The best overall is
clearly uniformly distributed between 0 and 1 (considering that to be
the index into the "deck").
The bit of insight here is that the next best-so-far (the one that
comes before the best overall) is uniformly distributed between 0 and
the best overall. And the one before that is uniformly distributed
between 0 and that. And so forth.
The first player's strategy wins if there is exactly one best-so-far in
the interval [c_1, 1], where c_1 is the first player's cut-off value.
The winning probability is then
W_1 = integral[x=c_1, 1] (c_1/x) dx
= -c_1 ln c_1
which is maximized at c_1 = 1/e, yielding a winning probability which
is also W_1 = 1/e. Curious. Presumably we all agree on this answer.
Now, the second player's strategy. He has another cut-off value
c_2 < c_1. He wins in two different situations:
a. There are no best-so-fars in [c_1, 1], and exactly one
best-so-far in [c_2, c_1]. (In other words, the first player
lost because he already passed the best overall.)
b. There are exactly two best-so-fars in [c_1, 1], and no
best-so-fars in [c_2, c_1]. (In other words, the first player
lost because he picked too early.)
Call the second player's winning probability in these two cases W_2,a
and W_2,b. W_2,a can be determined as W_1 was:
W_2,a = integral[x=c_2, c_1] (c_2/x) dx
= -c_2 - c_2 ln c_2
W_2,b is a bit more complicated--it involves a double integral which I
won't repeat here--but it too can be computed and gives simply
W_2,b = c_2/2
The overall winning probability for the second player is
W_2 = W_2,a + W_2,b
= -c_2/2 - c_2 ln c_2
This is maximized at c_2 = exp(-3/2). For further details and a more
general treatment, please see http://gost.isi.edu/brian/puzzles/ and
look for the dowry problem (it's long, you can't miss it). In
particular, there ought to be a link to a PostScript file with a more
formal exposition (although still not up to theory scratch). You'll
note that by my calculations, W_j = c_j for each j that I calculated
the answer for, a nice bit of symmetry that I find strangely
satisfying.
I hope this clears matters up somewhat. If someone would like to do a
simulation (and post the code, please), I'm sure that would help
matters even further. And if anyone has a closed-form expression for
the optimal c_j, that would be fantastic!
-- Brian Tung <brian@isi.edu> (25 November 1997)
I wrote:
> W_2,b is a bit more complicated--it involves a double integral which
> I won't repeat here--but it too can be computed and gives simply
>
> W_2,b = c_2/2
It occurs to me that I ought to give this integral, because it's
probably the source of the conflict.
The proper integral for this value is
W_2,b = integral[x_1=c_1, 1] integral[x_2=c_1, x_1] (c_2/x_2) dx_2
(dx_1/x_1)
That last term is vital! It is very easy to slip up and write simply
dx_1 instead of (dx_1/x_1). The reason that you must add in the extra
(1/x_1) factor is that x_2, the best-so-far immediately preceding the
best overall, cannot range freely from 0 to 1. It can only occupy the
range [0, x_1]. Thus its density function is expressed by the value
(1/x_1) in that interval, 0 outside it.
In particular, if you don't add that factor in there, you get an
expression which is maximized at c_2 = exp(-(2-1/e)) [Editor:
"exp(2-1/e)" in the original] = 0.1955, which I believe is what Bill
Ryan got.
The way I arrived at the above integral is highly ad hoc. The
PostScript notes I refer to above contain a more systematic way of
arriving at the integral, and a more-or-less closed form solution for
the probability associated with a given winning configuration. (The
general question of the winning probability for a given player still,
alas, lacks a closed-form solution.)
-- Brian Tung (25 November 1997)
[ Editor: for the version in which the suitor knows the distribution
of the dowries, see decision/dowry.known.distribution. ]
[ Editor: three pages of notes on the dowry problem, in the TODO
collection as dowry.ps. No author is named in the file; they appear to
be the "PostScript file with a more formal exposition" that Brian Tung
mentions in his November 1997 postings above, since they use his
notation and give his values. The formulas are put into plain text:
x^k for powers, ln for the natural logarithm, prod and sum for the
product and sum signs, and [a, b) etc. for intervals. Passages that
repeat the entry verbatim are replaced by a note. ]
What follows are my notes on this problem. Because they are *my*
notes, they are somewhat sketchy, and things that I believe are true
are often left out of the exposition for brevity's sake. Please
forgive.
1 Introduction
Problem 1 [ Editor: the sultan and his hundred daughters, word for
word as in decision/dowry.p. ]
This is a typical formulation of the problem known variously as the
Sultan's Dowry problem or the secretary problem. As stated, it is
flawed. In particular, we must say something about the distribution
of dowries. Suppose that there are two reals written on two slips of
paper (these represent the values of the dowries). A player is shown
one of the reals. It is well-known that even with an arbitrary
distribution of numbers, the player can identify whether this real is
higher or lower than the other with a probability greater than 1/2.
We suggest casting the problem in the following more precise (albeit
less entertaining) version.
Problem 2 On a table in front of you are N = 100 slips of paper,
labeled on the back "1," "2," "3," ..., scrambled in a random order.
Your object is to select the slip with "100" written on it. I allow
you to make your selection in the following manner. I will look at
the number on the first slip (without disclosing it to you). You may
select this slip, or reject it forever.
If you reject it, I will look at the number on the second slip
(without disclosing it to you), and tell you only whether this second
number is greater or less than the first number. You may now select
this second slip, or reject it forever, too.
Each time you reject a slip, I will look at the number on the next
slip, and tell you only how it ranks with the previous numbers. At
that time, you may either select that slip, or reject it and go on to
the next one. What strategy should you use to maximize your
probability of selecting the slip with "100" written on it?
In this formulation, it can be shown that the best strategy is to skip
the first N/e = 37 slips of paper, then select the next slip of paper
with a number higher than all previous. This is easy to show,
assuming that the best strategy is of the form, "Skip the first k,
then select the next one better than all previous." In fact, most
demonstrations of this fact neglect to show this assumption holds,
when it is far from self-evident.
[Need to show how to prove this.]
In the next section, we will formulate a continuous version of this
problem, and show how to solve it.
2 Statement of the Problem
Problem 3 [ Editor: the continuous problem, as PROBLEM 1 in Brian
Tung's text above (b_0 = 1, each best-so-far b_l uniform on
(0, b_(l-1)), the player picks a_0 and is shown a_1, a_2, ... in
turn), with K in place of L; the aim is to choose a_K = b_1. ]
We may also consider the iterated continuous suitor problem, in which
there is an infinite sequence of players. Each succeeding player knows
only the strategies of the previous players, and (of course) that each
previous player failed to find the value b_1.
Define the interval I_1 = [x_1, 1). Also define intervals I_2, I_3,
..., by
I_k = [ prod(j=1..k) x_j, prod(j=1..k-1) x_j )
so that I_2 = [x_1 x_2, x_1), I_3 = [x_1 x_2 x_3, x_1 x_2), and so
forth.
Define a *strategy* to be a set of m n-tuples P = {p_1, p_2, ..., p_m}
where
p_i = (p_(i,n), p_(i,n-1), ..., p_(i,1))
A player with strategy P examines values, starting with a_0 = inf(I_n),
and continues examining them until there exists a tuple
(p_(i,n), p_(i,n-1), ..., p_(i,1)) in P such that
1. p_(i,j) = 0 for all j less than some k
2. it has been verified that there are exactly p_(i,j)
best-so-fars in I_j for all j greater than k
3. it has been verified that there are at least p_(i,k)
best-so-fars in I_k
In that case, the player selects the p_(i,k)th best-so-far in I_k. The
solution to this problem thus requires two components:
1. an explicit description of the nth player's strategy
2. the probabilities yielded by these strategies, which will
determine the optimal values for x_1, x_2, ...
3 Solution
3.1 Strategies
Inspection of the problem quickly produces a heuristic for listing the
strategies for the nth player. Clearly, the first player's strategy
is simply the singleton {(1)}. Thereafter, the nth player's strategy
is always a set of n-tuples. It can be computed in terms of the
n-1th player's strategy in the following manner. Let P_n denote the
nth player's strategy. Then
P_n = {(1, 0, ..., 0)} union
{(0, ..., 0, p_k + 1, p_(k-1), ..., p_1) :
(0, ..., 0, p_k, p_(k-1), ..., p_1) in P_(n-1)}
where the first set of 0's has n-k entries and the second n-1-k.
Therefore, we have
P_2 = {(1,0), (0,2)}
P_3 = {(1,0,0), (0,2,0), (0,1,2), (0,0,3)}
and so forth.
3.2 Probabilities of Tuples
The probability that a player with strategy P wins (selects the value
b_1) is the probability that there exists a tuple (p_n, p_(n-1), ...,
p_1) in P such that there are exactly p_k best-so-fars in I_k for all
k, 1 <= k <= n. It therefore remains for us to determine the
probability of a given tuple. We claim (for the time being without
proof) that this probability is given by
prod(k=1..n) x_k integral(z_1=x_k..1) integral(z_2=x_k..z_1) ...
integral(z_(p_k)=x_k..z_(p_k - 1))
dz_(p_k)/z_(p_k) ... dz_2/z_2 dz_1/z_1
This can quickly be simplified to
prod(k=1..n) x_k (-ln x_k)^(p_k) / p_k!
In the case of the first player, the probability of winning is simply
the probability of the "tuple" (1). According to the above expression,
this probability is -x_1 ln x_1, which has a maximum at x_1 = e^(-1),
yielding a probability of e^(-1).
For succeeding players, note that there is only one strategy with a
leading 1; all others have at least one leading 0. In other words,
knowing x_k for all k < n quickly gives us x_n. Canceling out the term
x_1 x_2 ... x_n from the above expression gives us
1 + ln x_n = - sum over (p_n, p_(n-1), ..., p_1) in
P_n - (1,0,...,0) of
prod(k=1..n-1) (-ln x_k)^(p_k) / p_k!
or if we define y_n = -ln x_n, we have
y_n = 1 - sum over (p_n, p_(n-1), ..., p_1) in P_n - (1,0,...,0) of
prod(k=1..n-1) y_k^(p_k) / p_k!
The probability of winning for the nth player is
prod(k=1..n) x_k = e^(-sum(k=1..n) y_k). For the first five players,
we have
x_1 = exp(-1)
x_1 x_2 = exp(-3/2)
x_1 x_2 x_3 = exp(-47/24)
x_1 x_2 x_3 x_4 = exp(-2761/1152)
x_1 x_2 x_3 x_4 x_5 = exp(-4162637/1474560)
[ Editor: the notes end here. ]