wu :: forums « wu :: forums - The Dowry Problem (Part 2) » Welcome, Guest. Please Login or Register. Apr 17th, 2024, 8:27am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, william wu, towr, Icarus, Grimbal, Eigenray, ThudnBlunder)    The Dowry Problem (Part 2) « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: The Dowry Problem (Part 2)  (Read 941 times)
navdeep1771
Newbie

Gender:
Posts: 28
 The Dowry Problem (Part 2)   « on: Jun 23rd, 2018, 11:32am » Quote Modify

You must have heard about the Part 1:-

The king, to test a candidate for the position of wise man, offers him a chance to marry the young lady in the court with the largest dowry. The amounts of the dowries are written on slips of paper and mixed. A slip is drawn at random and the wise man must decide whether that is the largest dowry or not. If he decides it is, he gets the lady and her dowry if he is correct; otherwise he gets nothing. If he decides against the amount written on the first slip, he must choose or refuse the next slip, and so on until he chooses one or else the slips are exhausted. In all, 100 attractive young ladies participate, each with a different dowry. How should the wise man make his decision?

It's discussion: (I would recommend you to only see the solution of part 1 if you have tried the problem or you have already solved before)
(http://bayesianthink.blogspot.com/2012/12/the-sultans-dowry-puzzle.html

Now, here comes a twist in Part 2.
In the previous problem (part 1)  the wise man has no information about the distribution of the numbers. But in this problem (part 2) he knows exactly.

Part 2: "Choosing the Largest Random Number"
As a second task, the king wants the wise man to choose the largest number from among 100, by the same rules, but this time the numbers on the slips are randomly drawn from the numbers from 0 to 1 (random numbers, uniformly distributed). Now what should the wise man's strategy be?

[Source: 50 challenging problems in probability by Frederick Mosteller]
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: The Dowry Problem (Part 2)   « Reply #1 on: Jun 23rd, 2018, 12:13pm » Quote Modify

Take a new slip while there are better than even odds there's a better one than the one you're holding.
i.e if b is the best so far and there are r unseen slips remaining, pick a new one if 1/2 > b^r or if you don't hold b

I think I asked a variant once where you knew it was a normal distribution, but not the mean and variation (so you had to estimate them as you went).
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: The Dowry Problem (Part 2)   « Reply #2 on: Jun 25th, 2018, 8:18am » Quote Modify

 hidden: I don't think it is that simple. While your criteria is correct to decide which is the best decision for that slip, it doesn't mean you can benefit from it. If you keep the slip, you will win with probability b^r.  If you reject the slip, you are right with probability 1-b^r but you still can loose.
 « Last Edit: Jun 25th, 2018, 8:19am by Grimbal » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: The Dowry Problem (Part 2)   « Reply #3 on: Jun 25th, 2018, 11:04am » Quote Modify

It's definitely a better strategy than the one for the original bachelor dilemma (a Monte Carlo simulation easily shows that). But you're right that it may not be optimal.

One important thing is that if there is a better slip among the remaining, then unless you attempt to get it, you've already lost.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: The Dowry Problem (Part 2)   « Reply #4 on: Jun 26th, 2018, 6:39am » Quote Modify

Here's a dumb idea: take the first slip to equal or exceed (n-1)/n.

Obviously not optimal.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: The Dowry Problem (Part 2)   « Reply #5 on: Jun 26th, 2018, 1:15pm » Quote Modify

Choosing a fixed cutoff based on N is not a lot worse than my strategy, funnily enough.

Maybe picking a cutoff for every index + not stopping if you don't have the best seen so far might do even better.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: The Dowry Problem (Part 2)   « Reply #6 on: Jun 27th, 2018, 7:22am » Quote Modify

on Jun 26th, 2018, 1:15pm, towr wrote:
 Choosing a fixed cutoff based on N is not a lot worse than my strategy, funnily enough.   Maybe picking a cutoff for every index + not stopping if you don't have the best seen so far might do even better.

It's obvious that the only relevant information on each draw is whether you've already seen a better, and where in the sequence you are.

For the traditional problem, you use part of the data to estimate the distribution. Because the distribution is known, the only relevant information about past draws is whether or not one of them beat your current draw - there's no information about your potential future draws there.

Your strategy is another example of having a fixed cutoff for each index.
 IP Logged
dudiobugtron
Uberpuzzler

Posts: 735
 Re: The Dowry Problem (Part 2)   « Reply #7 on: Jun 27th, 2018, 5:31pm » Quote Modify

on Jun 27th, 2018, 7:22am, rmsgrey wrote:
 It's obvious that the only relevant information on each draw is whether you've already seen a better, and where in the sequence you are.

I think that the value on the slip you drew is also relevant (if it is the highest so far).  Since you already know the probability distribution, you can use the information (like towr did) to work out the probability of improving on your result.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: The Dowry Problem (Part 2)   « Reply #8 on: Jun 27th, 2018, 10:31pm » Quote Modify

The value on the slip is only relevant in so far as you need to compare it to the cutoff for the i-th slip, you don't need it to calculate the cutoff. Rewriting my earlier criterion gives b < (1/2)^(1/r) , r=n-i
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
FiBsTeR
Senior Riddler

Gender:
Posts: 581
 Re: The Dowry Problem (Part 2)   « Reply #9 on: Jul 7th, 2018, 6:08am » Quote Modify

I wrote a script to simulate the strategies presented so far: https://pastebin.com/spkfmCNd. Either my code is buggy or my intuition is way off but I was surprised how high the win percentages are!

For 100k trials with 200 slips:

Fixed cutoff based on N (rmsgrey's) wins ~52%.
Choose slip if <50% chance there is better later (towr's) wins ~58%
In both cases, the ratios assume you keep going if you've seen better earlier.

Any other ideas to try that might be better?
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: The Dowry Problem (Part 2)   « Reply #10 on: Jul 8th, 2018, 6:57am » Quote Modify

on Jul 7th, 2018, 6:08am, FiBsTeR wrote:
 I wrote a script to simulate the strategies presented so far: https://pastebin.com/spkfmCNd. Either my code is buggy or my intuition is way off but I was surprised how high the win percentages are!

For my approach, you win when:
There are no dowries above the cutoff but the last is the highest by chance (conditional probability 1/N)
There is exactly one dowry above the cutoff (conditional probability 1)
There are exactly k>1 dowries above the cutoff and the first of them is the highest by chance (conditional probability 1/k).

With the expected number of dowries above the cutoff being 1, there's going to be a large chunk of the total cases where you get exactly 1 and auto-win.

If P(k) is the probability of having exactly k dowries above the cutoff, then P(k+1) = ( (N-k) / [(k+1)(N-1)] ) * P(k) so for small k, P(k)~ P(0)/(k!) (so long as (N-k)/(N-1) ~ 1)

So for large enough N, you'd be looking at (1/e)Sum k=1N[1/(k*k!)] or a little under 50% (~48.5%)

So, yeah, my intuition of "about half" (half the times k is 0, 1 or 2 and the other cases don't contribute much either way) seems about right.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »