Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Spooky math problem

by tilly (Archbishop)
on Nov 01, 2000 at 05:41 UTC ( #39366=perlmeditation: print w/ replies, xml ) Need Help??

On my home node for some time I have had an interesting problem:
Suppose I have two envelopes. All you know is that they contain different numbers. I randomly hand you one of them. You open it, look at it, then hand it back. You now have sufficient information to, with guaranteed better than even odds, correctly tell me whether I gave you the envelope with the larger number. How?
I warn that the answer is crazier than the problem.

It being Halloween I think it appropriate to publically demonstrate that by giving the answer.

The trick is that you make up a number, pretend it is the one that I still have, and that gives you just enough information to get better than even odds, guaranteed!

How is that for sheer and utter insanity? Not to mention being spooky!

Now before I fill in details and explanations, I should mention that this problem is not original to me. I learned it from Laurie Snell, a well-known probability theorist, and it has a history dating back to the 60's. From me it found its way onto the Internet, and can be found in such places as rec.puzzles.

First details. The above answer is indeed correct, and to have it work you need to pick your number from a "continuous probability distribution with non-zero density everywhere". If that confuses you, just think of a normal distribution which is widely known as the bell curve.

Now explanations. The first is a simple algebraic explanation. If you sit down and do the algebra, you will find that your probability of being right turns out to be exactly 50% plus 1/2 the probability that you pick a number between my two. While obviously you don't know when you pick a number between my two, you do know that you have some chance of doing so, so you know that you have better than even odds of being right.

Some people like that explanation, some prefer to see a picture. Well get out a piece of paper and draw a line. Put two marks on it to represent my two numbers. From the right mark draw an arrow left. This is the range of numbers you need to pick in to get the answer right if you are handed the larger number. From the left mark draw an arrow right. This is the range of numbers you need to pick in to get the answer right if you are handed the smaller number.

Now look closely. If you pick a number bigger than both of mine, you have even odds of being right. Ditto if you pick a number smaller than both of mine.

But if you pick a number between mine, You are right. Guaranteed.

Since you always have a chance of picking a number between my two, you always have better than even odds.

See? You can get something for nothing! Real information from just making something up! How much you cannot know, but you get something! :-)

UPDATE
This appears in the rec.puzzles FAQ as "high or low" and their answer appears here.

UPDATE 2
I have posted Perl code at Spooky math - with Perl which shows the argument in detail. It is a little raw, but works and shows the key ideas in the explanation.

Comment on Spooky math problem
RE: Spooky math problem
by BlueLines (Hermit) on Nov 01, 2000 at 06:02 UTC
    Hrmm, i dunno about this.

    Let x,y be your two numbers. So there are |x-y| possible "correct" guesses (a "correct" guess being one that falls between x and y).

    Let z be the set from which i'm randomly picking a number n. This number can be anything (1, pi, 2^.5, e^i*pi, etc). So there's an infinite set of numbers from which i'm choosing one member. (I'm not going to get in to the infiniteness of this infinity, as it's been too many years since i've taken discrete math).

    The chances of me picking a "correct" number are |x-y|/|z|, where z is infinite, which is 0.

    The assumption of gaining odds based on this imagined third number assumes that there is a last number at some point. Once you can quantify infinity, you can retrieve a decimal approximation of your odds. Until that point, you are dealing with zero.

    If you're going to pretend that a number is in between the other two, you might as well pretend you know what the other number is....

    Update: Here's the proof in the rec.puzzle FAQ. I see two things wrong with it (i think), but i'm going to check into this before posting:-)

    Pick any cumulative probability function P(x) such that a > b ==> P(a) > P(b). Now if the number shown is y, guess "low" with probability P(y) and "high" with probability 1-P(y). This strategy yields a probability of > 1/2 of winning since the probability of being correct is 1/2*( (1-P(a)) + P(b) ) = 1/2 + (P(b)-P(a)), which is > 1/2 by assumption.

    Update II, Electric Boogaloo: Here's the problem with the proof. As it is written, it is correct, but the first assumption it makes is false. For this situation (picking two random numbers from an infinite set), it is impossible to create a cumulative probability function P(x) as the solution describes. The cumulative probability function is based on the probability mass function, which is always undefined in this case. The probability mass function for any value in this problem is 1/infinity, which is zero. The cumulative probability function is a sum of probability mass functions, which will be zero no matter how many you add together. So if it were indeed possible to pick a function like the proof describes, the proof would hold. However, since the initial assumption is a contradiction, the proof fails.

    Here's a nice discussion on cumulative probability functions, and here's a discussion of the probability mass function. Neat-o. Has anyone seen another proof of this?

    BlueLines

    Disclaimer: This post may contain inaccurate information, be habit forming, cause atomic warfare between peaceful countries, speed up male pattern baldness, interfere with your cable reception, exile you from certain third world countries, ruin your marriage, and generally spoil your day. No batteries included, no strings attached, your mileage may vary.
      Read very, very carefully. :-)

      What your probability is of being correct depends on what two numbers I have. You only can guarantee that it is better than even, but it could be by a very small amount indeed. There is theoretical discussion on this, and the fact that you don't know the probability turns out to be important. (I don't remember details though.)

      However there is a variant of this problem where both you and I pick our numbers independently out of the same distribution. Now you can work out the probability of your being right prior to my picking my numbers. And even though your number has no actual information about mine, you turn out to be right exactly 2/3 of the time. If you disbelieve this it is easy to write a short script to test it.

      Again, I got this problem from a probability theorist and it really does work.

        A Perl script describing this would be most helpful. All this math talk is giving me a headache. Theoretical physics I can handle. It's conceptual. Math is another matter. Given that I think in Perl, I think that'd be best.
      Questions about how I got my numbers get you into the kind of trouble you describe. But that is outside of the problem.

      What is inside is that when you make up a number, you need to use a "good" cumulative distribution. And there are plenty of them indeed to be found in any good probability theory book. In fact I named one. The standard normal, which is the prototypical bell-curve, is a probability function which will work. (Albeit with a tail that falls off very rapidly, so your win is miniscule if my numbers are very far away from zero.)

      Trust me. I studied math long before I studied Perl, and I got this problem off of a well-known probability theorist. The solution is good.

