Author |
Topic: The Dowry Problem (Part 2) (Read 944 times) |
|
navdeep1771
Newbie
Let your thoughts go beyond your imagination
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print