wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The Dowry Problem (Part 2)
        
(Message started by: navdeep1771 on Jun 23^rd, 2018, 11:32am)

Title: The Dowry Problem (Part 2)
Post by navdeep1771 on Jun 23^rd, 2018, 11:32am

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]

Title: Re: The Dowry Problem (Part 2)
Post by towr on Jun 23^rd, 2018, 12:13pm

[hide]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 [/hide]

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

Title: Re: The Dowry Problem (Part 2)
Post by Grimbal on Jun 25^th, 2018, 8:18am

[hideb]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.
[/hideb]

Title: Re: The Dowry Problem (Part 2)
Post by towr on Jun 25^th, 2018, 11:04am

[hide]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.[/hide]

Title: Re: The Dowry Problem (Part 2)
Post by rmsgrey on Jun 26^th, 2018, 6:39am

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

Obviously not optimal.

Title: Re: The Dowry Problem (Part 2)
Post by towr on Jun 26^th, 2018, 1:15pm

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.

Title: Re: The Dowry Problem (Part 2)
Post by rmsgrey on Jun 27^th, 2018, 7:22am

on 06/26/18 at 13:15:32, towr 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.

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.

Title: Re: The Dowry Problem (Part 2)
Post by dudiobugtron on Jun 27^th, 2018, 5:31pm

on 06/27/18 at 07:22:07, 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.

Title: Re: The Dowry Problem (Part 2)
Post by towr on Jun 27^th, 2018, 10:31pm

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 [hide]b < (1/2)^(1/r) , r=n-i[/hide]

Title: Re: The Dowry Problem (Part 2)
Post by FiBsTeR on Jul 7^th, 2018, 6:08am

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:
[hide]
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.
[/hide]
Any other ideas to try that might be better?

Title: Re: The Dowry Problem (Part 2)
Post by rmsgrey on Jul 8^th, 2018, 6:57am

on 07/07/18 at 06:08:11, 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=1^N[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.