RE: Spooky math problem
by runrig (Abbot) on Nov 01, 2000 at 07:04 UTC
    This is voodoo math. I looked in the rec.puzzles FAQ on deja and all I could find is this:

    "Someone has prepared two envelopes containing money. One contains twice as much money as the other. You have decided to pick one envelope, but you can then "prove" that the other envelope contains more money than the one you chose."

    "Threads about these and other logical paradoxes tend to go on for a long time and can get nasty as people try to convince each other of the truth of their positions. If you would like to start a thread about a paradox, please read the archive explanation first to see if that clears things up for you. Whether you are reading or posting to one of these threads, remember that there are many logical interpretations that are often equally valid. If there weren't, it wouldn't be a paradox, would it?"

    Update: I looked at the url you gave, but I like this one (update: that link now dead AFAICT) better :-) (At least he uses perl...I wonder if he uses taint?)

    Update regarding BlueLines's post: I would've bet that there'd be a division by zero somewhere...
RE: Spooky math problem
by rlk (Pilgrim) on Nov 01, 2000 at 11:37 UTC
    I don't buy this. Call the amounts in the two envelopes "A" and "B". A is known, B is not. So you guess at B and pick the number "B'". Now, If B' > A, you will pick B, and you will be right if B > A. B can be anything, so the probability of this is 50%. Alternately, if you pick B' such that A > B', your chance of being correct with respect to B is also 50%. So, 2 out of 4 possibilities of being correct. Even odds overall.

    --
    Ryan Koppenhaver, Aspiring Perl Hacker
    "I ask for so little. Just fear me, love me, do as I say and I will be your slave."

Non-Perl Topic OK?
by princepawn (Parson) on Nov 01, 2000 at 13:24 UTC
    Because it has been awhile since I have received deluge of downvotes and because I am eager to secure my fourth position in the all-time worst nodes hall of fame, it is time for me to ask a question:

    What does the original post in this thread have to do with Perl? And, assuming I know enough about to Perl that my conclusion that it has nothing to do with Perl is correct, then why should I not downvote this because it has no business here?

    Of course, it is very hard to criticize someone whom you have met in person, but, well, somebody's gotta do the dirty work.

    And of course finally,due to my highly developed psychic powers, I can already see a -30 or -40 reputation on this post. But, if you would be so kind, please drop me a line as to why I deserve such treatment for an innocent and reasonable post.

    Over and out, the -- magnet, princepawn

      princepawn, I believe that until your post contains the words "Natalie Portman naked and petrified" you may still be looking at a single digit negative reputation for this node.

      And for the record, the above is the first time I have ever typed the words "Natalie Portman naked and petrified", much less posted such in a monastery.

        Sounds good. Where can I buy copies of the sculpture? Are there any plans to petrify anyone else? Adriana Lima maybe? ;-)

        Jenda
        XML sucks. Badly. SOAP on the other hand is the most powerfull vacuum pump ever invented.

      Not everything on this site is strictly perl. For example, look at the current poll. At other times, conversations take twists and end up being about everything but programming. I think it would be pretty dull if we never brought up other topics.

      On the other hand, too much off-topic discussion will obscure the main subject of the site. I, at least, would find it nice if posts were labeled in some way, either with an 'ot' disclaimer in the title, or with a section as discussed.

