DOWRY

[Prime]

This is a bit more difficult probability puzzle. Old classics, fun to solve, if you haven’t encountered a similar problem before.

As a young aspiring Chief Statistician at the King’s Court, you are presented with this challenge. You must select a bride with the largest dowry. (Being married is a requirement for the Chief Statistician position.) Wherefore, you must choose from 100 equally beautiful young females with a weakness for only the smartest of statisticians, where each bride’s family offers a different dowry. The $ amount of each dowry is written on the backside of the girl’s personal card. Those amounts are presented to you one at a time in random order. When an amount is presented to you, you may either reject it, or settle for it. When you reject a dowry, you are presented the next card. If you fail to choose the dowry, which is the largest among 100, then you loose both your chance for the Court position and your right to claim your bride.

What strategy can you develop to maximize your chance for the position and the wealthy bride? What is the best chance?

(Obviously, the dowries are presented to you just once -- no chance of going back to the amount you’ve rejected. The range of the dowries is unknown.)

[bushindo]

Okay, second time is the charm,

[bushindo]

Here's an approach,

The general strategy to determine a number N beforehand. During the game, the statistician should to look at the first N girls' cards and note the maximum dowry value among the N cards. We shall denote this maximum dowry value as M.

Having done this, the statistician should then look at the remaining (100-N) girls, and choose the first girl that has a dowry value larger than M.

The probability of winning using this strategy is
(100 - N)*N/[ 100 * 99]

Using derivatives, it is straightforward to see that the optimal choice for N is 50. So the optimal winning chance is (1/2)*(50/99)

[vistaptb]

First, reject the dowries of 1/e of the brides (.37 or 37 of them), then accept the next dowry that is larger than all the dowries you just rejected. I can't remember what the probability of success is, though. Could someone help out here?

[Prime]

First, reject the dowries of 1/e of the brides (.37 or 37 of them), then accept the next dowry that is larger than all the dowries you just rejected. I can't remember what the probability of success is, though. Could someone help out here?

I did stipulate that it would be fun to solve if you haven't encountered a similar problem before. If you remember seeing such problem but have forgotten the solution (as seems to be the case,) it could be fun to derive and prove it over again.

[bushindo]

Here's an approach,

The general strategy to determine a number N beforehand. During the game, the statistician should to look at the first N girls' cards and note the maximum dowry value among the N cards. We shall denote this maximum dowry value as M.

Having done this, the statistician should then look at the remaining (100-N) girls, and choose the first girl that has a dowry value larger than M.

The probability of winning using this strategy is

(100 - N)*N/[ 100 * 99]

Using derivatives, it is straightforward to see that the optimal choice for N is 50. So the optimal winning chance is (1/2)*(50/99)

Forgot about some cases in computation of winning chance. Back to the drawing board.

[Caliban27]

I modelled the problem by numbering the girls 1 to 100, then generated a random dowry between $500 and $1,000. I then calculated a progressive mean which, as expected, approached closer and closer to $750. I then calculated a progressive Standard Deviation which very quickly dropped below $150 and then slowly approached $133. The simple formula might then be to accept the dowry which is greater than AVG + 2 x STDDEV. However, I found that this hurdle was more often over $1,000 and therefore no dowry passed the hurdle. Trial and error found AVG + 1.7 x STDDEV usually produced acceptance of the greatest dowry. However, my stats capability does not allow me to calculate the best value for the multiple of STDDEV, nor the resultant probability of success. Graph from XLS

Dowry model.pdfattached.

[Prime]

I modelled the problem by numbering the girls 1 to 100, then generated a random dowry between $500 and $1,000. I then calculated a progressive mean which, as expected, approached closer and closer to $750. I then calculated a progressive Standard Deviation which very quickly dropped below $150 and then slowly approached $133. The simple formula might then be to accept the dowry which is greater than AVG + 2 x STDDEV. However, I found that this hurdle was more often over $1,000 and therefore no dowry passed the hurdle. Trial and error found AVG + 1.7 x STDDEV usually produced acceptance of the greatest dowry. However, my stats capability does not allow me to calculate the best value for the multiple of STDDEV, nor the resultant probability of success. Graph from XLS

Dowry model.pdfattached.

The range of dowry amounts is unknown. There is no average, no deviation.

[bonanova]

This puzzle asks for the strategy that maximizes the likelihood of choosing the babe with the greatest dowry.

Real-life situations often ask for the strategy that yields the best result, on average - best result or not.

Clearly a strategy that on average gets you into the top ten percent of the dowries would be preferred over

