wu :: forums
« wu :: forums - The Dowry Problem (Part 2) »

Welcome, Guest. Please Login or Register.
Sep 24th, 2018, 5:58pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, william wu, ThudnBlunder, towr, Grimbal, SMQ, Icarus)
   The Dowry Problem (Part 2)
« No topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: The Dowry Problem (Part 2)  (Read 184 times)
navdeep1771
Newbie
*



Let your thoughts go beyond your imagination

    navi
Email

Gender: male
Posts: 22
The Dowry Problem (Part 2)  
« on: Jun 23rd, 2018, 11:32am »
Quote Quote Modify 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: male
Posts: 13640
Re: The Dowry Problem (Part 2)  
« Reply #1 on: Jun 23rd, 2018, 12:13pm »
Quote Quote Modify 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: male
Posts: 7408
Re: The Dowry Problem (Part 2)  
« Reply #2 on: Jun 25th, 2018, 8:18am »
Quote Quote Modify 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: male
Posts: 13640
Re: The Dowry Problem (Part 2)  
« Reply #3 on: Jun 25th, 2018, 11:04am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: The Dowry Problem (Part 2)  
« Reply #4 on: Jun 26th, 2018, 6:39am »
Quote Quote Modify 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: male
Posts: 13640
Re: The Dowry Problem (Part 2)  
« Reply #5 on: Jun 26th, 2018, 1:15pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: The Dowry Problem (Part 2)  
« Reply #6 on: Jun 27th, 2018, 7:22am »
Quote Quote Modify 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: 713
Re: The Dowry Problem (Part 2)  
« Reply #7 on: Jun 27th, 2018, 5:31pm »
Quote Quote Modify 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: male
Posts: 13640
Re: The Dowry Problem (Part 2)  
« Reply #8 on: Jun 27th, 2018, 10:31pm »
Quote Quote Modify 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
****





   
WWW

Gender: male
Posts: 581
Re: The Dowry Problem (Part 2)  
« Reply #9 on: Jul 7th, 2018, 6:08am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: The Dowry Problem (Part 2)  
« Reply #10 on: Jul 8th, 2018, 6:57am »
Quote Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« No topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board