RE: Spooky math problem (featuring perl!)
by turnstep (Parson) on Nov 01, 2000 at 22:49 UTC

    Someone asked for some perl?

    Try this out with a small range (3) and then boost it up to 100 and watch the difference. Running at least 100,000 games is recommended but play around with the variables. :)

    #!perl ## HiLowDeal use strict; ## This program has a "dealer" and a "player" ## The dealer generates two random numbers and sticks them ## into two envelopes. One of these is handed to the player. ## The player looks at her number, then picks another ## number at random and assumes that she has picked the ## dealer's number. She then either states that she has ## the high or the low envelope. 50/50? Perhaps not... ## Usage: HiLowDeal 10 10000 50 ## The above example plays ten thousand games, ## uses the numbers 1 through 10 to draw the random numbers from, ## and outputs a running total about 50 times my $games = shift || 10000; ## How many games shall we play? my $limit = shift || 10; ## What range of numbers? my $checkpoint = shift || 3; ## Approximate # of checkpoint displa +ys $checkpoint = int $games/$checkpoint; ## The total set is really an infinite set, but we ## will restrain our players to this without letting ## them "know" the range, making it effectively infinite. ## In other words, if a "10" is received, they do not know ## that there is no "11", "12", etc... and cannot automatically ## deduce that they have the higher card. my @money=(1..$limit); print "Games=$games, from 1 to $limit, checkpoint is $checkpoint.\n"; my ($letter1, $letter2); my ($guess, $result, $actual); my $total=0; my $counter=0; for (1..$games) { ## Select two random cards, must be different $letter1 = $money[rand @money]; { $letter2 = $money[rand @money]; redo if $letter1 == $letter2; } ## Player one has both, letters, then one to player #2. ## Player two looks at his, then makes a guess as to the other one. ## Cannot guess their own number { $guess = $money[rand @money]; redo if $guess == $letter2; } ## The player's best guess: (1 means they have the higher card) $result = $letter2 > $guess ? 1 : 0; ## The actual value: $actual = $letter2 > $letter1 ? 1 : 0; ## Are they correct? If so, give them a point. If not, take one away +: $total += ($result==$actual) ? +1 : -1; if (++$counter == $checkpoint) { $counter=0; print "TOTAL: $total\n"; } } print "Grand total: $total\n";
      Update: OK I'm re-reading everything and I'm still not sure that I understand it after all.. *sigh*..

      For those that don't get it, like I didn't, realize that we're making one important assumption here: that both parties know the upper and lower bounds of the numbers!

      Sure, if we know we're working from 0 .. 100, and the envelope we see is number 88, odds are, it's the higher of the two envelopes (assuming both are truly random; this can be defeated if the "dealer" keeps writing two consecutive numbers or otherwise knows the trick). Now I look at the situation and think, "Well yah, duh."

      But what if you don't know the upper bounds? Modify the lines in the script like below, and the odds come out to exactly 50%: what we'd expect. The way *I* would play this game in real life, without knowing the limit, is to try to "figure out" the limit as I go, but statistically, given a one-time shot, we have to assume that the number we were given is, on average, mid-way through the distribution. This means that no matter what number we think of, we're still 50% likely of guessing right.

      ... $letter1 = $money[rand @money / 2]; { $letter2 = $money[rand @money / 2]; redo if $letter1 == $letter2; + } ... { $guess = $money[rand (($letter2+1) * 2)]; redo if $guess == $lette +r2; } ...
      But if we know we're going to play 100 games, we can sorta "figure out" the upper limit as we go (assuming there is one, and it's kept constant during play), by assuming that our numbers will average out to be mid-way through the distribution. That would let us approach a higher probability of being correct further down the line. The script can be modified to play by those rules too, but I'll leave that as an exercise for the reader.

      If you were to actually make these bold statements and try them in real life (give them 10 cards, pick two at random, show me one and I'll guess 66% correctly whether it's the higher of the two cards), I would seriously hope that they would figure out the trick without me needing to guess very much, if at all. If they were smart, they'd shut up when they figured it out and would keep pulling, say 9 and 10, and showing me the 9 all the time.

        Whoa. What tilly is claiming is that we have a "better than 50% chance" of getting it right. The degree to which it's "better" can be *mind-bogglingly miniscule* (we're talking continuous quantities here) so I don't think we're warranted in exporting any claims about the actual probabilities from what a program reports.

        Philosophy can be made out of anything. Or less -- Jerry A. Fodor

        No such assumption is made in the problem.

        With a continuous probability distribution you can have some probability of picking a number in any range at all. The probability may be low, but it is always positive. That is why I said "non-zero density everywhere" in the details.

        More carefully stated the experiment is defined as, "I hand you one of my two numbers at random, you look at it, hand it back, and make a guess as to high or low." The assertion is that there is a method you can use such that, no matter what my numbers are, you will have better than even odds of being right. What your odds are will depend, of course, on what my numbers are. All that you can guarantee is better than even.

        Of course any purely mechanical computer will have the usual problems with "randomly pick out of a continuous distribution" however you can specify a concrete algorithm for doing that with coin-flipping (note that you don't need to find the number precisely, just determine it to sufficient detail to compare it with the one you were handed). You need make no assumptions on my numbers. And an outside observer who knows both my numbers and your method can calculate the exact probability you will be right - and that will be better than even.

        Guaranteed.

        (Yes, this skirts on the boundary of a lot of interesting problems, philosophical and otherwise, in math.)

(crazyinsomniac) RE: Spooky math problem gone CRAZY
by crazyinsomniac (Prior) on Nov 02, 2000 at 00:36 UTC
    When I saw tillys question for the first time, i was really confused. My problem, as always, turned out to be that i didn't really understand the question in the first place. The English combined with my lack of attention to detail, really warped my perception of what the question was. Here's my version of the question (modified so normal people can understand):
    Suppose I have two envelopes. All you know is that they contain a different number of flashcards, with different numbers on each of them. I randomly hand you one of them. You open it, look at it, then hand it back. You now have sufficient information to, with guaranteed better than even odds, correctly tell me whether I gave you the envelope with the larger sum. How?
    This is how i understood tilly's problem at first, so i thought, "what the $@@$!?! THATS IMPOSSIBLE!!!" Then i thought "OK,ok, don't give up so fast, he says there's a solution." I continued thinking about this problem and the answer tilly gave occured to me, but i thought you don't know how many flashcards you have, so the sum can be anything. But think about it.
    You make up a number, and pretend it is in between the sums of the two envelopes, and that the number on the flashcard I handed you is between the number of flashcards in each envelope, and so you can guarantee to have better than 1/2 odds of guessing which envelope has the largest sum. It is more miniscule percentage than the one from tilly's original problem but it is the same principal.

    1/2 + (crazy math) = better than 1/2

    update: May 2, 2001 11:50AM PST
    I've been reviewing some of my posts lately, and I've noteiced that this one doesn't quite reflect my ignorance and misunderstanding of the question. With that said, I point out that what is written here is not what was in my head at the time of writing, but rather a broken argument of misunderstanding. So please just accredit this one to irresponsibility, sleep depravation, and whatever else you want. Like all(most) of my posts, I leave this one as a reminder and example of what to avoid, in hopes i will not repeat my stupdeneous error, or merely dislexic miscommunication.

    "cRaZy is co01, but sometimes cRaZy is cRaZy".
                                                          - crazyinsomniac

RE: Spooky math problem
by Compilers-R-Us (Initiate) on Nov 02, 2000 at 01:04 UTC
    Let's frame this in the simplest terms: You can only 'win' if you know something about the mean of the probability distribution that produced the numbers. As we say in physics, this breaks the symmetry of the problem. You have more information that just the value of one number, and from there you can compare your number with the mean. If your number is higher than the mean, than you are likely to have the higher number. Otherwise it is likely to be the lower. If you have a uniform probability distribution between + and - infinity, one could argue that the mean is zero. Therefore, if the number you viewed is positive, it is likely the higher one and vice versa. However, I don't feel comfortable saying it is the mean - too many infinities are involved. It depends on your definition of zero and infinity. A good definition of zero is that it is the mean of integers, rational and/or irrational numbers. A bell curve, although infinite, has a definite mean and finite integral. The probability is zero at +/- infinity, so there are fewer affronts to nature.
      Read the problem again. Were such assumptions needed you can be sure I would have stated them. But they are not.

      The key is that your random number needs some chance of falling in the interval between the numbers. As long as you can guarantee that, you get better than even odds. But it turns out that is not hard to guarantee. However if the two numbers differ by, say, 1 from each other it turns out that on average you are ahead by all of zero percent (very large tails with probabilities near 50% dominate). So against a mildly malicious opponent you - on average - don't come out ahead. But that is an average across an infinite number of situations, every last one of which you came out ahead in. (Infinity has lots of strange stuff like this.)

      Again, the probability of your winning depends on the two numbers that I have. But it is always better than even. And you can guarantee that no matter how I tried to produce my numbers.

RE: Spooky math problem
by Compilers-R-Us (Initiate) on Nov 04, 2000 at 19:06 UTC
    Actually, you do. In order to generate a random number, you have to know the probability distribution. Therefore your original assertion was right, and my analysis was right. I didn't get it 100% last time. In the problem the probability distribution is the 'trivial' uniform, infinite distribution and with a mean of zero you can actually beat better than 50-50 odds with only the ability to generate a random number - you don't actually have to do it. If you are randomly given a second number without knowledge of the distribution, the result tells you something about the distribution again giving you better than 50-50 odds. I'm done!
      Please look at Spooky math - with Perl. You will see that the numbers I have are parameters to the experiment, the guesser uses no knowledge about numbers, and the trick is that the guesser is sometimes guaranteed of being right.

      The only limits to the guessing rule in that program are internal to how computers select pseudo-random numbers and the floating point math that Perl uses.

      Other incidental notes. Your "trivial" uniform, infinite distribution actually does not and cannot exist. Its not existing has deep consequences. The details of why not are covered in real analysis. In the US and Canada this would traditionally be taken either by an advanced 4'th year math student or a beginning graduate student.

      And random trivia. Not only is an infinite uniform distribution impossible, but attempts to look for really random numbers invariably turn up patterns that don't fit with a uniform distribution. For instance Benford's law states that the first digit obeys a logarithmic distribution. It isn't really a theorem, but other than that detail the following is a good introduction for the general public. Knuth tries to explain it in his series, but does not manage IMNSHO to show why his abstract model has anything to do with reality.

      Just thought I would throw that out there...

Re: Spooky math problem
by lidden (Deacon) on Sep 05, 2004 at 17:01 UTC
    Suppose I have two envelopes. All you know is that they contain different numbers. I randomly hand you one of them. You open it, look at it, then hand it back. You now have sufficient information to, with guaranteed better than even odds, correctly tell me whether I gave you the envelope with the larger number. How?
    No, that question actually is:
    If I give you a number from a set of two diffrent numbers tell me if you got the small or large number?

    My odds of doing that is exactly 50%.

    If you sit down and do the algebra, you will find that your probability of being right turns out to be exactly 50% plus 1/2 the probability that you pick a number between my two.
    Hmm. If I choose to guess myNumber + epsilon(where epsilon is small enough) I have 50% chance of being between your two numbers and hence have 75% chance of being correct, which is silly:-)

    Ok four years late but I got here from this node.

      Suppose I have two envelopes. All you know is that they contain different numbers. I randomly hand you one of them. You open it, look at it, then hand it back. You now have sufficient information to, with guaranteed better than even odds, correctly tell me whether I gave you the envelope with the larger number. How?
      No, that question actually is:
      If I give you a number from a set of two diffrent numbers tell me if you got the small or large number?

      My odds of doing that is exactly 50%.
      You'd think that your odds of doing that are 50%. It turns out that they don't have to be. This violates common sense, which is what makes the problem interesting.

      Mathematicians are very interested in understanding situations where their intuitions differ from what happens. By examining those "pathological cases" you sharpen your intuition for how things work.

      Note that in these weird boundary cases it is important to be very precise in your thinking. Any sloppiness will cause you to misanalyze the problem to fit your preconceptions, not reality.

      If you sit down and do the algebra, you will find that your probability of being right turns out to be exactly 50% plus 1/2 the probability that you pick a number between my two.
      Hmm. If I choose to guess myNumber + epsilon(where epsilon is small enough) I have 50% chance of being between your two numbers and hence have 75% chance of being correct, which is silly:-)
      And that is what sloppiness looks like.

      The algebra only works if your method of choosing the other number is independent of the number that you get. As soon as you introduce a dependency you have to analyze that dependency, and it changes the answer.

      Since you don't seem inclined to try the algebra, allow me to demonstrate what it looks like. Suppose that the numbers that I have are x and y with x < y. Suppose that p(z) is the function that tells you for any number how likely you are to think that you got the larger one if you're handed that number. Then:

      P(You're right) = P(You're handed x)*P(You don't think that x is larger) + P(You're handed y)*P(You think that y is larger) = 0.5 * (1 - p(x)) + 0.5 * p(y) = 0.5 + 0.5*(p(y) - p(x))
      So far we haven't introduced any details about the method. With the method that I described, though, p is a monotonically increasing function, in fact p(y) - p(x) is the probability that you pick a number between x and y, so you're better than even odds by half the probability that your number is between my two.

      With the choosing method that you came up with, you always conclude that you're handed the smaller number. Therefore p(x) and p(y) are both 0.5 and your odds of being right remain at 50%. Slight difference!

      If your eyes are glazing over at the algebra, then please examine the following (bad) ASCII art version of the picture that I described in my root node.

      (Right if handed the larger) | <----------------------------| (even odds) (guaranteed) | (even odds) <-------------x------------------y---------------> | |-------------------------------> | (Right if handed the smaller)
      As you can see, no matter what number you independently come up with, you never have worse than even odds of being right, and you have some chance of guaranteeing that you're right. That chance gives you better than even odds overall.
        In order for the envelope receiver to receive the benefit of additional odds above 50%, I think the receiver must come up with a random number before viewing the number in the envelope. Then given the number in the envelope they can determine whether to say high or low.

        Using tilly's ascii chart above; my guess is z, assume my guess in between x and y. When I open the envelope to reveal x, which is smaller than z, I will then say that I was handed the smaller number and I will be right. If I open the envelope to reveal y, which is larger than z, I will say it is the larger number and I will be right. If my guess z is smaller than x, I will be wrong when ever I am handed x, and right whenever I am handed y. Similarly if z is larger than y, I will be right whenever I am handed x and wrong when handed y.

        Now, if I look at the number in the envelope first, as a human, I am incapable of picking a truly random number not biased by that number. (Hell, humans are incapable of picking a truly random number period). So, I now have a 50-50 shot at deciding to pick higher or lower than that number. Which means 50% chance of deciding whether to say the received envelope number is higher or lower than the number in the other envelope. It no longer matters whether my 'guess' falls between the actual numbers anymore, because I can not receive the other envelope. Therefore, the odds are 50%. Only by choosing a number before the envelope is handed to you can you increase your odds however slightly.

        -Scott

