==> decision/dowry.s <==
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)

Here's a twist on the sultan's dowry problem I hope hasn't been posted yet.
I became interested in an iterated version of this problem, which goes as
follows:

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

QUESTION 1: What is his best strategy?

ANSWER 1: His best strategy is:

    "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."

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.

QUESTION 2: What is suitor number 52's best strategy?

ANSWER 2: His best strategy is:

    "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."

By the end of the day, of course, a wedding will be set, won't it?

MORE QUESTIONS: If each suitor uses the best strategy at that point, how
    many suitors will it take before the right girl is certain to be found?
    Does each succeeding suitor always have a better chance of winning
    than the preceding one?
    
SPECULATION: The last strategy is "Pick the last girl."  Its probability
    of success is 1.  And it is strategy number 100.  (The corresponding
    conditions hold for 3, 4, and 5 daughters.)

Does anyone have any observations on this one?

byron elbows
(mail to brian@cs.ucla.edu)