The Price is Right.

[Hellbent]

Let's say you were given a chance to marry rich. The King tells you that he's got 100 maidens with varying dowries. If you select the maiden with the largest dowry she will be yours as well has the kingdom. But if you choose a maiden with a dowry less than the highest dowry, you get nothing and lose your head to boot. You know nothing of the maidens' dowries, but each maiden presented to you will have the value of her dowry announced to you. You then must decide if she is the one with the highest dowry, or if you want to try your luck on the next maiden. Remember, you get no points for second place, you are solely interested in winning the maiden with the highest dowry. Is there any method you could use to help your odds in selecting the maiden with the highest dowry? Or are your odds one in 100 no matter what you do? The order of the maidens is completely random and you have no knowledge of the range that their dowries might fall within; that is, you don't know the upper limit or the minimum their dowries could be.

[John Smith]

Without knowing any values for certain other than the number of maidens its a one in one hundred chance of guessing the right one. A lot more information is needed to make anything resembling a statistical determination.

[EarthQuake]

I would guess that the odds are 1 in 100. But knowing you, you probably stumbled upon something on the internet that's similar to this.

[GreyGhost]

Pick the ugliest one or embrace polygamy.

[Aliotroph?]

This is why being able to carry guns is a good thing. If you have a 99% chance of losing your life anyway, shooting the king is probably not a bad plan.

[Twinzen]

This is a very interesting problem. I think the way to solve it is by statistical methods involving calculating the standard deviation and average for each new maiden you are presented with, and then choosing the first maiden whose dowry far exceeds it. The problem is that there is a lot of uncertainty in the beginning, so you better hope the right maiden is not among the first ones. I will try to solve this rigoruously today.

[bytor]

Profess Allah as your supreme god and all 100 maidens are yours!

...or something like that.

Been watching Deal or No Deal?

[Twinzen]

I might need to revise my original assertion. When using standard deviation on a dataset you assume there is rhyme and reason to it, but in this problem the dowry doesn't necessarily have an upper bound a priori. As an educated mathematician within the more theoretical branches, I can't claim to be an expert on numerics/statistics, but I have a tentative solution based on experimentation. (Using C++, which means my random number generator won't be very good, but I did the experiment 1 million times per number so it should be in the ballpark of the real solution.)

Basically, my method is as follows; Ask the first N maidens what their dowry is, then iterate over the rest of the maidens, asking each one what their dowry is, and as soon as someone claims to have a higher one than any of the first N maidens, choose her. Which value for N gives the highest probability of success? Turns out it is somewhere around 35-37. I'll go with 36. In other words, had I beed faced with this dilemma, I would ask the first 36 maidens what their dowry is, then I'd choose the first maiden among the rest who had a higher dowry than any of the first 36.

Chance of survival would then be 37.1% or so.

Is there a better solution?

[Maes]

Heh, we had to solve such decision/classification problems in signal theory during my M.Sc courses, although the classification wasn't so radical: e.g. we had to decide the optimum "cutoff point" between classifying fish in a canning factory as either cods or salmons, bearing in mind that a customer that found salmon instead of con in his tin can would likely NOT get pissed and press charges as someone who paid the premium for salmon yet found cod.

So the classification algorithm was biased to be "generous" with what would be considered "cod", and much more "strict" to classify something as "salmon" (even if that meant classifying some cods as salmons).

In this case however the problem is really simpler: only 1/100 is the good one, and none of your previous knowledge can help you "wisen up" for future choices (you don't even know if you left "bad" choices behind, as in the Monty Hall problem).

As unintuitive as it sounds, your chance to get the "good" bride is always 1/100, since you can't go back to any previous choice if I understood correctly (only blindly decide to advance to the next), and you can't make compromises/there is no tradeoff point as in just walking away with less money.

That being said... the chance that the first maiden is the "good" one is 1/100. If you choose it out of pure luck, congratulations, you won against a 99/100 chance to die! Otherwise, you make a choice saying "it's one of the remaining 99".

Assuming that the first one was NOT the right one, then the second one has a 1/99 chance to be the "good" one, and there's still a 98/99 chance for her NOT to be the good one.

So the n-th bride out of N in general has 1/(N-n+1) chance to be the good one, assuming that the previous ones weren't, and (N-n)/(N-n+1) not to be the one among her group.

The chance that you go entirely blindly through the first k-1 ones and then stop right dead-on on the k-th, right one is therefore

((N-1)(N-2)(N-3)...(N-k+1)))/(N(N-1)(N-2)....(N-k)))(1/(N-k+1) =

(N-k+1)/(N(N-k+1)) = 1/N

Aka the chance is always 1/N.

E.g. if it's the 1st of 100 this obviously gives 1/100.

For the second one, it would go

(99/100)(1/99)= 1/100.

For the third one it would go:

((99*98)/(100*99))(1/98)=1/100 again etc.

This essentially means that no matter which one is the "right" maiden, you have exactly 1/100 chance to find her (which is kinda obvious). Even when you are left only with 2, the chance that it's one of them two (and that you'll get that far by rejecting the other 98) is still 1/100.