Re: Spooky math problem
by SimonClinch (Chaplain) on Aug 30, 2005 at 13:39 UTC
    Another approach:- There is some additional information needed. 1) The smallest size per digit you are capable of writing the numbers, 2) the largest envelope size you are capable of acquiring, these collectively limit the number of digits the remaining number can have. For the sake of argument lets call it D. If the numbers in envelopes are M and N, with M being the one handed to you, then the probability that N < M is p=(M-1)*10^(-D). Because D is arbitrarily large, p is arbitrarily small.

    One world, one people

      First of all, no additional information was needed.

      Secondly you are implicitly assuming a probability distribution on the numbers in the envelopes, namely that it is evenly distributed among all possible numbers that could be written on the pieces of paper. This assumption is both wrong and unnecessary.

      Thirdly note that the technique must work no matter what pair of numbers happen to be in the envelope. Creating a technique which will work for 90% of the pairs that you think could be there won't cut it. It has to be all pairs.

        It is a well-known result from statistics that expectancy becomes undefined if the rule for randomness is ambiguous. So, of course a definition of randomness is necessary, otherwise the answer is simply 'undefined' for this case.

        In the absence of any particular definition ... oh forget it - I am clearly wasting my time here.

        One world, one people

Re: Spooky math problem
by tmoertel (Chaplain) on Sep 21, 2005 at 18:57 UTC
    The trick here – and there is a trick – is a subtle use of equivocation: You make a claim about one problem but then explain the claim in terms of another problem that is subtly yet significantly different.

    In the first problem, each envelope can contain any number. In the second problem, however, you require that the distribution of numbers have a "continuous probability distribution with non-zero density everywhere." These problems are not the same.

    To see why, imagine an infinite number line representing all numbers. If you pick any segment on this line, say that between 0 and 1, the portion of the line that the segment represents is zero. Hence the probability density function over the segment is also zero, which contradicts the assumption made in your analysis.

    If we repeat your analysis, this time using the distribution of numbers for your originally stated problem, we find that the probability of picking a number in between your two numbers is zero, and thus knowing the first number provides no benefit. Our intuition turns out to be correct.

      There is no trick.

      In the problem, each envelope can contain any number. The requirement of a distribution of numbers that has a continuous probability distribution with non-zero density everywhere is on the one you create for your algorithm. That number is made up out of thin air and has no connection to either of the numbers in the envelopes. The trick is that it gives us a chance of telling the two numbers apart.

      The probability density function that you are trying to describe, "uniform over the real numbers", is not a valid probability density function. It is a classic result both in real analysis and probability that it can't be. (The real analysis statement is that no such measure exists, the probability theory statement is that no such probability distribution exists. Those statements are the same.)

      This is why you have to be very careful in the wording to even get a well-defined problem. Given any two numbers and the algorithm, there is a well-defined probability that you're right, and that probability is over 0.5. Prior to the numbers and algorithm, the probability of your being right is undefined and undefinable.

      Again I'd like to point people to Bently Preece's excellent explanation. The goal of the question is to come up with a single strategy that will give better than even odds for every game in a particular class of games. And the described strategy does that.

      Now I haven't explained why this particular probability distribution can't exist. The technical reason is that the axioms of probability require the probability of a countable disjoint union to be the sum of the probabilities, and that the probability of the whole set is 1. But the real line is a countable disjoint union of intervals, each of which has probability 0 (for the reason that you explained), so the probability of the whole set is a countable sum of 0's, which is 0. Contradicting the requirement that it be 1.

      Now it is easy to object that one could just define probabilities differently. And it is true, one could. But any way you define it, you'll have a lot of subtleties around infinity, and attempting to think about a uniform probability distribution on the real numbers will be one place that you'll encounter lots of them.

      BTW in the USA this fact is generally covered in a real analysis class in advanced undergraduate or beginning graduate school mathematics.

        There is no trick.

        Yes, there is – even though it is probably not intentional – and it is equivocation. First, you say:

        In the problem, each envelope can contain any number.
        Here, you present "any number" as meaning "any number, with absolutely no restrictions." Later, however, you do place restrictions on the numbers by requiring that it be possible for a guessed third number to fall between two such "any numbers" with a probability of greater than zero:
        Given any two numbers and the algorithm, there is a well-defined probability that you're right, and that probability is over 0.5.
        In other words, you subtly (and perhaps unknowingly) redefined "any number" to effectively mean "any number within a finite range."
        This is why you have to be very careful in the wording to even get a well-defined problem.... Prior to the numbers and algorithm, the probability of your being right is undefined and undefinable.
        Precisely. Prior to the numbers and the algorithm, the probability of your being right is undefinable. How, then, did you arrive at a concrete statement about that probability? You redefined the problem to make it possible. You did it while explaining the "numbers and the algorithm," which made it harder to see, but you did do it.

        I'll say it again: The problem you originally presented and the problem you ultimately analyzed are not the same. The original problem's numbers were free of restrictions, but the analyzed problem's numbers were not. Two different problems.

        Cheers,
        Tom

