Author 
Topic: The Dowry Problem (Part 2) (Read 941 times) 

navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender:
Posts: 28


The Dowry Problem (Part 2)
« on: Jun 23^{rd}, 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/thesultansdowrypuzzle.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 23^{rd}, 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 25^{th}, 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 1b^r but you still can loose. 

« Last Edit: Jun 25^{th}, 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 25^{th}, 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 26^{th}, 2018, 6:39am » 
Quote Modify

Here's a dumb idea: take the first slip to equal or exceed (n1)/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 26^{th}, 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 27^{th}, 2018, 7:22am » 
Quote Modify

on Jun 26^{th}, 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 27^{th}, 2018, 5:31pm » 
Quote Modify

on Jun 27^{th}, 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 27^{th}, 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 ith slip, you don't need it to calculate the cutoff. Rewriting my earlier criterion gives b < (1/2)^(1/r) , r=ni


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



FiBsTeR
Senior Riddler
Gender:
Posts: 581


Re: The Dowry Problem (Part 2)
« Reply #9 on: Jul 7^{th}, 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 8^{th}, 2018, 6:57am » 
Quote Modify

on Jul 7^{th}, 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 autowin. If P(k) is the probability of having exactly k dowries above the cutoff, then P(k+1) = ( (Nk) / [(k+1)(N1)] ) * P(k) so for small k, P(k)~ P(0)/(k!) (so long as (Nk)/(N1) ~ 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.


IP Logged 