It's NOT the same as being presented with just two maidens to begin with. So there.

And before people start linking to the monty hall problem...it's NOT the same because you're not given input on the previous choices. And if you skip over the 1st one which happens to be right one you're 99% fucked ;-)

[Twinzen]

Maes said:and none of your previous knowledge can help you "wisen up" for future choices (you don't even know if you left "bad" choices behind, as in the Monty Hall problem).

This is the point I would contest. Knowing the highest dowry you have heard up till a certain point would make you know for certain whether some of them NOT could be the right one, as they might present lower dowries. This makes it safe to exclude some. My argument is, take a chance that it is none of the 36 first maidens (64% chance of being right) then pick the first one who presents a dowry higher than any of the 36 first. (You could still be wrong of course, but I think the chance of success using this strategy is much better than 1/100.)
Anyway, I might be wrong in my analysis, but I can't see where exactly the problem lies.

[Twinzen]

Maes said:wall

I will demonstrate why your argument fails. Say there were only 5 maidens, and your strategy was to hear the 2 first maidens out, then pick the first of the 3 last ones who gives a higher number than the 2 first. I will use the numbers 1-5 to represent the maidens' dowries, where 1 is the lowest and 5 is the highest, though they are only representations of the real values.

Line up the maidens, and start interrogating them. There are 120 (5!) ways in which they can be lined up, and I will demonstrate that by using my strategy the chance of winning is higher than 1/5, and by analogy, the 100 maiden problem has a winning chance of more than 1/100:

The 5 is first: 5****, you lose (24 permutations)
The 5 is second: *5***, you lose (24 permutations)
The 5 is third: **5**, you win (24 permutations)


The 5 is last:

You only win if the 3rd and 4th digits are less than any of two first, that is, if 4 is among the 2 first:

34215
34125
43215
43125

24135
42135
24315
42315

14235
41235
14325
41325

12 wins, the rest are losses (4!-12 = 12)

we have determined that you will win in at least 36/120 scenarios, which is 30%. The real chance is even bigger since there are winning scenarios where the 5 shows up as the 4th digit, but I don't need to calculate it as I have shown that this strategy gives a winning chance higher than 20% (1/5).

I realized that the solution I gave earlier in this thread actually is analoguous to using standard deviations and statistical inference, as I use the first 36 values as a representative subset. Can you do better than my strategy? Probably, but you need to determine where to stop, how many standard deviations from the mean f.ex? This is subtle statistics that are out of my expertise, so I will wait for OP to post his answer. I will be surprised if it is much better than my strategy yielding ~37.1%.

[Hellbent]

Twinzen's answer is dead on. Interestingly, the reciprocal of 0.36 happens to be ~ the number e The best cut off point remains at 36% of all the maidens, whether there be 100 or 38,000.

EDIT: I'm taking a calc I right now and this was a problem the professor posed to the class. We didn't get into the methodology (a bit too advanced at this point) but he did say that if you pick the highest dowry after 36 maidens have gone by, that gives you the best chance of winning.

[Maes]

Twinzen said:

This makes it safe to exclude some.

From the OP::
You then must decide if she is the one with the highest dowry, or if you want to try your luck on the next maiden.

My understanding of this is that you CAN'T go back to rejected choices, so any information you collect about them is worthless: you must decide right there and then if you want to pick a particular maiden, and at most you can know the amount of HER dowry. If you reject her and later on you discover that she was, indeed, the one with the higher dowry, then you're fucked: you can't go back. Else it would not be a dumb luck problem, it would be simple search algorithm ;-)

That formulation also implies that if you reject all of the first 99 Maidens, you are FORCED to choose the last remaining one no matter what.

That's the main diff

Twinzen said:

My argument is, take a chance that it is none of the 36 first maidens (64% chance of being right)

No :-D

When examining any one of them individually, you are always faced with
a 1/100 chance of being right and 99/100 of being wrong.

Now, if the VERY degenerate case that they are lined up from lower to higher (without you knowing it), rejecting the first one would be corect 99/100 times (in the other 1/100 you pick her), the second would be 98/99, etc. so doing all 99 correct rejections has still (99*98*...*1)/(100*99*....*2) = 1/100 chance of occuring.

Since a picture is worth 1000 words...



After 36 rejections, and ONLY in that particular case where they are already sorted in order AND you are told that none of them was the highest one, you have an increasing chance of picking the right one after a rejection (yellow line), but you also have a decreasing chance of keeping rejecting correctly is the remaining n-k maidens could be in any order (blue line). Picking one at random after k rejections is shown with the purple line.

AGAIN, if you are NOT told anything about NOT having already picked the one with the highest dowry, YOU CAN'T BE CERTAIN UNTIL YOU REACH THE VERY LAST ONE OF THEM, and all picks are a 1/100 flatline.

[Twinzen]

Maes said:

No :-D

Yes. If you have 100 maidens lined up the chance of the right one being "to the right" of the first 36 is 64%. That was all I was saying. The first chance you take is discarding the first 36 as the right one, the second chance you take is assuming the first maiden who presents a higher dowry than the first 36 is the right one, if any such exists, whatever the probability is. With hindsight I can say that the probability of that is 58% since I know the product probability to be around 37%.

Thanks for the interesting problem Hellbent.

[Maes]

@Twinzen: applying a-posteriori odds on a situation where you are not deliberately shown the "known losing" options is not proper, therefore your method, although correct from a procedural point of, would not actually help the poor devil faced with that diabolical choice in the least.

What you are doing in fact, is willingly cutting away a part of the problem by rejecting the 3 first maidens no matter what, and then applying your "enhanced odds" only on the remaining two (and the same thing by extension to 100).

Then again only by running a numeric simulation we can be 100% sure...

I mean, imagine if this was a sorting algorithm which must find the maximum in an array of n elements.

Does it sound like a good idea to examine the values of the first k elements, REJECT them, and then pick the first of the remaining that's larger than any of the first?

Sure, you have a (n-k)/n chance to find it in somewhere WITHIN the remaining n-k elements alone, 1/(n-k) of actually finding it WITHIN those elements (if it's there), and still 1/n chance overall (or 0/n if you left it in the first k elements).

It's pure elementary probability, as the values of any element you examine don't tell you if you're doing something wrong or if you're in a good way.

In the Monty Hall problem and its generalizations you are actually given negative feedback ("Here, I uncovered a known bad for you!").

[Hellbent]

Maes, do you want to write a simple program that tests Twinzen's hypothesis? It seems to me reasonable that if you wait for a certain number to pass, and then pick the highest after that, you've at least done something to increase your odds above completely blind guessing. I might show him both of your arguments after class on Monday and see what he has to say. Honestly, the calculations for this problem are above me, but I thought it was titillating, so I thought I'd share.

[Twinzen]

Maes said:

Does it sound like a good idea to examine the values of the first k elements, REJECT them, and then pick the first of the remaining that's larger than any of the first?

Absolutely, it is a good idea. Indeed it is the best strategy in the long run. The point is that we use the first 36% of the dataset as a representative subset. Also the a posteriori odds are either 100% or 0%. My odds are a priori. If you were "the poor devil" facing this situation, you would be well adviced to use my strategy, as there is nothing better. You need to discard a certain amount of datapoints just to get a representative subset that will make the standard deviation small enough to go by.

If you discard too few, the standard deviation stays so large that you can't make good judgment where to stop.
If you discard too many, your sd will be smaller but you risk rejecting the right maiden for every new datapoint you collect.
This problem is about finding the balance between the two. That being said, I am glad I don't face this dilemma irl. :p

Edit: My apologies. Looks like I quoted you out of context. In a searching algorithm over an unsorted dataset you have no choice but to iterate over all the elements, and choose the biggest one you find. By using my "method" you will only be right in ~37% of all cases. However, your life is at stake, so you need to take a risk, but try to minimize it. By iterating over all maidens like if it were a searching algorithm you would have to choose the last one, and the chance of being right would be 1/100 as you correctly point out.
The good thing about a searching algorithm is that you can go back and select a datapoint a posteriori, but in this riddle you can't go back to an earlier maiden. A searching algorithm under the condition that it can't go back would indeed have to use my strategy, and only yield a 37% success rate. Not relevant for computer science, I agree.

[Maes]

Hellbent said:

Maes, do you want to write a simple program that tests Twinzen's hypothesis? It seems to me reasonable that if you wait for a certain number to pass, and then pick the highest after that, you've at least done something to increase your odds above completely blind guessing.

Such a program would only "win" if it chose the highest number more often than 1/100, for 100 numbers, in absolute terms.

That is, I run it 10000 times, and if it finds it significantly more than 100 times. Then I don't see how rejecting any part of the array a-priori would help with that. It's like turning a blind eye on a part of the problem. If that was practical, it would bring a revolution in computer science...guess why it didn't.

[Maes]

Well, I'll be damned...

public class Debunk {

    public final static int SIMULATIONS=100000;
    public final static int REJECT=36;
    
    public static void main(String[] argv){        
        
        
        double[] shit=new double[100];

        
        //System.out.println("Maximum: "+max + " Index: "+maxindex);
        
        int wins=0;
        int twinzenwins=0;
        
        
        for (int i=0;i<SIMULATIONS;i++){
            
            double max=Double.NEGATIVE_INFINITY;
            int maxindex=0;
            
            // Both will work on the same array.
            
            for (int j=0;j<shit.length;j++){
                shit[j]=Math.random()*100;
                if (shit[j]>max){
                    max=shit[j];
                    maxindex=j;
                }
            }
            
            
            // Dumb luck
            int gamble=(int) (Math.random()*99);
            if (gamble==maxindex) wins++;
            
            // Twinzen's "better" odds.
            double twmax=Double.NEGATIVE_INFINITY;
            double twindex=-1; // none found.
            

            for (int j=0;j<shit.length;j++){
            // Reject first REJECT maidens, and find tentative max.                
                if (j<REJECT){
                    if (shit[j]>twmax)
                        twmax=shit[j];
                        }
                    
                else {
                    // found first bigger value. Stop.
                    if (shit[j]>twmax) twindex=j;                    
                }   
            }
            
            // Seems Twinzen won ;-)
            if (twindex==maxindex) twinzenwins++;
            
        }
         
        System.out.println("Dumb luck pure wins: " +wins);
        System.out.println("Dumb luck odds: " +(100.0*(double)wins/SIMULATIONS)+" %");
        
        System.out.println("Twinzens pure wins: " +twinzenwins);
        System.out.println("Twinzens odds: " +(100.0*(double)twinzenwins/SIMULATIONS)+" %");
        wins=0;        
       
        
        }       
        
    }

It actually does give a 36-odd chance for the "Twinzen method". It also seems that this particular number is the maximum possible, rejecting any more or less causes the odds to decrease, with the
limit approaching the same odds as the dumb luck method as one goes towards 0 or MAX-1 rejections. Even rejecting 1 gives a solid 5% winning odds.

I admit I'm puzzled, because I thought that the perceived odds were simply due to context trickery/wordplay.

On the other hand, simply rejecting any number of maidens with the "dumb luck" approach doesn't change the odds at all: any random pick is good as any other.

Twinzen said:

Not relevant for computer science, I agree.

Well..it could yield an improved version of bogo sort ;-)