Re: Spooky math problem
by polettix (Vicar) on Sep 26, 2005 at 14:58 UTC
    Hi, your link to the puzzle has to be updated, it now points to a nonexistent page.

    Nevertheless, I found the solution and also this discussion about the problem, but the solution is flawed IMHO. Apart from the fact that the author is arguing about the phrasing in the original solution, the algebra should be the following (quoted from one of the messages in the thread):

    P(correct guess) = P(we were shown the higher number H) * P(we guessed "high" given H) + P(we were shown the lower number L) * P(we guessed "low" given L) => (plugging in from the original selection method) P(correct guess) = (1/2) * (1 - F(H)) + (1/2) * F(L) => P(correct guess) = (1/2) (1 - (F(H) - F(L))) => Since F(H) - F(L) > 0 (by assumption) P(correct guess) = (1/2) (1 - (a positive value)) => Therefore, P(correct guess) < 1/2.
    What I find very amusing is that we're using two different values (namely H and L) to feed the F function, but this is not applicable. We have to use the same value - that is the value we figure out in our mind, let's call it y. This leads to:
    P(correct guess) = (1/2) (1 - (F(y) - F(y))) = 1/2
    as it should clearly be.

    Flavio
    perl -ple'$_=reverse' <<<ti.xittelop@oivalf

    Don't fool yourself.
      You've got it backwards. It should be
      P(correct guess) = (1/2) * F(H) + (1/2) * (1 - F(L))
      
      which does give you a probability > 1/2.
