|Perl: the Markov chain saw|
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! :-)