one has a better shot at picking the highest dowry but on average gets you only into the top twenty percent.

That said, and if someone has written the simulation for this puzzle, I wonder where the OP best strategy

places you in the distribution, on average. And, is there a strategy that places you higher?

A good sample set of dowries to find out would be simply 1, 2, 3, ... , 98, 99, 100. Run the algorithm

100,000 times without using knowledge of the distribution, and average the value of the result.

[Rainman]

If we accept the first dowry, we always have 0.01 chance of success. To get >0.01 chance of success, we must reject the first dowry no matter how large it is. Now that we have seen and rejected a dowry, it would be auto-fail to accept a dowry unless it is larger than every dowry we have already rejected. Whenever we are offered a dowry that is larger than all previous dowries, we could choose to accept. If we accept, we have n/100 chance of success, where n is the number of dowries seen, including the one we accepted. To summarize:

• We should reject the first dowry.
• We should never accept a dowry unless it is larger than every dowry we have seen before.
• When we do accept, our chance of success depends only on total number of dowries seen.

With this in mind, I propose this strategy: start by seeing and rejecting K dowries, K being at least 1 and at most 99, then accept the first one that is larger than each of those. Now we need to find the chance of success for this strategy. We could succeed by correctly accepting the nth dowry, for any n from K+1 to 100. So our total chance of success is the sum of the chances of correctly accepting the nth dowry, for all n from K+1 to 100.

Note that our chance of refusing a dowry is K/(K+1), i.e. the chance that it is not larger than all of the K dowries we started by rejecting. Let x=K/(K+1) for simplicity.

P(correctly accepting dowry #K+1) = 0.01

P(correctly accepting dowry #K+2) = 0.01*P(refusing dowry #K+1) = 0.01*x

P(correctly accepting dowry #K+3) = 0.01*P(refusing dowries #K+1 and #K+2) = 0.01*x²

^...

P(correctly accepting dowry #100) = 0.01*P(refusing dowries #K+1 through #99) = 0.01*x^99-K

This is a geometric sequence, the sum of which is P(success) = (0.01-0.01*x^100-K)/(1-x) = (0.01-0.01*(K/(K+1))^100-K)*(K+1).

Now to maximize this with respect to K, anyone in the mood for some differentiation?

I threw some numbers into my computer calculator instead.

K = 37 yields P(success) = 0.3092

K = 44 yields P(success) = 0.3222

K = 45 yields P(success) = 0.3227

K = 46 yields P(success) = 0.3229

K = 47 yields P(success) = 0.3227

K = 48 yields P(success) = 0.3223

K = 55 yields P(success) = 0.3111

It seems the optimal strategy is to reject the first 46 dowries, then accept the first dowry that is larger than each of those.

[phaze]

Do the girls know the number written on their card? Do they know the number written on any other card (like those standing beside them)?

[Prime]

Okay, second time is the charm,

puzzle.png

That is a neat solution! Mine is a lot messier than that. The formulas could use some explaining... On the other hand, there is still a little bit of puzzle left for those who can’t invest a lot of time into solving this problem from scratch. Check out the two equations by Bushindo and figure out the precise reasoning for their construction. (Note: some people are more used to the _nC_k notation for combination.)

There is also a general solution already mentioned by Vistaptb, which may be guessed at by the actual answers found by Bushindo. People who like calculus may want to tackle that aspect of the problem.

Honorable mention to Rainman for also finding the right idea.

As for the problem of finding the largest number where the distribution is known suggested here by Caliban27 and Bonanova -- that's a different one. I never got around to working on it, so I will not start a new topic, though deserving it may be. I agree with Bonanova about the social implications of such problem. The problem presented here has a great value for young people in making their real life choices, as well.

[phaze]

Provided the kingdom has lax laws on polygamy marry all the women

[Prime]

Provided the kingdom has lax laws on polygamy marry all the women

Good tangential thinking. But it does not work per OP. You can't claim the prize, lest you pass the test. Sure, given 100 dowries, you may not need the job. However, the participating women would not be interested.

[bonanova]

The problem is easy to state and has a surprising solution. It goes under many names. Martin Gardner mentioned it in his February 1960 Scientific American article series as the Secretary Problem Googol problem. For only a moderately large number of applicants, and beyond, the stopping criterion and the probability of success are the same, namely 1/e. you go 1/e of the way into the applicant pool, and find the optimal candidate 1/e of the time. A good reference is this one http://en.wikipedia.org/wiki/Secretary_problem which explores a class of such problems.