Re: Spooky math problem
by ikegami (Pope) on Mar 25, 2009 at 04:31 UTC
    One flaw: The guarantee fails if the enveloper contains two adjacent numbers. 50% + 0.5 * 0 is not greater than 50%.
      In standard mathematics there is no such thing as adjacent real numbers. Endless arguments from non-mathematicians notwithstanding, 1 and 0.999... are two different ways of representing the same number and not two different numbers.

      This is because one of the rules the real numbers follow is trichotomy, which says that if x and y are real numbers then exactly one of the statements x-y>0, x=y and y-x>0 must be true. (Depending on the axiomatization chosen trichotomy can be either an axiom or a theorem. Either way it is true.) The requirement in the problem that the numbers be different rules out the second possibility.

      In fact we can make an even stronger statement. There is a basic theorem (called the Archimedean principle) which makes an even stronger assertion, given any two distinct reals there is always a rational number between them. So let n/m be a rational number between 0 and x-y. Then x and y must differ by more than 1/m. So you see that between any two real numbers there is always a finite visible gap. There is therefore no such thing as an infinitesmal in the standard real number system.

      (Google will provide adequate references to demonstrate that I'm not just making this up.)

        (Google will provide adequate references to demonstrate that I'm not just making this up.)
        You hacked google to become a reference so it would appear that way ... ;P
Re: Spooky math problem
by wazoox (Prior) on Mar 31, 2009 at 20:38 UTC
    I can't wrap my head around this, however I know you must be right because I've read exactly the same problem (maybe with a slightly different story) from Martin Gardner, the famous headache-provider :)
Re: Spooky math problem
by oiskuu (Pilgrim) on Jan 08, 2014 at 20:07 UTC

    Here's my attempted proof. Please do not hesitate to correct me if it's insufficiently crazy.

    First, we need to gather the important bits of the puzzle:

    Suppose I have two envelopes. All you know is that they contain different numbers.
    The second crucial hint is more readily apparent in explications that follow, I quote:
    ... given any two distinct reals there is always a rational number between them.

    Okay. From the above, we now know that (a) the entertainer has two envelopes; (b) he passes you one of the envelopes, opening which you discover a piece of paper where a real number is written in its precise infinite glory. Clearly, this is a feat that only God could pull off.

    Having witnessed the magnitude of the Number, you are invited to make a guess. However, by the mere fact that we exist at all, we know that God is good. And omnipotent. It is therefore evident that whatever guess you may make, you are always correct! As God hands you the second envelope, it shall magically contain yet another piece of paper with yet another infinitely glorious and satisfactory Number. Unless maybe, perhaps, if you've been naughty?

Re: Spooky math problem
by hdb (Parson) on Jan 09, 2014 at 20:47 UTC

    In my opinion, this great thread still needs a simple Perl script to prove what's going on. Here it is, so that you can play the game yourself against the script. In order to avoid any confusion about the source of the numbers in the envelope you have to specify them as parameters to the script yourself. The third required parameter is the number of repetitions in the simulation to evaluate the odds.

    use strict; use warnings; use List::Util qw(min max); sub chose { my $x=shift; $x>0?1-chose(-$x):0.5*exp($x) } my ($a,$b,$n) = @ARGV; # provide numbers and repetitions on command li +ne my $ctr = $n; my $correct = 0; while($ctr--){ my $envelope = rand()<0.5?$a:$b; # pick an envelope at random my $answer = rand()<1-chose($envelope)?'low':'high'; $correct++ # count the correct answers if ( $envelope==min($a,$b) and $answer eq 'low' ) or ( $envelope== +max($a,$b) and $answer eq 'high' ); } printf"Correct ones: %20.17f%%, theoretical odds: %20.17f%%\n", 100*$c +orrect/$n, 50+50*(chose(max($a,$b))-chose(min($a,$b)));

    IMHO, the script is simple enough to prove that no cheating is going on.

    If you play with the inputs you can see that if you provide numbers that are easily distinguishable (by the chose function) the odds are significantly larger than 50% (for example choosing -1 and 1 will lead to odds larger than 80%). If numbers are less distinguishable like 100 and 200, the odds will converge to 50%, and the simulation error will be larger than the advantage.

    Great puzzle!

Re: Spooky math problem
by oiskuu (Pilgrim) on Jan 10, 2014 at 00:21 UTC

    If you want a good, counter-intuitive but concrete puzzle, allow me to direct you towards Monty Hall problem.

    Personally, I find this "spooky math" problem little more than a guileful parlor trick. It is vague and ambiguous. We don't really know the full setup. Possible choices lead to effectively different puzzles.

    In reality, both Contestant and Entertainer would have individual bias, and a very constrained range for their rand(). Assuming the Entertainer gets to choose his numbers, is he spiteful or sympathetic? Now it's a behavioral game with external factors.

    The abstract problem on an infinite number set is different. In this case, there is no strategy to take advantage of.

    The third scenario, two persons and/or programs acting it out—that's just a curiosity, a sleight of mind, a voluntary(?) deception.

Re: Spooky math problem
by oiskuu (Pilgrim) on Jan 11, 2014 at 06:07 UTC

    Considering and reconsidering the abstract case once more, it now admittedly appears very similar to Monty Hall problem.

    First, let's get rid of the red herrings and ambiguities. A random list needs no reshuffling: no need to pick an envelope. Generate the numbers, including the guess. Assume they are distinct. Now the roles of Entertainer and Contestant have become superfluous. Values of numbers are also irrelevant, only their order matters. All we are left with is six permutations:

    A < B < C .......... 1
    A < C < B .......... 1
    B < A < C .......... 0
    B < C < A .......... 1
    C < A < B .......... 0
    C < B < A .......... 1
    The favorable outcome is one where A (revealed number) is not between B and C (the guess). Comparing to the guess reduces permutations (to first or second half). The chances of winning are evidently 2/3. But increasing the number of guesses will asymptotically improve your outlook towards 3/4.

    So there is a strategy that works. Très bizarre.

      Can you please explain, how this relates to the original question? Where does the guess come from? The original question was to state whether it is high or low. Also, there is no way that the six cases you list have the same probability. If A and B are very close (whatever that means), C will not be between them with the same probability than outside.

        Quoting from here:

        The numbers x and y are part of the experiment. How they came to be is not part of the question asked, and therefore questions about how to choose them do not enter into the problem.
        Despite tilly's meticulous attempts to befuddle, bemuddle and obfuscate, there is an implicit assumption made. The numbers have a defined relationship, a comparison function. In the absence of further restraints, they form an open-ended (infinite) ordered set.

        Drawing elements from a finite set, randomly and without bias, yields n**3 equally likely hands. In this abstract case, the set is infinite. Elements are drawn from the same set because there is an (implicit) mutual understanding, and presumption of rationality.

      Sorry, you're skirting a ton of paradoxes in probability theory. This looks reasonable but isn't for the simple reason that there is no way to pick "a truly random real number". That probability distribution does not exist.

      In order to avoid paradoxes the problem has to be *very* carefully stated.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://39366]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (7)
As of 2014-08-21 12:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (135 votes), past polls