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

Fatal Error:

lib/CachedMarkup.php (In template 'browse' < 'body' < 'html'):257: Error: Pure virtual



Fatal PhpWiki Error

lib/CachedMarkup.php (In template 'browse' < 'body' < 'html'):257: Error: Pure virtual