# Can Information Rise From Randomness?

Quanta’s new puzzle column asks you to believe the seemingly impossible — that you can win at a number guessing game with absolutely no information.

Olena Shmahalo/Quanta Magazine

138

Greetings, Quanta readers! It’s a privilege to present this new monthly puzzle column. I look forward to sharing some intriguing puzzles with you.

A monthly puzzle celebrating the sudden insights and unexpected twists of scientific problem solving. Your guide is Pradeep Mutalik, a medical research scientist at the Yale Center for Medical Informatics and a lifelong puzzle enthusiast.

Solving puzzles is a quintessentially human activity — we are, after all, the only species that solves puzzles for fun. Like all puzzle columns, this one will primarily be an expression of that fun — a celebration of sudden insights and counterintuitive results, and an exploration of the new challenges that follow from those insights and deepen them. But in addition to fun, I also have a more serious purpose in exploring puzzles. I believe that puzzles are far more than a recreational activity. Some puzzles and their solutions can be seen as a microcosm of scientific progress, as readers build on each other’s comments and insights to discover something new, a process I experienced firsthand in many of my New York Times puzzle blogs. Puzzles can also deepen our understanding of scientific concepts, as in this puzzle whose solution provides insight into the second law of thermodynamics. And, as I argue in a recent Math Horizons article, I believe that our human love of solving puzzles is a reflection of the unique cognitive-emotional link that makes us the intelligent creatures we are. To coin a classically mixed neologism, we are Homo enigmatus — in more ways than one. Evolution has made us cognitive beings by giving us small internal rewards whenever we solve a puzzle — a very effective strategy.

So, as we solve these monthly puzzles, we’ll try to look deeper into their analytic content and their emotional denouements, but we will also search for connections between our puzzles and problems in various fields of science. We’ll also explore some fascinating overarching themes that hold inexhaustible conceptual riches. Today’s puzzle highlights two such themes: randomness and information.

Through a Random Looking-Glass

Alice laughed. “There’s no use trying,” she said: “one can’t believe impossible things.” “I daresay you haven’t had much practice,” said the Queen. “When I was your age, I always did it for half-an-hour a day. Why, sometimes I’ve believed as many as six impossible things before breakfast.”

—Lewis Carroll, Through the Looking-Glass

Today’s puzzle asks you to believe something that seems impossible — that you can somehow win at a number guessing game in which you have absolutely no information:

I write down two different numbers that are completely unknown to you, and hold one in my left hand and one in my right. You have absolutely no idea how I generated these two numbers. Which is larger? You can point to one of my hands, and I will show you the number in it. Then you can decide to either select the number you have seen or switch to the number you have not seen, held in the other hand, as your final choice. Is there a strategy that will give you a greater than 50 percent chance of choosing the larger number, no matter which two numbers I write down? (Update: The solution is now available here.)

Since you know nothing whatsoever about the two numbers, the only thing you can do, it seems, is make random guesses. But can randomness generate information?

Actually, randomness can be very powerful. When coupled with nonrandom selection and given enough time and iterations (such as in the process of evolution), randomness can exhaust almost all possible variations on a design, inevitably generating exquisite products that seem to have been planned with obsessive attention to detail. In some especially difficult problems, procedures called genetic algorithms, which simulate the interplay between randomness and selection characteristic of the evolutionary process, often provide better solutions than the best human experts. The crucial information that selection provides in this process is simple: It tells us which of two alternatives is better. Randomness, meanwhile, has the tedious job of working through a tremendous number of cases. So while randomness and selection are equal partners, the key information is provided by selection.

With no way to know which alternative is better, what can random guesses achieve? Well, you could guess correctly and, improbably, hit a jackpot. This happens to all of us from time to time, convincing some people that they can access information in unexplained ways. But such luck tends to even out in the long run. After thousands of trials, the expected outcome of guessing in our game above is exactly 50 percent, no matter how many lucky guesses you have. This seems like a dead end.

We know that randomness by itself is completely devoid of information. In Claude Shannon’s famous measure of the entropy of information, a random guess is considered to have maximum disorder and consequently an information content of zero. We decry as pseudoscience any attempt to get meaningful information out of events that seem to be random, as in astrology, palmistry, synchronicity, apparent telepathy, or Tarot card reading. The only way these methods could work is if the events are not really random but arranged in some way, perhaps supernaturally, to correspond to the information we want. And we have no reliable evidence of that in any of these cases.

Getting back to our puzzle, in real life you might guess what numbers I am likely to use from your knowledge of human psychology. But we have framed the puzzle as an abstract problem that explicitly denies any such knowledge: No information about the unknown numbers is available to you. I could be a robot or an alien, whose ways of thinking are absolutely foreign to you, or I might use an unimaginably wacky algorithm to generate my numbers. What now?

Since you have no basis to prefer the number in either hand over the other, your chances of guessing the larger one should remain stubbornly stuck at 50 percent. The problem is impossible to solve by purely logical means, right?

Wrong! I assure you that there is a way to bring your chances of choosing the larger number above 50 percent. If you were to bet a sum of money for each guess and receive even money every time you were correct, you would always come out ahead in the long run.

Your task is to find this magic method, explain why it works, and figure out where the information, if any, is coming from.

This puzzle was brought to my attention by my colleague Joseph Chang, a statistics professor and chairman of the Quantitative Reasoning Council at Yale University. Joe has a tradition of giving his students a parting gift in their last class. He presents them with “two impossible things to believe in before lunch,” thus getting them to practice the kind of thinking the White Queen recommends in Lewis Carroll’s Through the Looking-Glass. The above problem is one of those two impossible things.

Ready to achieve the impossible? Happy puzzling! And may the insight be with you.

(Hint: If you are completely lost and need something concrete in order to get your bearings, or you are just an intrepid soul who loves such things, below are some variants of the above problem to sink your teeth into. They just might guide you in the right direction.)

Bonus Questions

One strategy for tackling difficult mathematical problems, laid out in George Polya’s famous book How to Solve It, is to “consider special cases.” Here are some special cases for you to consider.

1. Let’s say we play this guessing game repeatedly, and I promise you that my two numbers will always be between 0 and 10 and randomly generated. What’s your best strategy now, and what is the best success rate you can achieve with it?
1. We play a variant of the first bonus game above, but this time my numbers are generated at random from some range of numbers that you do not know. What’s your best strategy in this case?
1. This time I offer to play you for money: I pay you a dollar if you correctly choose the larger number, while you have to pay me $1.10 if you don’t (to compensate me for the fact that in the original game you can succeed more than 50 percent of the time). I agree to use only decimal numbers between 0 and 10, using no more than three decimal places. However, the numbers are not generated at random: I will use whatever numbers I think will help me win the game. Should you accept this offer? 1. Now let’s get back to something resembling the original problem, where you know nothing about the range or the method used to choose the numbers, but in this case you do know that the numbers were picked by a human who is not trying to fool you or be adversarial. Would you switch to the number in the other hand if the number in the open hand is: a) 0.6; b) -5; c) 10,000? Have these extra problems changed the way you look at our original impossible puzzle? Feel free to express yourself in the comments section below. We’ll publish full answers in a couple of weeks. Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt. Update: The solution has been published here. View Reader Comments (138) Leave a Comment ## Reader CommentsLeave a Comment • I hope you’re not posting these until a set time later, so everyone can have the fun of trying to figure this out! Just wanted to mention that I’m super excited to see a new puzzle section in Quanta — even though I’m not a master puzzler, and in fact usually give up before reaching any sort of solution, I have some thoughts on a strategy that might be relevant for this one. The puzzle first reminded me of the Monty Hall problem, where a gameshow contestant is choosing between three doors. One has a car behind it, and the other two have goats. After choosing a door, the host or assistant will open another door to reveal a goat. Then, the contestant gets to either stick with their original guess or switch to the other unopened door. Statistically, they have a 1/3 chance of getting it right if they stay put and a 1/2 chance if they switch — a baffling proposition, until you consider that the contestant is getting additional information before one of the guesses. The host doesn’t just randomly open a door; he or she uses outside knowledge to open a door without the car behind it and thus narrow down the contestant’s choices. That’s why the likelihood is suddenly 50/50 if the contestant switches. (And yes, I have diagrammed this out to try to wrap my head around it, plotting all the possible situations of car locations and goat reveals. It sort of helped.) But in the case of this puzzle, no outside agent is revealing extra information — you pick a hand, the author reveals the number in his hand, and then you get a chance to switch. Especially when the numbers aren’t confined to a particular range, how on Earth does seeing one of the numbers even help you? Assuming one number can be objectively deemed larger or smaller than the other, we can assume that they’re real numbers — no square roots of negative one that stretch the number line to a number plane, or anything like that. In which case, every number chosen (although we don’t know how they’re chosen) will be either positive, negative, or 0. And that gives us something to work with. Consider a situation where the two numbers are chosen completely randomly, from all of the real numbers. We don’t know the algorithm for choosing the numbers, so we don’t know of any particular bias — this is the best we can do for now. Thinking about positives and negatives (and ignoring 0 for the moment), there can be four possible situations (+ meaning positive and – meaning negative): First number + and second number + First number + and second number – First number – and second number + First number – and second number – If you stay on the first number every time, you will have a 50% chance of getting it right: First number + and second number + — 50% chance first number is larger First number + and second number – — 100% chance first number is larger (+ always greater than -) First number – and second number + — 0% chance first number is larger First number – and second number – — 50% chance first number is larger If it’s completely random, for both numbers, there’s a 25% chance each of those scenarios will occur. So you get the odds: .25*.5 (first scenario) + .25*1 (second scenario) + .25*0 (third scenario) + .25*.5 (fourth scenario) = .5, or 50% chance of getting it right if you don’t switch. Same deal for if you always switch First number + and second number + — 50% chance second number is larger First number + and second number – — 0% chance second number is larger First number – and second number + — 100% chance second number is larger First number – and second number – — 50% chance second number is larger But what if you switch only when you see a negative number? First number + and second number + — 50% chance first number is larger First number + and second number – — 100% chance first number is larger First number – and second number + — 100% chance SECOND number is larger (and you switched, lucky you!) First number – and second number – — 50% chance SECOND number is larger Switching doesn’t help at all if both are negative, but in the situation, 1/4 of the time, where the first number you choose is negative and the second number is positive, you’re boosting your likelihood from 0% to 100% getting the right number. Your chances will be: .25*.5 (first scenario) + .25*1 (second scenario) + .25*1 (third scenario) + .25*.5 (fourth scenario) = .75 = 75% chance! Now, this depends on if they’re truly chosen randomly, and if you don’t get a 0. If you get a 0, I recommend screaming and running away or staying on the same number, whichever you feel like — the first, because why not add a bit of spontaneity to your life and the second because you always kick yourself more when you switch AWAY from the right answer, in my experience. Whatever you do, these edge cases shouldn’t mess up your score too much; just think of how unlikely a 0 is compared to the infinite (alpha 2 infinity!) real nonzero numbers. For that matter, it’s highly unlikely the choice was actually random and unbounded if you wound up with 0 for that same reason (it could be random but constrained to integers 0-10, for instance, or decimals to two places from -500.00 to 500.00; the former would make it much more likely for you to get 0 and would also make our strategy terrible). If the numbers aren’t random, but you don’t know the parameters, no particular strategy will be able to help you that I can think of — so might as well use a strategy that will work if it’s pretty close to random. As a sidenote: if you know the range and are assuming more-or-less random within that range, you should replace “positive” and “negative” with “greater than (median of the range)” and “less than (middle of the range)”, always switching if you get “less than (median of the range)”. I only say median because what if the numbers are like 1, 2, 3, 50000, 50100? Then you want to switch on 3, not some greater number that’s halfway between 1 and 50100. What you do when the number you choose is 3 is your own business. If, playing this game, you begin to get the creeping feeling that the author is messing with you, the numbers are following barely-discernable patterns, or you are guessing right or wrong nearly 100% of the time, all bets are off. It’s probably not random (or you are latently psychic), and you should apply that new information to derive a new strategy (or take over the world). If the revealed numbers are occasionally letters like A, figments of people you once knew, or abstract concepts like joy or shame, either something fishy’s going on or the author is cheating, and you should run away screaming as described above. Thanks, and I look forward to seeing how close I got! (Full disclosure: not that it makes me better at puzzles, but I have written a freelance article for Quanta, describing a Grand Theory of Wrinkles) • triga says: this is very problematic due to the nature of selection. has the number generator used simple rules to attain numbers (eg dates, years) or more complex rules (orders of magnitude difference). assessment of the first digit may reveal a hunch, similar to the monty hall problem in a way, whereby if the number reveaed starts with a large number (6->9), it may be a wise bet to stay, whereas if the number revealed starts with a smaller number, it may be wise to switch. this breaks down when two numbers of differing magnitude are selected (eg 9 and 101) or two of very similar magnitude (eg 91 and 99) • ger groeneveld says: A complete random process has a probability giving an certain outcome of 1/N, with N the number of possible outcomes. All sets have a median, though you don’t know what it is and finite sets, once one number is shown, have one number less, skewing the probability curve from a flat line to a slightly curved line with probability of 0 for the number to be higher/lower be the same as already showed A strategy is to fix the median at the number given and determine a new median from both numbers, first guess will always be 50/50 but one bet lost isn’t the end, now you know already 2 numbers from the set. If the following number shown is higher as the median but lower than previous shown number, chance is that the other number is lower than this one is a tad higher; if the number shown is higher than the previous high number, one has to reset the median value and take an educated guess if the other number is higher or not. Again it is random so it is unlikely that a previous number comes up again. Also now you know the distance between the numbers. giving you some more info from what solution line/plane/volume the numbers are drawn. I could describe this as a sample theorem combined with quicksort (to sort the distance between the numbers so to find the algorithm used to draw the numbers ) • Samantha says: In order for any strategy to guarantee better than 50% odds, the game must include the stipulation that the two numbers are generated independently. If this is not the case then the author can simply randomly select which hand’s number will be higher, and generate two numbers accordingly. • Marcelo says: The method proposed by Sarah L will works if the number assigned to the second hand is drawn independently from the number assigned to the first hand. However, the game allows the existence of arbitrary relationships between these numbers. For the most general case, we can play the game several times and keep track of the outcomes (this is how we gain information about the drawing method). Let’s call A and B the numbers observed on the first and second hand, respectively. After many trials, observing A in the current game we can compute the probability of observing B>A ( P(B>A) ) as the fraction of previous outcomes where B was greater than A. The computation of P(B>A) is problematic if we haven’t observed A among the previous trials. For this, we can use as surrogate of A previous outcomes where the value of the first hand was the closest to A. Let’s call this surrogate: A_s. Thus, we can approximate P(B>A) as P(B>A_s). Thus, if for the current game we are given A we choose the second hand if P(B>A)>0.5, or we choose the first hand otherwise. Cheers, Marcelo • Jason says: Although the problem setup says that the two numbers are random and that the method by which they are selected is unknown, it is not true that there is no information contained in the problem setup. We know that there are always a pair of numbers, and we know that one of them is larger than the other. Thus, let us consider the following selection procedure: Prior to selection, choose some arbitrary threshold. Choose one of the numbers at random. If that number is greater than or equal to the previously chosen threshold, keep it; otherwise, switch to the second. Since the numbers are drawn from some totally ordered set and we know ahead of time that they are not equal, then there are three possible outcomes. If both numbers are smaller than the threshold, we will always choose to switch, in which case the probability of winning is 50% (since the initial choice was made at random). If both numbers are larger than the threshold, we will always choose not to switch, and again the probability of winning is 50%. If one of the pair is smaller than the threshold and the other is larger, then our winning probability is 100% (since in this case we will choose to switch if and only if our initial choice was the smaller of the two). Thus, given this process, our probability of winning is: P[win] = 0.5*P[smaller] + 0.5*P[larger] + 1.0*P[split] = 0.5 + 0.5*P[split] where P[smaller] is the likelihood that both numbers are smaller than the threshold, P[larger] is the likelihood that both numbers are larger, and P[split] is the likelihood that one is smaller and the other is larger. P[split] is, by definition, greater than or equal to zero, so P[win] is at least 50%. However, it is possible for P[split] to be zero if the threshold is chosen in such a way that both members of the pair will either be always smaller or always larger than the threshold. Thus, we must choose the threshold in such a way as to preclude this possibility. It is important to note here that, while we have no knowledge of how the pairs of numbers are being generated, we are likewise free to select our threshold arbitrarily (and the process which selects the pair of numbers has no knowledge of the process we will use to select our threshold). Thus, so long as our threshold-generating process has some chance at producing a threshold between the two numbers – a chance which can be guaranteed by choosing the threshold at random from a distribution with non-compact support – then we guarantee that P[split] is greater than zero, and therefore that P[win] is greater than 50%. • Toby O'Donnell says: It seems to me that what is in question here is not the random nature of probability and mathematical equations, but rather the tendencies of human nature as to how they naturally arrange things. The selection process of the numbers is inconsequential, as is looking at one hand to see what number in that one. Evaluating these things will not increase your chances of guessing WHICH HAND HOLDS THE RIGHT NUMBER, which is the only important factor. And that answer is the right hand. In most languages words and numbers are arranged, and read from left to right. Therefore it is human nature to naturally, and unconsciously arrange numbers from left to right. The person holding the numbers will be reading them, and therefore is more likely to hold the smaller number in the left hand and larger number in the right. First guess should always be the right hand. Repeating the procedure with the same person then becomes more of a “poker duel” as to how well you know the person holding the numbers, and whether or not they are likely to change the hand that holds the larger number just because you guessed right. Repeating the procedure with different people, go with the right hand. • jon says: I don’t see how to do better than 50% on the first try, but on the second and later try one can take the median of all the numbers seen so far and use that as an estimate of the median of the distribution being used. However, that approach would consistently fail if the person selecting the numbers gradually increases or decreases the numbers being chosen. • Jonathan says: I propose an argument based on some notions from game theory, as we suposse that a player which will take the role of the questioner who knows the solution of the game and has no strategies, any strategy choose by the player 2 which is made to take any of the two random numbers can be discussed with the following : he can surely assume that the questioner already knows the answer, so his strategy would be motivated for him to loose the less, if we are aware that the questioner does not realize about players 2 strategy and since he knows the answer, he is not able to change any strategy, player 2 knows little about the two events, he only knows that one of the two random numbers is bigger than the other, as said before, the questioner posses this information. But the argument does not conclude here, player 2 has two strategies, the questioner does not know anything about game theory, although he knows the solution, he is not able to guess about players 2 offensive, and that one of the strategies is the solution itself. Nevertheless, as players 2 strategy is motivated on the above mentioned,the problems solution is not adress completely.Maybe a solution could be reached through an inverse method. • Marcelo says: Jason’s method is correct, and is more general than mine as it doesn’t need a training sequence of games (also, I just discovered that the method that I previously proposed is bound to fail under some rules to assign numbers). Jason, good luck trying to get truly random numbers though 😛 • Dan Shepherd says: I would pick the same hand every time. From this I could interpret generalized information about the person/equipment used to select said numbers, inherent consistencies, ranges and qualities. The more information I gather greatly increases my ultimate ability to predict the outcome. • There is information. It’s obtained when you determine the number of times you attempt to pick the higher number, and it’s represented by N. We are just trying to pick the higher number(H) more than 50% of the time. In each of our attempts at picking H, we are either going to be right or wrong. we need to know HOW MANY WAYS we can get that 50% +. That’s where N comes in. For example, say we have 4 attempts(N) at picking the hand with the high number(H). To simplify things, I’m always picking the same hand to represent H; never switching. I need to know how many out of the 4 attempts(N) can be H, and how many different ways can I get H in those 4 attempts(N). This gives me the probability: N! / H!(N-H)! ex. # of H #of Ways 0 1 1 4 2 6 3 4 4 1 If I wanted to know the probability of getting the high number(H) two times, out of 4 attempts(N): I would take the # of possible ways to get H twice in 4 attempts, and divide it by the total of ALL possible ways of getting H in in those 4 attempts: 4! /2!(4-2)! = 24 / 4 = 6 ; 1+4+6+4+1 =16; 6/16 = .375 A quicker way to get the probability would be: N! /((2^N)(H!(N-H)!)) So, all the information you need IS in the question. You get the highest probability at half the number of attempts(guesses)… And good gravy, does anyone remember my point? Someone check my math. I’m just a musician that is fascinated by small, sparkly objects, and was distracted by this article. • Andrew E says: “Is there a strategy that will give you a greater than 50 percent chance of choosing the larger number, no matter which two numbers I write down?” Yes: choose the Left hand, then switch and choose the Right hand. You have thus chosen both hands, and so with this strategy your probability of choosing the larger hand is 100%.( The question as phrased never explicitly states that only the final-choice counts as a “choice”.) In case the above solution doesn’t count (damn sticklers…), I’ll go with “compare the number you see to the running median of all numbers you’ve seen in previous attempts”. This strategy assumes the numbers are pulled from a well-defined probability distribution (it is impossible to pull random numbers from the entire Real line uniformly), which is probably a fair assumption. • James McDonald says: While Jason’s method is theoretically correct, it’s easy to see that the expected percentage is unlikely to be more than a *very* tiny fraction above 50%. For example, I could start with X = Ack(Ack(Ack(Ack(1000)))) in one hand (where Ack refers to Ackerman’s function) and X + 1/X in the other. That’s a very tiny needle in a very large haystack. After that, I keep moving dramatically faster out, by some random factor, perhaps also randomly flipping positive/negative, while also dramatically reducing the delta. The naive mathematical probability of success multiplied by the number of attempts you could make in this universe would produce a number that differs by far less than one from the value you’d get using 50%, which raises rather deep philosophical questions about the meaning of probabilities. • John Bailo says: Perhaps the bonus questions are more than generous. All random number generators are up against real world constraints. One of this is the pool of numbers from which they choose (otherwise it could take infinite time to generate an infinitely long string of digits thus making the game impractical). If you can over time by tracking the maximum number revealed estimate the upper bound of the number set, then perhaps you can use a rule where you figure whether the first number is in the upper or lower half of that range. If it’s in the upper, then it’s more likely the next number is in the larger pool of lower numbers, and vice versa. • shane says: (In all of the following we assume the thing producing the numbers does so without replacement.) Let’s say we play this guessing game repeatedly, and I promise you that my two numbers will always be between 0 and 10 and randomly generated. What’s your best strategy now, and what is the best success rate you can achieve with it? Ans: The intuition here is that all numbers in [0,10] have same probability, however, by knowing the bounds and information revealed by selection you can adduce additional information: Randomly choose either hand. Let N be the number revealed. We now break the bounds into two internals [0,N] and (N,10] and observe that it’s more likely to have a bigger number in the bigger interval since there are more ways to choose larger numbers. By cases: if the number 5 keep it if the number is exactly 5 randomly choose [flip coin] to keep it. Provided the oracle does not supply 5 infinitely often the non-5 numbers will help push the overall win percentage > 50% We play a variant of the first bonus game above, but this time my numbers are generated at random from some range of numbers that you do not know. What’s your best strategy in this case? Ans: The author points out that that we’d always win “in the long run.” So it won’t cost us too much to throw away some guess on the front side of the game to make up on the back. This scenario is like above except we do not know the bounds. So we simply waste guesses trying to find the bounds. Do the following K times: (a) randomly select the left or right hand. If on guess K=1 or if the number was smaller than the smallest number ‘m’ seen so far assign that number to m. (b) as you update ‘m’ update ‘M’ which is the maximum seen so far. After K iterations you’ll have boundary [m,M]. You can increase the level of confidence that m and M really are the bounds by making K bigger. Then this reduces to the game (1) in which m=0, M=10. This time I offer to play you for money: I pay you a dollar if you correctly choose the larger number, while you have to pay me$1.10 if you don’t (to compensate me for the fact that in the original game you can succeed more than 50 percent of the time). I agree to use only decimal numbers between 0 and 10, using no more than three decimal places. However, the numbers are not generated at random: I will use whatever numbers I think will help me win the game. Should you accept this offer?
Ans: No. Argument: There’s something like 10,001! ways the oracle could sequence the numbers for our selection. For a particular iteration of the game the left hand could hold the Nth element of the Ith permutation and the right-hand the N+1th element. The key point is that the probability of the element in the right hand being the higher than the left is still the first game. If the left hand has .001 the other hand can only contain .000 with probability 1/10,001 so as with the first game choose the right hand. In order to come out ahead we need to at least break even:
A*1 – B*1.10 = 0 -> A/B = 1.10 where A # of correct guesses, B # of wrong
That means the number of right guesses has to be 10% more than the number of bad guesses to break even and even more to out right win. Ex. 10 wrong guesses requires at least 11 guesses to break even. But A + B = 10,001 guesses so this implies A ~= 5238 and B ~= 4763. But the algorithm only guarantees us A = 5000 over the long haul. Even if we remembered each point chosen and thus could refine the probability of what remains unseen I don’t see how we could improve enough.

Now let’s get back to something resembling the original problem, where you know nothing about the range or the method used to choose the numbers, but in this case you do know that the numbers were picked by a human who is not trying to fool you or be adversarial. Would you switch to the number in the other hand if the number in the open hand is: a) 0.6; b) -5; c) 10,000?
Ans: The only way I think I could figure out a decision algorithm is to spend K guesses where K might be a big number and attempt to find the absolute range. Then I could break the range M-m into N parts and spend L more guesses per interval L/(M-m) to see assess what the range and frequency of numbers was. Then I could fall back to game 1.

• Denis DeFrancesco says:

Pick the same hand

• Amin says:

(Edit)
This can be compared to rock-paper-scissors’ game. But instead, we only have two possible choices. (Left hand, Right hand) Science confirmed that there is a winning strategy for rock-paper-scissor which I think we can also use in this game. So there are two players. The one guessing the numbers, and the one holding the numbers.

Study shows that “if a player wins over her opponent in one play, her probability of repeating the same action in the next play is considerably higher than her probabilities of shifting actions.”

In rock-paper-scissor… If a player loses two or more times in a row, he or she will not play the same sign, but will instead play whichever sign would have beaten the one that had just allowed his or her opponent to win. So in this game… if Player A (the one holding the numbers) has been on a losing streak, and Player B (the one guessing the number), just guessed it right to beat A, A will likely switch the larger number in the other hand, which stands a good chance of winning since B is likely to stick with his previously won choice anyway. This is called the “win-stay, lose-shift” strategy.

• Mark says:

If the first digit of the number in the hand chosen is under five, pick the other hand.

• Kerberos says:

…generate a third random number…make a rule that if the revealed number is smaller than your number, the hidden number is the larger…and if the revealed number is bigger then the hidden number is smaller.

This guarantees a win IF the random number you generate falls between the two original numbers. Over time you are guaranteed an advantage.

• Lincoln Phipps says:

When we receive a random event then as random events have a high entropy then the maximum uncertainty in the receiver is resolved and so the information is the maximum.

As an example with a fair coin toss, when we learn of the outcome then we have received 1 bit of information. If the coin was both sides heads then we would receive no bits of information.

Though the author seems to do some mathematics he’s a bit loose with his wording when he says, “We know that randomness by itself is completely devoid of information. In Claude Shannon’s famous measure of the entropy of information, a random guess is considered to have maximum disorder and consequently an information content of zero. ”

Well that’s just wrong and messing up entropy with disorder and then throwing in a so-called “random guess” is just absurd as humans are appalling at doing “random”. He later inserts “meaningful” information into the paragraph without understanding the implications of this from a mathematical point of view.

As an example, any one individual atom of radioactive isotope decays at random but it is absurd to say that when one of those random decay events occurs that no information has been received and it is as equally absurd to suggest that this decay event is not meaningful. For example when bismuth metal decays then that event is meaningful to the researcher waiting for the alpha decay to happen given the half life is a billion times longer than the age of the universe.

That whole paragraph of his is really just too wrong to fix. Pradeep Mutalik needs to remove it.

• Liam says:

You do not have “absolutely no information” – you have the first number. You can use this as a “guide” to the range of possible numbers. So if the first number is between 0 and 9, then you assume the other number is also less than 10, and guess accordingly – lower for numbers 6+, higher for 4 and below, random pick for 5.

If the number shown has two digits, then you assume a larger range of possible numbers, and guess accordingly. If it is a high number in the range of digits given, pick lower. I.e if the number displayed is 89, you pick lower.

In this, you are using an application of Benford’s law, about distribution of first numbers. This method will fail many times, in the first example, if you’re actually choosing either 0 or 1 and show the 1, say. But you’re looking for a method that gives you an edge over all the possible games played, and I would say this does.

Things get rather more interesting if the first number revealed is zero. I suspect most people would then say “higher”, but if negative numbers are allowed, (as per an example above) then I’d say zero is the one time the first number revealed gives you no useful information.

• Spiros M. says:

This is probably a silly observation, but one way to see that there is a forced interval within which the numbers lie is to consider the size of the author’s hands. If he is to hold up the two numbers, he must be able to write them down somehow. There is a wonderful post by Scott Aaronson on how to write down extremely large numbers on a small piece of paper given a finite time constraint (http://www.scottaaronson.com/writings/bignumbers.html). So, let us assume that the largest number that the author can write on a piece of paper and hold up is N (up to a negative sign). Then the effective range is [-N,N]. Choosing the threshold to be 0 (using Sarah’s and Jason’s ideas), you have the probability of a split (one number being larger and the other smaller than 0) being nearly 50% (0 itself breaks the tie). If Jason’s calculations are correct, then the total probability of winning is 0.5+0.5*P[split] ~ 0.75 > 0.5.

• Garrison says:

I am in no way qualified for this discussion, but I would say that true randomness cannot lead to information, since information is something attributed by intelligence, and since true randomness requires an absence of intelligent input, it cannot truly create information.

• Amin says:

(Edit) My other answer. First, make random guesses. Take note of the highest number that you see and the lowest number. Divide the highest number by 2 and the lowest number by 2. Add the lowest number’s quotient to the highest number’s quotient. That will be your 50% mark. Example, the lowest number you recorded is 2 and the highest number is 10. 10 /2 = 5 (highest number’s quotient. 2 / 2 = 1 (lowest number’s quotient). Add HQ and LQ. We get 6. 6 is now the 50% mark. It’s the number that is between 2 and 10. So if you chose a number from a hand to see, and it is above 6, stick with it. If lower than our 50% mark (which is 6), choose the other hand. If it’s higher than our recorded highest number, or lower than our recorded lowest number, replace our recorded numbers with it. Then find our 50% mark again.

• shane says:

(This site needs a edit-old-post-button to avoid making corrections needlessly spread over 10 places.)

Earlier I wrote the following in response to the author’s first question:
“By cases: if the number 5 keep it if the number is exactly 5 randomly choose [flip coin] to keep it. Provided the oracle does not supply 5 infinitely often the non-5 numbers will help push the overall win percentage > 50%”

Note sure why it appeared so; it’s garbled. It should read:

Randomly choose left hand or right. The selection of the highest number proceeds by cases:
(a) if the number is > 5 keep it.
(b) if the number is < 5 choose the other hand
(c) if the number is 5 flip a coin to accept or reject

And on the the last scenario "Now let’s get back to something resembling the original problem, where you know nothing about the range or the method used to choose the numbers, but in this case you do know that the numbers were picked by a human who is not trying to fool you or be adversarial. Would you switch to the number in the other hand if the number in the open hand is: a) 0.6; b) -5; c) 10,000?" my answer was just plain sloppy. Let me try that again.

If we don't know bounds or the shape of the probability distribution then my proposed strategy is to spend K guesses looking for the absolute bounds as with scenario two. Then we break the absolute range (M-m) into L pieces where L can be made as large as desired. For each piece or segment L/(M-m) we spend J more guesses per segment determining how many numbers occur in that segment. With this information in hand we then return to the game play like scenario one. Any revealed number must occur in a segment. From the earlier work we'd know the probability of higher numbers in all the segments to the right of the selected segment and to the left. It's then a matter of choosing the higher side.

• Burton Voorhees says:

While not offering a solution to this question, I want to comment on your statement that since Tarot cards layouts are random, they provide no information. This is incorrect. Why? Because each card has a defined meaning/interpretation and the person involved will project from their experience based on that meaning. They constructs a meaningful interpretation based on their particular background, within the framework of the question that led them to consult the cards in the first place. The cards and the form they are laid out in act as what Dennett calls intuition pumps, or as organizers. This is somewhat like the idea that by listening to the sound of wind blowing (more or less randomly) through a tunnel one can work out the dimensions of the tunnel.

• Nelson says:

I agree with those who say to take a running average of all the numbers, then if the number is smaller than this switch, if larger stay. There has to be a bound somewhere; a random number taken from the infinite set of numbers is meaningless as it will be infinite itself. To those commenters who say something about using psychology to “outsmart” the person presenting the numbers, this is explicitly declared to be immaterial in the article in this paragraph from the article:

“Getting back to our puzzle, in real life you might guess what numbers I am likely to use from your knowledge of human psychology. But we have framed the puzzle as an abstract problem that explicitly denies any such knowledge: No information about the unknown numbers is available to you. I could be a robot or an alien, whose ways of thinking are absolutely foreign to you, or I might use an unimaginably wacky algorithm to generate my numbers. What now?”

• Phaedrus Bùxiu says:

Assume no restrictions on the range of the numbers. If the revealed number is positive choose high, if it’s negative choose low. Across trials use Bayes Filtering to restrict the actual range of the numbers in play, then adjust high or low plays based on predicted maxima.

And since the answers are judged on a criteria of most interesting: wouldn’t it be cool if one could put their eyeglass prescription into their webcam’s options so that it adjusts their screen’s output?

• Jeremy Magland says:

For simplicity, let’s assume the numbers are non-negative integers (the solution may be adapted in the more general case).

Take the first number N, divide by 4, and look at the remainder. If the remainder is 0 or 1, then it’s probably smaller than on average, so pick the other number M. Otherwise, if the remainder is 2 or 3, then it’s probably larger than on average, so select the original hand.

The denominator “4” could be replaced by another even number (see bottom), but it’s important to pick the number “4” BEFORE playing the game. Otherwise we could be biased.

If the integer part of N/4 is the same as the integer part of M/4, then we have a greater than 50% chance of winning (you can do the calculation)! Otherwise, all bets are off, and there is no reason to think that we wouldn’t have anything other than a 50% chance of winning/losing. Therefore the probability of winning is either 50% in the worst case and greater than 50% in the best case. Overall the probability is somewhat greater than 50%, depending on the probability of the first condition.

If the numbers can be positive or negative, then just take the remainder such that -8 goes to 0 and -7 goes to 1, etc. If the numbers are real, then just look at the integer part.

Of course, the person could choose a scheme where we would have a less than 50% chance of winning, if they knew what our strategy was. Therefore, it might be useful to replace “4” by a random even integer, so they would have no way of guessing. But this gets tricky. If I wanted to be super-conservative (only wanting a slightly greater than 50% chance of winning) I would do the following….

Choose the denominator to be a random even integer between 0 and 10^100. That should be safe. 🙂

• Geojenks says:

If the numbers are generated effectively randomly, then their actual values are meaningless. The problem with Sarah L’s solution is it assumes a median of 0 (and therefore even chance of +ve or -ve) — there is no reason why this would be true.
If I know how many games I’m playing in advance, let’s say 500,000, then I know there will be 1,000,000 numbers in the game. I can substitute the random set for an ordinal one. This is where the information comes from, I have created it myself; “larger” is a completely arbitrary property to a random set, I have ordered the set by applying this. I have favoured larger numbers, much like evolution favours appropriate characteristics, arbitrarily.
The set can be considered fatalistic. With a predetermined, unknown median. Or it can be considered to have a dynamic median. Either way, by the end of the game the set will inevitably have a median (between the middle 2 numbers) with 500,000 numbers either side of it.
Using this, you can run a fairly simple simulation. The simulation generates a random sequence of the numbers from 1-1,000,000 (1 is used instead of the lowest number, 2 for second lowest…) and it also calculates the dynamic median (median of all the numbers so far) after a short while, the median is likely to be close to its final value and thus useful for predicting whether the next number will be higher or lower.
—- I ran this simulation in Excel 10 times with numbers from 1-100 and after 26 iterations (13 of these “games”), all of the simulations (except 1 which took 40 iterations!) were within 10 of 50.5 –the final median, which makes the dynamic median useful for the last ~75% of the games.

• Dan says:

If both positive and negative numbers are allowed, and there is no outer limit to the range in either direction, then zero becomes the midpoint. Using the 0-10 range as an analogy, zero would be the 5. Therefore, if the hand you select is a positive number, you should keep that hand as the higher number. If the hand you select is a negative number, you should select the other hand as the higher number.

Back to the 0-10 analogy, a positive number would be 6-10 and a negative number would be 0-4.

• stevenzakirov says:

Since these numbers can be generated randomly or picked intentionally you will encounter both cards ( if you have chosen none yet ) as wavefunctions that are evolving in respect to schrödingers equation through time , relative to you. The person who owns the cards in his/her hands collapsed this wavefunction relative to himself or herself. To know with more than 50%( if you already have one number) certaintly which number is greater is to observe the other wavefunction if possible. If you can’t , well you have to guess based on the log of the number of numbers available.

• Dustin says:

The most interesting element of puzzles (and subsequent discussions) like this is the assumptions people project onto the problem before they even begin to solve it. Some people are assuming that the process is discernible with time and data (in other words, the numbers chosen are not truly independent), some that at least the edges of the range may be discernible, some even assume only positive or whole numbers are in use.

The only assumption that seems to be needed to solve the puzzle is that we are only using real numbers (discerning “larger” with imaginary numbers would be at the very least complicated). Since we don’t know the process, we can’t say that the process is even consistent from round to round. We might be pulling data for hours/days before truly having enough data to validate our hypothetical model.

Based on special case 4, we can safely assume that negative numbers are allowed as well. If so, the simplest and most straightforward solution is as Sarah L and Dan pointed out, if the number seen is positive, select it, otherwise select the other number. If only whole numbers are used, there are 2x more possibilities (where x is the absolute value of the chosen number) to be right rather than wrong. Compared to the infinite number of positive whole numbers (or half of the number of all whole numbers), that difference is infinitesimally small, but it is more than 0 (unless the chosen number is 0 of course). If you use all real numbers, we have 2x infinities (# of real numbers between 0 and 1) to add to the infinite number of positive real numbers (reminder: different size of infinities here).

As for the special cases, 1 is straightforward enough, simply replacing the infinite range with a finite range, in this case treating 5 as the midpoint (i.e. if above the midpoint, keep, if below the midpoint, switch). 2 seems to require a sufficient number of guesses to reasonably determine the range, then treat the midpoint of the range as zero , but reevaluating whenever a number outside the estimated range appears. 3 is a fist-fight waiting to happen. The opponent should choose 2 numbers 0.001 apart. Unless they choose 0 or 10, which they shouldn’t, there will be an even chance that you will win or lose, and your opponent makes money over time. In other words, I’ll stick to the slots, thank you. 4 should have you switch on b only (a is close, but the slim chance is better that the other is lower than higher).

• Tom says:

There are tons of good strategies above that make some distribution assumptions due to past information, and I think the crux of those working is that your very worst case is that the information you have already gathered is useless. In this very worst case, you’re expected to win 50% over the long-term. If there’s even a chance that your observations are or become reflective of some–any–underlying mechanics for the number selection or hand selection or whatever, you just boosted your win probability above 50%.

If there’s a chance the observations are informative, then your long-term probability of being right in a given round is necessarily >50%.

• shane says:

@Dustin writes,
“The most interesting element of puzzles (and subsequent discussions) like this is the assumptions people project onto the problem before they even begin to solve it.”

Problems one and three have explicit boundaries in the givens. Problems two and four don’t. But problem (2) has a finite number of known elements also in givens. Nothing is said how about the numbers are generated in 2 or 4. True. But the author also writes the oracle producing the number is fair and is not adversarial. I infer a “generating function” possibly quantum is being used to supply the number and thus it is not totally with merit to attempt to spend guesses attempting to guess the probability distribution. In some natural phenomenon, for example, it would hardly be surprising to see a Gaussian one. That indeed is strongly relevant data.

• Jamie says:

Always pick the other hand no matter what number was revealed. This method won’t always give you the bigger number but over successive trials you will have a greater than 50% probability of getting the higher number. This is basically the ‘Let’s Make a Deal’ puzzle. On that show the contestant is shown door number one and then asked if they want what’s behind door number two. Always pick door number two. Why? Because the value of what’s behind door number two is either lower, equal or higher than door number one. That’s three possible states, two of which are ‘positive’ outcomes and one is ‘negative’. Therefore the contestant has a 67% chance of something as good or better if they pick door number two.

In the ‘number in the hand puzzle’ you should always pick the hand not revealed (i.e. door number two). Since the numbers were selected randomly from the full set of real numbers you still have three possibilities – the unrevealed number is either smaller, equal, or larger than the revealed number. The chances of the two numbers being equal gets smaller as the size of the set/series gets bigger, but nevertheless this possibility still tips the scales in favour of not finding a number smaller than the one revealed.

In short – always pick door number two.

• Josephus says:

Hmm, I must have misunderstood something, because this seems trivially simple.

If I just keep a running average of all the numbers I’ve seen during my guessing, then all I need to do when guessing is to keep the first shown number if it’s above that running average, but switch to the second hidden hand if it’s below it in order to maximize my possibility of winning.

That’s not correct, I screwed something up, I feel it in my bones. 🙁

• James McDonald says:

A wrinkle that no one seems to have noticed is that according to the given rules, the player choosing the numbers can presumably use all past guesses as part of their number generation.

That’s theoretically a bad strategy, though, because it allows the guesser to exert some control over the process. Even if that control is done unwittingly, a Bayesian update given sufficient time would probably figure out how to exploit it.

On the other hand, since we (the chooser) are only human, and subject to human foibles, maybe an argument could be made that the generator could take advantage of our inherent human predilections to persistently thwart us.

This particular consideration would seem to boil down to a question of whether we as the chooser have access to the same kinds of unbounded computational power ascribed to the generator.

• carla wood says:

The moment the first card is revealed you gain information. With that information alone it would increase your chances. I would take the number reveal and determine what the logical probability would be … for instance say the number was 58 … I would start by guessing that the other number would be lower … and therefoe gaining information with each guess … I believe that just because you lack the information needed to solve the problem doesn’t mean that information is not obtainable.

• Jeff B says:

Let’s consider four cases:

1. What if the game is played for only one round? (There is nothing in the description that says it’s a repeated game.) This is really challenging because we can’t use statistical inference to discover anything about the probability distribution. But there is one thing we do know: that the author has *written down* the numbers. Due to the infinite range of numbers that exist, the vast majority of numbers (asymptotically all of them, in fact) are too large or complex to be written down. This is still true even if we allow special notations and even if we allow them to be “written” using every particle in the universe. So by knowing that the numbers have been written down, we are restricted to the very small subset of numbers that are writeable. And sadly, in the absence of being able to make inferences about psychology or how long it took to write down the numbers, that’s all we know. So we have to assume that the numbers are drawn uniformly from the set of writeable numbers. Fortunately, this is a distribution centered around zero (since the set of writeable numbers is finite, and every writeable positive number can be converted to a negative by putting a minus sign in front of it). That means that statistically if your number is positive, more of the possible numbers are below it than above it. So in the case of only one round of the game, I’m going to go with keep your number if it’s positive, and switch if it’s negative.

2. What if I can keep playing as many rounds as I want? Here you should guess randomly and simply quit when you’re ahead. It’s easy to show that this is a winning strategy. I’ll be right on my first try exactly 50% of the time. And I’ll be {wrong, right, right}, which is winning overall, 12.5% of the time. So those two cases together show that I can come out with a winning record at least 62.5% of the time, before we even consider the long tail of other cases like {wrong, wrong, right, right, right} etc. I just have to have the discipline to stop when I accumulate a winning record.

3. What if I have to play as many rounds as the game host demands? In this case I’m probably screwed, since it’s the opposite of Case 2 above. However, if the number of rounds is fixed in advance, see Case 4 below.

4. What it I have to play a (pre-specified) large number of rounds, or an infinite number of rounds? In this case, as others have already commented, you should use statistical inference to build up knowledge about the true probability distribution, then start applying that knowledge to pick the first number that appears to fall in the top half of the probability distribution. Eventually you should accumulate a winning record.

• Scipio J says:

It appears to me that while it may be possible to win with a probability of more than 50 % — nevertheless I am convinced that there is no positive number epsilon such that I can win with probability 50+epsilon %.

Namely, most of the strategies discussed involve the history of the game and the magnitude of the first number. This is the only information available, but it is not enough to win substantially: The first player can always bring the impact of history and the magnitude of the first number under any given threshold by first picking a sufficiently small interval (say a subinterval of [0,1]) at random, and then taking two random numbers from that interval.

Hence the information given (history + first number) is not sufficient for the second player to bring the probability to win above 50+epsilon %, for any positive epsilon.

• Jeremy Magland says:

Here’s my second attempt! Assume for simplicity the numbers are positive integers (other cases can be handled in similar way).

Flip a coin repeatedly until you get heads. Let N be the number of flips you needed. Then, if the first number M is >N then stick with it, otherwise choose the other number. No matter how the other person chooses, you will have a >50% chance of winning. Here’s why…

For any k, the probability that N=n is p(n)=1/2^n (assuming a fair coin). Now we don’t know how the other person chose their two numbers, but we can assume they were chosen from some probability distribution where q(m) is the probability that the number chosen is m. Let M1 and M2 be the first and second numbers in the two hands. There are four cases.

(a) M1 and M2 are both >N;
(b) M1 and M2 are both N and M2<=N
(d) M1N

In cases (a) and (b) there is clearly a 50% chance of winning, so we ignore those.
In case (c), we always win! (think about it)
In case (d) we also win! (think about it)

So, as long as there is a non-zero probability of being in case (c) or (d), then we have a greater than 50% chance of winning! In fact, we only need to show that there is a non-zero probability of being in case (c). Well, we can compute that probability and show it is greater than zero…

Probability of Case (c) is the sum of the following…
p(1)*(1-q(1))*q(1) +
p(2)*(1-q(1)-q(2))*(q(1)+q(2)) +
p(3)*(1-q(1)-q(2)-q(3))*(q(1)+q(2)+q(3)) +

Now, since at least two of the q(m)’s are positive, and since all the p(n)’s are positive, we know that sum is positive!

So, what information are we assuming?
* That the two numbers are drawn from the same probability distribution
* That the two numbers are distinct
* That q(m) is non-zero for at least two values of m

This can easily be extended to the set of all integers. However, the real numbers are more problematic. This is because the two numbers could be the same up to L digits for some very large L. That violates the second assumption above. So we cannot write down our threshold number (N) using decimals — we’d need to stop somewhere. So, to deal with this, we need to choose N as a ratio of two integers N=p/q. With some non-zero probability of every possible such fraction. Since the rationals are dense in the reals, I believe the above type argument will work.

So, with this strategy, no matter how the two numbers M1 and M2 were chosen, there is a >50% chance we will win!

• Cliff says:

If the intent is to have the game in the real world, with real people, then there is a way to win more often.

Let me explain. For any given number, there are more humanly describable numbers “above” it than “below” it. There is only enough room on the paper to write a certain number of digits, and there are infinitely many more numbers larger than that, but a finite number below.

If the human (who is not trying to fool you) writes a number close to this “largest number” you can bet the next number will be smaller, although in a pure mathematical sense the probability of the number being smaller is 0 (because there are only a finite number of numbers that are smaller), and the probability that it is larger is 1 because there are an infinite number that are larger.

(Taking the negative of that largest number generates a lower bound.)

So is this real world, or pure math?

• Jamie says:

I just wanted to point out that the two numbers can be equal to one another since the question does not specifically say one must be larger than the other. It just states that they are selected ‘randomly’. If they turn out to be equal then you dont lose by picking the other hand; you only lose if the other hand has a smaller number. So, I’m sticking to the answer I provided above… always pick door number two.

• Erica Klarreich says:

Jason wins the Internet! (At least in my opinion, and not speaking in any official capacity as one of Quanta’s writers.)

Let me try to describe his method in a slightly less technical and more concrete way.

So first of all, our opponent has already chosen the two numbers before we start our end of the process, and is tightly clutching them — let’s call them A and B, and suppose A is smaller than B. In what follows, we don’t care at all what process our opponent has used to choose the two numbers. No matter what numbers the opponent has chosen, we can beat 50% (though the particulars of the two numbers do determine how much better than 50% we can do).

We’re going to choose a number G (what Jason called the threshold) that will guide our strategy. We choose this guide number randomly, but the particular random process we use to generate it has to have some special properties that will become clearer after we see how the guide number helps us. I’ll save how to choose the guide for the end.

Our strategy is simple. We pick the left or right hand at random and look at the number it’s holding. If this number is bigger than the guide number G we keep it, but if it’s smaller we switch. (The chance that it’s exactly equal to G is vanishingly small so we can ignore that.) Now there are three cases to consider:

1. Suppose our number G is smaller than both A and B. Then it’s not a very useful guide. Whichever hand we pick, the number it holds will be bigger than G, so G will tell us to stick with that number. In this case our probability of winning is just 50%.

2. Suppose G is bigger than A and B. Then, again, it’s not a useful guide. Whichever hand we pick, the number it holds will be smaller than G so we’ll switch to the number in the other hand. Again, our chance of picking the larger number is no better than 50%.

3. But if our guide number G happens to fall between A and B then we’ve hit the jackpot! Whichever hand we choose, if we see the smaller number, our guide will tell us to switch, and if we see the larger number, our guide will tell us to stay put. Chance of winning: 100%!!

So since Cases 1 and 2 produce a 50% chance of winning and Case 3 produces a 100% chance of winning, our combined chance of winning is greater than 50%, provided that Case 3 has a non-zero chance of happening–that is, provided that G has a non-zero chance of falling between A and B. This is why the process of picking G is important: our selection process has to ensure that every interval [A,B] on the real number line has a non-zero probability of containing the number G.

There are many ways to do this, but here’s one concrete one (which Jeremy Magland also used, more or less, in his comment): Flip a coin repeatedly until it comes up heads. If the first head appears on the Nth throw, choose G to be a random number between N-1 and N. (To include negative numbers among the possibilities for G, we can do one more coin toss to decide whether to make G positive or negative.)

With this process for choosing the guide number G, no matter what values our opponent chooses for A and B, there’s a non-zero chance that G will fall between them. For example, if A is 17 and B is 34, then G will fall between them if the first head came up after 18 to 35 tosses (I’m glossing over the negative numbers here for simplicity, but including them doesn’t change anything significant.) The probability that the first head appears after 18-35 tosses is very small, so the probability of winning is just a teeny bit more than 50%, but that’s all we need.

• Pick some function f(x) defined for all real numbers, such that the limit as x->-infinity of f(x)=0, the limit as x->+infinity of f(x)=1, and f is monotonically increasing: that is, whenever x is greater than y, f(x) is greater than f(y). For example, you could choose:

f(x) = 1/2 + arctan(x)/pi

Pick one hand at random. If the number you are shown is x, compute f(x). Then generate a uniform random number z between 0 and 1, and if z is less than or equal to f(x) guess that x is the larger number, but if z is greater than f(x) guess that the larger number is in the other hand.

The probability of guessing correctly can be calculated as the probability of seeing the larger number initially and then, correctly, sticking with it, plus the probability of seeing the smaller number initially and then, correctly, choosing the other hand. If x is the larger number and y is the smaller number, this probability is:

P = probability of seeing x, times probability that z is less than or equal to f(x)
+ probability of seeing y, times (1 minus probability that z is less than or equal to f(y))
= 0.5 f(x) + 0.5 (1-f(y))
= 0.5 + f(x) – f(y)

which is strictly greater than 0.5, because f is a monotonically increasing function and x is strictly greater than y.

• Oops, I wrote a little hastily:

P = probability of seeing x, times probability that z is less than or equal to f(x)
+ probability of seeing y, times (1 minus probability that z is less than or equal to f(y))

= 0.5 f(x) + 0.5 (1-f(y))

= 0.5 + f(x) – f(y)

Of course the last line here should be:

P = 0.5 + 0.5 (f(x) – f(y))

And of course this is still strictly greater than 0.5, because f is a monotonically increasing function and x is strictly greater than y.

Quite simple. If the number is above zero go lower and vice-versa.

Hopefully the number set cleaves at zero.

• John Liesveld says:

Many of the prior discussion posts seem to infer that we (as players of the game) can run many trials (i.e. play the game multiple times). I’m not sure the author intended that to be the case. WHAT IF we can only play the game once in a lifetime. After playing that “one time” we can never play again. Does that change anyone’s method, or rules of probability employed, when trying to solve the puzzle. I’m not boasting any insight into the answer. I’m not a mathematician. And my brain is probably flummoxed by this conundrum of a puzzle more than most other brains. But my advice: try to watch as many episodes of that old TV show, “Lets Make a Deal,” with Monty Hall. The answer is in there somewhere.

It seems to me that by choosing to always go with the second choice (i.e. putting your initial choice back and going with the number in the other hand) will always decrease your odds to 1/4 because for both choices your goal is to always choose the higher number (1/2). And because one number doesn’t really say anything about the other number being higher or lower, and because there are always an infinite amount of numbers remaining to choose from, by going with the other hand you are, essentially, putting yourself in the position of trying to choose the higher number two times in a row (1/2 * 1/2) giving you a 1/4 chance of landing on the right choice.

My inkling is to stay with the first choice in this puzzle, not at all like the Monty Hall case (but that is because the parameters are different); this puzzle is random, Monty Hall’s game was far from random. However, I can’t figure out how to improve the odds beyond 50%.

I’m lost …

• ScaryRoj says:

Our chance of being correct starts at 50% then as we get more information (more numbers shown) we can approach 77.2727…% , therefore winning over the long-term

• Purushottam Dixit says:

My solution is the following (after taking inspiration from the bonus questions). I am assuming positive numbers but the solution for positive and negative is straightforward.

On the first try, stick to the hand that you chose. Subsequently, keep a track of the maximum number you saw till the Nth game, XN (if there are both positive and negative numbers, we keep track of max and min). If in the number in the N+1st game is higher than XN/2 stick to the hand. Reverse otherwise.

This solution basically assumes that the numbers are less than a certain number N. If we knew N, we have a strategy. This solution basically updates our guess of N as the game proceeds.

One can get fancier as well. Instead of just keeping track of all numbers, we can start building an empirical histogram with some bin width (helps if the numbers are integers) and base our guesses on this histogram.

• Florin L says:

Use the following strategy:

sum = 0, number-of-numbers = 0, mean = 0
while (not finished)
choose-left-hand, see n1
if (n1 > mean) then keep-left
else switch-to-right
see n2, win or loose
sum = sum + n1 + n2
number-of-numbers = number-of-numbers + 2
mean = sum / number-of-numbers
end-while

Given enough trials, it should yield a probability of success of up to 0.75. I tested it with random numbers from the uniform, normal and negative exponential distributions. It assumes that the ranges from which the numbers are drawn (or other parameters of the distribution) remain the same for all trials.

• Purushottam Dixit says:

A more complete solution. This assumes that 1) the numbers are coming from a unique yet unknown distribution and 2) there is no mathematically correct way to randomly draw numbers from the real line in a uniform fashion.

Also, note that if we know the distribution, we can have a strategy that is profitable. Now all we need to do is to keep on binning data to update the distribution. The solution is much easier when the numbers are integers but can get a bit messy when they are real numbers. So, till the point we have integers, we keep on binning on integers. Once we see a non-integer, we shift to fancier binning approaches. As we start getting more and more data, we get better and better estimate of the distribution and hence higher rewards.

• Daphne says:

It sounds a lot like Poker, and 21

• Lachlan C says:

I thought about the problem in much simpler terms than many above. I make a wee assumption about the nature of ∞.

1: our number system spans from negative ∞ to positive ∞, with an even amount of numbers greater than and less than zero. Zero is ‘in the middle’.
2: when I select any number other than 0, say five, the middle point has now moved, such that,
– to the greater than side of 5 there is a volume of ∞-5 potential numbers left for our second choice
– to the less than side of 5 there is a volume of ∞+5 potential numbers left
3: Hence
– the chance of picking a number greater than 5 is (∞-5)/2∞ (slightly less than 50%)
– the chance of picking a number less than 5 is (∞+5)/2∞ (slightly more than 50%)

Therefore our rule should simply be, if the first number is greater than zero, stick with it, otherwise pick again!

• John Hebbe says:

Modified answer. I tried to make this solution difficult but failed. Occam’s Razor. In fact, there IS information to be gleaned from the puzzle as presented. Two facts appear.
First Fact. As to whether the numbers are real (rational/irrational) as opposed to including imaginary numbers is resolved by noting that the numbers are singular (‘. . .one number in each hand’). The product of ‘i’ and a real number is impermissible. Singular, numerical quantities. Positive or negative (non-value changing) it may be argued. Of any size. So we have only the set of real numbers to consider. Real numbers, by definition, are those which can be placed on a line. Rationality can be demonstrated to be inconsequential for this puzzle solution.
Second Fact. The range is unspecified. If any range was specified, then, regardless of whether the range contains an even or odd set of real number values, a midpoint can be calculated and the decision to swap or not becomes an elementary process.
Not the case here. You may safely conclude, then, that the range here is infinite. And, to avoid argument, equally infinite in both directions. In the Arabic numbering system, it may be stated that the midpoint of these values is at the numeric zero, central position. As in Roulette, the existence of a zero numeric value here makes a difference. Why? Because with it, if the revealed number is zero, then the odds of the other number being higher or lower are identical. There is no solution. Without a zero number, there is always an odds-worthy solution however minimal. But wait. . . . . as noted in an earlier discussion, the structure of the number pool from which your two numbers have been chosen has everything to do with determining whether or not a valid conclusion exists. Here, no numbering format is hinted at. Consequently, no conclusion exists. You may not generate fact from random data in this problem.

• Brenden Roberts says:

Here’s a slightly different take: in the worst possible case, the information content of the number of bounded above by the Bekenstein limit on entropy. Let I be the Bekenstein bound of Pradeep’s fist in bits (~10^42), then the maximum range of values is (-2^(I-1),2^(I-1)) with a granularity of the integers, with the “-1” coming from the sign bit. More likely, some bits will be designated as mantissa and some as exponent, for a finer granularity but lower range.

If the number shown is less than 0, one knows that a sign bit is in use and the symmetric range given above applies; the optimal strategy is to switch hands.

If the number shown is greater than 0 but less than 2^(I-1), it is possible that the number is encoded without a sign bit, in which case the range is [0,2^I). With no additional information, assume that there is a 50/50 chance a sign bit is in use. If a sign bit is used, then the optimal strategy is to stay. If no sign bit is used, as the number is less than (2^I)/2 = 2^(I-1), then the optimal strategy is to switch. If the number is above 2^(I-1), then no sign bit is being used and the optimal strategy is to stay. Thus, the strategy in this case is:

Open hand 2^(I-1): Stay

• Bent Schmidt-Nielsen says:

There have been a number of insightful answers so far, but I feel that no single answer is sufficiently complete.

I will call the two parties to the game the presenter and the player. In order to come up with a reasonable answer I need to state two assumptions on my part:
1. The game is iterated an indefinite number of times.
2. Since the presenter is a non-adversarial human, the distribution of numbers presented is consistent over time.
Given these two assumptions, the wining strategy is as follows:
a. On each turn flip a coin to choose the hand to reveal and keep a list of all numbers that have been revealed.
b. On the first turn, knowing nothing about the distribution of numbers to be presented, switch if the number reveal is negative.
c. On all subsequent turns switch if the number revealed is greater than (or equal to) the median (not the mean!) of the previously observed numbers.

This strategy works because each number revealed comes from the consistent distribution generated by the non-adversarial presenter. The player builds up a list which is a subset of the distribution. The median is used since the wining decision is based merely of the relative value of the two numbers. It does not matter if the second number gets revealed since the first number which does get revealed does come from the consistent distribution. Thus regardless of the nature of the distribution of numbers selected, as long as it is consistent, the strategy approaches a 3/4 win rate as play proceeds.

• Odyssios says:

The only thought that occurs to me is that for any probability above chance, in fact the outcomes are not equiprobable. But how this works with a coin, or a probabilty of 0.1 for ten equally fprobable digits between 0 and 9, I have no idea. In fact, by my current undestanding, if you take the ten-digits probem, the actual outcomes expressed as decimal strings, first, first two, first three … represent noncomputable numbers, explicitly because there is no ‘algorithmic compressibility’ – no way of calculating the number that is shorter than the number itself (or longer!) I’ll be interested to see what, if anything, (a claim that a solution exists is not itself a solution!) I’m missing.

• John Liesveld says:

Second Attempt Solution
TITLE: Vanquishing Monty Hall!

Okay, one more try: after a bit of review of probability and calculus, I think I have a solution. Bare with me as I attempt to put the somewhat abstract (i.e. difficult to articulate) concepts into my own words. And I apologize in advance if this explanation becomes a bit convoluted:

Imagine Monty Hall (host of “Let’s Make a Deal”). Yes, again I use him as my example. Imagine that he gives you two doors (Labeled “Dullards” and “Good Sense,” loose puns intended 😉 Get it??). Behind each door are piles of money, and amazingly, using his beyond-the-grave supernatural powers Mr. Hall is able to manipulate the laws of physics so that the piles of money can also constitute into negative values, in which case you owe will owe Mr. Hall a only dollar if you WIN the premise of the game. If the money is negative and you lose the premise of the game then you will owe Mr. Hall the absolute value of the amount of negative money contained behind the door. The amount of money (positive, negative or zero) in each pile is determined randomly (somehow).

Okay, now we understand the scenario in terms of risk, stress and finances … something we can all relate to, especially if you’ve ever been a poor student.

Next, Mr. Hall smiles broadly, and a bit sardonically, and says, “I am going to let you open one door to observe the amount of money contained beyond. Careful though!! If the pile of money is a negative pile, then I must caution you to quickly avert your gaze and observe this quantum conundrum of para-physical phenomenon through your peripheral vision; as peering upon a negative pile of anything tends to ‘suck’ the sentience right out of any living body … don’t ask me to explain.”

“Now then,” Mr. Hall continues, “based on this observation I am going to ask you to make another choice. You may either 1.) discard your first choice and go with the alternative door. Or you may 2.) persevere with your first choice. The object of the game is to choose the door with the most amount of money awaiting behind their wood paneling.”

Amazingly, Mr. Hall’s smile broadens further, bordering on nefarious and then he adds, “I’m not promising you a ‘Big Win’ here, I’m only promising you the possibility of the least amount of financial heartache … There are four categories of outcomes that could result for you: one, you could win some money, potentially a lot of money; two, you could lose one dollar; three, you could lose more than a dollar … much, much more; or four, you could walk away having not lost or won anything other than relief that you will only have to play this game once in your life.”

“ And this point is important to understand: You are NOT allowed to run trials of this game over and over or to see results of prior attempts by other players. This is solely a ONE TIME DEAL.”

“Your task is to find a way to beat this seemingly paranormal dilemma of devious devilishness and come up with a system that will improve your odds beyond 50%.”

With that, Mr. Hall steps back into the unlit corner of the stage where the angled shadows morph his smile into an egregious smear of dim contours.

“Make your first choice!” he commands.

What do you do??

From my research, I have a pretty good solution and explanation (I think). I don’t exactly understand all of what I learned, and much of it (to me) seems a bit unintuitive. However, for the most part it seems to make sense.

So, here goes, my advice and suggestions to you:

STEP 1 :
Before making any choice between door “Dullards” or door “Good Sense” (door ‘D’ and ‘GS’ respectively, for simplification) I ask that you take out your trusty old smart phone on which I have coded and installed an App that generates true random numbers from all the real numbers on the number line.

Once the App spits out a number for you, assign that number to the variable ‘F’ for “First choice number.” Thus, F = some real number on the number line, chosen randomly.

STEP 2:
Okay, still with me? Now, choose a door at random, either door ‘D’ or door ‘GS.’ Then turn to Mr. Hall, stand tall, stand confident and tell him to open the door you chose.
REMEMBER, if the pile of money is a negative pile, look away quickly and observe only with your peripheral vision. Mr. Hall will tell you the amount of negative money. You might end up losing a dollar in this game, but I surely don’t want anybody losing their soul over this absurd premise.

STEP 3:
Now that you know the amount of money behind the door you chose, you must then decide whether the pile of money behind the alternative door is higher or lower (i.e. more hundred dollar bills or fewer hundred dollar bills).

To do this continue to STEP 4.

STEP 4:
Look back at your First Choice Number, ‘F,’ and measure it up against the following parameters.

a.) if ‘F’ {the amount of money behind the door you chose} THEN I advise you to reckon that {the amount of money behind the alternative door} is also greater. In this case, choose the other door, and ignore all sarcastic statements Mr. Hall might make to erode your confidence.

NOW FOR THE “KICKER,” Why does this work:

Well, stick with me here as I break it down into the following WINNING scenarios. Then at the end I will tie all these scenarios into one systemic calculation that shows, if you do it my way, you’ll tip the odds in your favor:

SCENARIO 1:
Refers to Parameter ‘a.)’ in STEP 4. You win if your ‘F’ number is less than both doors ‘D’ and ‘GS’ because in this case you would have guessed that the door you did not choose had a smaller pile of money behind it, so you would have stayed with your first choice and come out on top … or at least you would have lost only a dollar (if the piles are negative). And because the amount money in each pile was determined at random you would have had a 50% chance at guessing that your number ‘F’ is both < ‘D’ and both ‘D’ and ‘GS.’ Again you come out on top. However, for the same reasons mentioned in SCENARIO 1 the probability of this scenario is also 50%

SCENARIO 3: (Now I’m getting the interesting part)
What if your number lies somewhere between the amount of money behind door ‘D’ and door ‘GS.’ For instance, your smart phone App generates, at random, the number ‘F’ = 3.1204, and the amount of money behind door ‘D’ is less than ‘F’ and the amount of money behind door ‘GS’ is greater than ‘F.’ Or vice versa.

So, if ‘F’ is larger than {the amount of money behind the first door} (let’s say door ‘GS’) then you would have chosen the second door ‘D.’ That is GS < 3.1204 < D and you would have come out on tope because remember you’d have chosen to go with the alternative door ‘D’ because ‘F’ was greater than your first choice GS. You would have won how ever much money is behind the second door, door ‘D’ because it would have been more than 3.1204.

IF however ‘F was less than your first choice (let’s say door ‘GS’) then you would have also guessed that door ‘D’ was also less than ‘GS’ such that ‘D’ < 3.1204 < ‘GS’ and you would have chosen to STAY with your initial choice, door ‘GS.’ Again, you come out on top winning 3.1204.

Here’s where we mix probability with calculus. Because your First Choice Number, ‘F’ is random and the amount of money behind each door is chosen randomly and chosen prior to the start of the game (so that they remain fixed) the chances that ‘F’ falls somewhere between these two amounts of money occurs with a finite probability. This has to do with the fact that there is a probability distribution occurring between these to amounts of money, and that distribution is determined through integral calculus.

In terms of mathematical equations, if you assign the probability that ‘F’ falls between the amounts of money behind both doors to the variable, ‘B’ (Between), and then use the probability distribution equation:
(1+B)/2 you will always get something slightly greater than 50% because B, by physical and mathematical law cannot be zero.

THUS … FINALLY … IN THE END, because one of the scenarios (SCENARIO 3) always give you a slightly greater than 50% chance, taken together, as a system, this strategy will improve your odds at vanquishing the cynical supernatural enigma of Mr. Monty Hall’s financially perilous game of “Let’s Make a Deal.”

JUST DON’T LOOK DIRECTLY AT A PILE CONSISTING OF A NEGATIVE AMOUNT OF MONEY … or a negative amount of anything, for that matter. Because I’m not in the business of saving souls … I’m just here to cut your losses.

And a cheery day to all I cry!

• JM says:

Select a random rational number making sure that there is at least a positive probability of selecting any particular rational number. This could be done by choosing the numerator as the number of tail flips of a coin before a head, and choose the denominator the same (then randomly add a positive or negative sign — zero should also be included). If the first number is greater than your random number then switch. Otherwise stay. The reason this works is that there is always at least one rational number between the two given numbers. Therefore, there is always a non-zero chance that you will generate that number and will thus automatically win. Otherwise you have no less than 50/50 chance.

The information here is that the two numbers must come from some probability distribution which is necessarily biased in some way toward numbers that are close to zero. The extent of this bias is related to how good your chances are.

• g g says:

This is just a slightly simplified version of Jason’s method and an attempt at a more intuitive explanation of why it works.

To be successful, you need a strategy which makes you more likely to stay with your choice when the number shown is large and more likely to switch if the number shown is small. The difficulty is (of course) that you do not know what is small or large since “any numbers” are permitted. This is where probability will help you. So, as a first step, chose any probability distribution on the real line. (see https://en.wikipedia.org/wiki/Cumulative_distribution_function for further explanation)

I will describe the strategy by assuming the unknown numbers are 3 and 4. Of course one needs to make sure that the strategy works in general but this is simple. The strategy consists in three steps:
1. Flip a (fair) coin to choose one of the numbers with probability 50%. Assume the number chosen was 3.
2. Now draw a random number according to your chosen distribution.
3. If your random number is smaller than 3, stay and make 3 your ultimate choice. If your random number comes up larger than 3, then switch and make the hidden number your final choice.

This is all you need to do. Why does it work?
Observe that the probability that your random number (call it z) is smaller than 3 is always smaller than the probability it being smaller than 4. As a formula P(z<=3) < P(z<=4). This is a general feature of probability which means it works for all numbers x,y with x3).
If 4 comes up: You are right if you stay, which you do with probability P(z3) + 0.5*P(z3) = 1 – P(z<=3) and your total probability of success can be written as
0.5 * ( 1 + P(z<=4) – P(z<=3) ).
But P(z<=4) – P(z<=3) is always positive as stated above, hence the total probability of success is larger than 0.5.

Finally convince yourself that nothing was special about 3 and 4 and that all of the above works for any (real) numbers x and y with x<y.

• Eric T says:

How do you know that “we are, after all, the only species that solves puzzles for fun” – even if you restrict yourself to this planet?

• paul malenfabt says:

what if i tell you that i will always generate the numbers N and N+1. i will always put the odd number in my left hand. now, how can you possibly get better than 50% in the long run?

• Colin P says:

I would like to draw attention to three constraints that do not exist in the puzzle as described. There is no constraint that Pradeep must generate the two numbers independently, there is no constraint that Pradeep must assign them randomly between his two hands, and there is no constraint that Pradeep must reveal to me what the second number is.

For examples of these, a scenario in which the first number is generated by some algorithm and the second number is the first number plus one is consistent with the puzzle description, a scenario in which Pradeep (having generated them) inspects the two numbers and places the larger one in his left hand is consistent with the puzzle description; and a scenario in which Pradeep only states whether I have chosen the larger number or not, and does not tell me the value of the second number, is consistent with the puzzle description.

So to begin with perhaps the puzzle is a bit harder because I am not focussing on special cases. What do I know, or what are the constraints? That in each iteration of the puzzle method, before the “stick or twist” decision, I will know which hand I have chosen first, the value of the number in it, and that the number in the second hand is different, and after the “stick or twist” decision I will know which of the two numbers is larger.

Armed with this information my plan is this (it is not dissimilar to others before):

For a number of rounds, lets say 30 to begin with, I will always choose Pradeep’s right hand, I will make a note of the number he shows me, I will stick with it (choose it), and if he tells me it is the larger one I will score it +1, but if he tells me it is the smaller one I will score it -1, and I will write down all these 30 sets of data.

Well, I am nearly there, because I have done the easy bit which is the bit I am capable of. Having collected all 30 results I hope that statistics is going to ride to the rescue, so I will summons Pradeep’s colleague Joseph Chang, statistics professor and chairman of the Quantitative Reasoning Council at Yale University (helpfully mentioned later in the puzzle article and if he responds to summonses) to assist to begin to make sense of the data I am accumulating, and most probably to tell me how many more iterations I must do to gain a reasonable chance of being able to turn the game around and predict, on the basis of the “before” information alone, what I should do at each “stick or twist” decision.

If on the other hand Joseph Chang is unavailable, as seems likely, then I would attempt to proceed with the analysis myself, doing many more trials if necessary, and taking some comfort from the following observations:

1) If in my first trial my cumulative score is +30 then I would begin to suspect that Pradeep inspects the two numbers and assigns the larger one to his right hand. If I score -30 I would suspect he assigns the larger one to his left hand.

2) For any other cumulative score there are a large number of possible number generating and hand-assigning algorithms that could replicate it, but my task is to work out what decision to make, not to discover the actual algorithm itself, and any algorithm that leads to decisions that are arbitrarily close to the “correct” ones will do.

3) A 3-d graph with axes left hand vs right hand, first number value, and first number score (+1/-1), could go a long way to helping me visualize a successful algorithm. Ultimately I hope to plot enough 3-d points to be able to draw a continuous best-fit line through them, so that later when I choose a hand and Pradeep tells me the number value in it I can find which part of the line it belongs on and what left-hand relative score it gets: +1 (choose the left hand) or -1 (choose the right hand).

Of course, when I decide to switch from trial mode to decision mode (i.e. not always choosing Pradeep’s left hand number) I would continue to record the results, plot the data, and refine my best-fit “machine”.

Well, to be honest with you, I do not know how good or bad this answer is, but it has been entertaining, and in considering it I am led to believe that the puzzle shows that randomness may reveal information, but does not generate it.

• Colin P says:

hmmm, editor at work, rights and lefts confused!

In my post item 3) should have concluded, “…I can find which part of the line it belongs on and what right-hand relative score it gets: +1 (choose the right hand) or -1 (choose the left hand).

and in the following paragraph, the part in parentheses, “(i.e. not always choosing Pradeep’s right hand number)”

• Steven Alexander says:

I believe the general solution is that stated by “g g” [July 12, 2015 at 7:16 am] with the proviso that the probability distribution be one with nonzero cumulative density over every real interval (which is necessary to his explanation being correct). Others came up with particular ways of doing this, such as Jeremy Magland’s [July 9, 2015 at 9:26 pm] choosing a random rational number. It would be just as good to pick a rational number at random and add, e.g., e to it.
I now see that Erica Klarreich [July 10, 2015 at 12:00 am] said much the same.

• jon says:

The problem as stated requires the person to show you the number, but numbers are abstract mathematical objects that cannot be seen. What we can see is a numeral, and that assumes an appropriate notation that is agreed upon. If the notation system is not defined beforehand we can just make up a notation system that makes the number we chose to be the larger one.

Author’s Notes for the Second Week

Greetings, all! Thank you for all your responses that have generated this lively discussion.

Now that the puzzle has been out there for a week or so, I thought I’d dive in. My purpose here is to issue some clarifications, highlight some contributions, and in general, stir the pot to generate further discussion, before we wrap up this puzzle later this week.

-Cliff asks: Is this the real world, or pure math?

Great question, Cliff! By and large, our mathematical models give superb results in real world problems – the whole edifice of science is based upon this. But I have often observed that our immense successes with modeling the world using mathematical thought blinds us to cases where our abstract scenarios sometimes are not good models of the world. Could this be one such situation? One clear-cut difference, if this were a single real world bet instead of an abstract problem, is that you would use all the contextual and psychological knowledge at your disposal to try and make a best guess. Some of the commenters have invoked such strategies as picking the same hand, estimating the maximum size of number that can be held in the hand, etc. Any of these could be relevant to some extent in a real world case and in some situations could easily become more important than the logical solution of the purely abstract problem.

In setting up this puzzle, I tried to accommodate both the “pure math” and “real world” scenarios. The main problem is “pure math”: it describes a purely abstract, non-adversarial situation in which a pair of numbers is generated by some unknown process. On the other hand, all the bonus problems are “real world” situations in which problems 1, 2 and 4 describe non-adversarial situations and 3 describes an adversarial one.

Since the main problem is purely abstract, you can imagine it as a non-repeated game, or as a game where the two target numbers in any iteration of the game are generated completely independently of previous trials, from completely different “distributions,” if any.

So far readers have come up with some very well-reasoned and well-explained contributions. I’d like to compliment Jason for his insightful contribution and to Erica Klarreich for explaining it so well. Also interesting are Ger Groeneveld’s idea of a dynamic median and its actual simulation by Geojenks.

Although there have been very good responses that address the logical problem, it seems to me that the underlying philosophical conundrum behind the puzzle – where does the information come from? – has not yet been satisfactorily addressed. A lot of respondents have said that you do have some information – you are shown the number in the first hand – which is true. But, given that these numbers come from an unknown distribution, or not from any “distribution” at all, the number we know has no bearing on whether the number in the other hand is smaller or greater. So it seems that our chance of guessing which is larger should be stubbornly stuck at 50%. If it is not, then we must be getting some information about the other number from somewhere. What are we missing here?

• Jason says:

Pradeep, thank you for the compliment.

To proffer a guess a to where the information is located, I would have to say that it can only be in one possible place – the knowledge that the two numbers are not equal. This isn’t much information, but it was the clue I used to come up with the answer I posted above.

If we restrict ourselves to dense sets (such as the real numbers), then we know that for any two numbers x and y, with x strictly less than y, then there are an infinity of other numbers z satisfying x < z < y. This remains true no matter how large or small are x and y, and no matter how close together they might be. We could imagine some adversarial opponent trying to break this using limits – for instance, choosing y to be equal to x+1/n in the limit that n goes to positive (or negative) infinity – but that gives us x = y, violating the terms of the game.

Thus, we can win the game if we can, independently of our opponent, guess one of those z's. This is hard to do. In fact, an adversarial opponent can make it arbitrarily hard to do – but he can never make it truly impossible, simply because, for any given x, there is no unique smallest real number larger than x.

Now, an interesting question to ask here is "what if the opponent doesn't restrict himself to real numbers?" Fortunately, we can rule out things like complex numbers, because we require a well-defined notion of greater than. But, we can't rule out things like infinite cardinals – for instance, what if the opponent chooses aleph-0 and aleph-1 as the number pair? If we know what set the numbers are being drawn from, we can create a mapping to the reals – as long as the drawing set is no larger than the reals. (In the case where the drawing set is larger than the reals, I think we are safe, because I don't think it's possible to well-order such a set – but I'm not sure on this point.)

But, if the opponent only says "number," and doesn't mention which set of numbers he's drawing from? Then, I think, we're truly dead in the water.

• Where does the information to win with a probability of greater than 0.5 come from?

In the solution I gave, the probability of sticking with the revealed number x is f(x), where f is chosen to range from 0 to 1 as x ranges from minus infinity to plus infinity, and f(x) is greater than f(y) whenever x is greater than y. Since the probability of sticking with a number is always greater for a greater number, we’re more likely to choose the greater of two numbers x and y, however they have been selected.

When we pick a hand at random, the probability that we have picked the greater of the two numbers initially is exactly 0.5, but when we are deciding whether or not to swap, we don’t need to know a value for “the probability that the other number is greater” in order to execute our strategy: all we need to do is make it more probable that we stick with the greater number than that we stick with the lesser number. Our advantage comes from the difference between the actual situation and the counterfactual alternative: if we had chosen the other hand, our probability of sticking with it would have been appropriately greater or smaller.

So, seeing a single number does not give us any information about which of the two numbers is greater. Nevertheless, because we might have seen either of the two numbers, we can arrange the difference in the way these two possibilities would have caused us to act to make us more likely to end up choosing the greater number.

• Jason says:

On revisiting my above post, it occurs to me that the answer to “where is the information?” has been staring me in the face the entire time, and yet I’ve been blind to see it. Indeed, I spent more of the above post talking about the actual answer than I did addressing the one I actually proffered.

The information is contained within the properties of the real numbers themselves – specifically, the concept of density, and what it means for one real number to be larger or smaller than another.

• John Liesveld says:

Yes, what Jason said: The information arises from the fact that the two numbers are not equal. But to take it a bit further … that means that there is a set of numbers that exists between the two unknown numbers that are finitely defined. And if the random number you choose before prior to playing the game, the number you use to determine parameters of how you will play (See my second post: “Vanquishing Monty Hall”) falls between the two unknown numbers, then where it falls can be predicted by a probability distribution that exists between the two unknown number. Therefore, the farther apart the two unknowns are the higher the probability that your pregame number falls somewhere in between the unknowns. Thus the higher the probability (above 50%) that you win. The closer together the numbers are then the lower the probability (more approximating 50%) that your pre-game number will fall between them and thus.

Hmmm? Not being a mathematician (just a nursing student) I lack the technical terms and “equational” prowess to describe it any better … but my answer feels right … to me, anyway.

• Colin P says:

Since the puzzle begins with the words, “I write down…”, it is arguable that this limits the set of numbers under consideration. Could it be said that the information comes from the boundary conditions (of the puzzle)?

• Philippe says:

Hi, I will try to throw my insight in the debate. As a physicist, I decided to attack the problem using an image that I knew really well: Maxwell’s demon paradox, which goes like this.

Suppose a box fill fill with a gas made of two types of atoms (A and B) in equal proportions. The two types of atoms are not identical (e.g. in mass or speed). Now let’s divide the box in half with a panel with only a small aperture in the middle. If a small demon were sitting on this aperture, letting only one type of atoms pass through it in a given direction, and letting the other type of atoms pass only in the other direction, both sides would be filled eventually with identical atoms, and the entropy of the system would have decrease with respect to the original scenario where all the atoms are mixed inside the box.

Now here is the paradox: How can the entropy of the system diminish without breaking thermodynamic’s second law claiming that entropy can only be raised (the disorder can only be enhanced)? The solution is that one needs to consider the entropy of the box AND of the demon; by his actions of measuring and filtering the atoms, the demon would increase its own entropy at least as much as he lowered the entropy of the box. For example, the demon could be a detector that would release heat (and thus entropy) by working out its task. The only way the demon could proceed to his duty without raising the entropy of the whole system would be if his measurements were perfectly reversible actions that could be undoable after a given amount of time. However, reversible actions need storing the information that was proceeded indefinetly, which is impossible for a real gas, due to the lack of both finite storage capacity and readout speed. As soon as you erase one data, you start to increase the entropy of your system.

Now here is the link with the problem at hand. You are the demon that decide whether the number you pick goes on one side (greater) or the other (smaller), and by doing so you change an incoming set of numbers (chosen by the algorithm) with high entropy to an outcoming set of numbers with a lower entropy (because they are ordered).

If you wish to produce an outgoing set of numbers with a lower entropy, you must necessarily increase the entropy of something else, somewhere else. And that would be inside a register were you keep track of all the information that you have proceeded (numbers that you saw, hand that you picked, and the final results). It is the only way you could possibly lower the information entropy that you have proceeded, and start to have outcomes that are better than 50%.

Now the question is: how do you use the register? Many people pointed out that you should use statistical informations of your data (mean, extrema, median…). However, by doing so, you erase information, because there is more information in a whole register than there is inside few statistical values, thus you increase the entropy of your whole system, and mitigate the efficiency of the outcome. For example, if the algorithm is such that a number superior to the median will always imply that the other number is also superior to the median, your process becomes very floppy.

Every decision should therefore necessarily be made using the WHOLE register. For example, we could say that given a number that you see after the person opens his hand, you choose the result associated to the closest number in your register. Eventually, your results will get better and better, and you will be lowering the entropy of the outcoming set of numbers that you produce.

This proposition is based on the assumption that the range of the numbers is finite, as well as their precision. Clearly the bigger the precision and the range of the numbers are, the slower you will decrease the entropy of your system, and the bigger your register will need to be. There is no such thing as a free lunch in nature.

For a beautiful (and one of my favorite) discussion on entropy and thermodynamic’s second law, check out chapter 46 of Feynman’s lecture, Volume 1. It is one of the best physics reading I did in my life.

• sagef says:

the information comes from randomness, just like everything else in the known universe. selection or observation collapses what we don’t know and can’t completely know eg. the randomness into information.
seems there would be two ways to beat the game, one purely by the winning just happening eg. some really good luck, sort of like the forming of the universe and evolution and two perhaps gaining a mathematical advantage from information gained by selecting over time while employing logic to implement the advantage.

• g g says:

The puzzle is not related to and does not require any numbers. I will show this by giving an abstract version. I fear this might not be comprehensible to non-mathematicians but this happens sometimes if you try to get really to the bottom of things. For this more general setting you need two ingredients:

1. An abstract set (call it Omega) which is (strictly) totally ordered, i.e. for two different elements x,y of Omega you have either xy.

2. A function f from Omega to the real numbers which is consistent with the ordering, i.e. if x<y you have f(x)<f(y).

Given 1. and 2. you can apply the randomisation trick more or less verbatim.

One example for the more abstract game might be geometric shapes in the plane ordered by inclusion (Omega) and their area (f).

• g g says:

I am not convinced that this puzzle is an example of “information created by randomness”.

Observe that the definition of the task already implies randomness: You are looking for a strategy which makes success more likely than 50%. Without a notion of probability or randomness in the background this task would make no sense in the first place.

I would describe this more as an instance of breaking a symmetry. You start with a completely symmetric setting, i.e. you choose either one number or the other. Then this symmetry is broken by seeing one of the numbers. That this is “information” is solely due to the fact that it can actually be used as input to the “absolute yardstick”, i.e. the randomisation trick.

• JM says:

The information comes from the fact that we know the numbers are indeed numbers, and therefore they are closer to zero than almost all other numbers. In other words, they are relatively speaking extremely small.

• Philippe says:

Following my previous comment, I would like to point out that my answer to the question “Where comes from the information” is: information comes from your register that you have the ability to fill with previous information that you gain. And from your ability to read this information at will, in order to perform reversible processes every time you make a decision on a number. Again, the more complicated the numbers are (in range or in precision) the bigger your register needs to be.

• Deb says:

Since measurements bring conclusions and conclusions rule out variable possibilities, it might be best just to stop thinking and trust. Perhaps, we already know the numbers – even now : )

• John Hebbe says:

Jason, et al. Thank you for your erudition and the genuine excitement of seeing how your minds function. My earlier arguments (7/10 @ 7:25) maintain. In every situation, your analyses apply assumptions not provided in the stated problem. Given: (1) We have two differing numbers of unknown origin. (2) One is revealed. Quest: Does a method exist to determine whether the unrevealed number is larger. Have I missed anything? Any theory of proofs argues that assumptions degrade the validity of all proposed solutions. If you made any assumption, your conclusion is invalid. Period. My Final Answer remains: No. In the problem as presented, no method exists to guide you to stay or switch with any mathematical advantage. Occam’s razor. I apologize if these remarks seem disrespectful in any manner.

• Steve Rampley says:

We know one number. Surely we know things about that number. Positive, negative, zero, rational, irrational, prime, etc. Is there a relevant strategy for each kind of number that is revealed to us? Sorry if this is repeating an earlier comment. Please just delete this one.

• Kewl Doug says:

pick a number n as close to the middle of the unknown range as possible.

if revealed number x is greater than n, choose the other number y. else, choose x.

there are two key situations. either n is between x and y, or it isn’t. If it isn’t, your odds of picking the larger number is 1/2. If it is, your odds are 1. You’ll always pick the right one in that case.

So, let’s say your number n is between x and y 1/3 of the time. 2/3 of the time your odds will be 1/2. 1/3 of the time your odds will be 1. You should choose correctly 2/3 of the time.

If n is between x and y only 1/4 of the time, your odds should be 1.25/2.

Of course, if the number you pick is never between the two numbers, your odds will remain at 1/2.

More likely than not, the number you pick will fall between the two options some of the time. However much it does, 1 + that rate / 2 will be your odds of picking the right number.

• Jason says:

g g, you make a good point about the possibility of abstracting things away from the real numbers. I still think that the information must be encoded in the structure of the set from which the objects are drawn – and that that structure must be known in advance in order for the game to be beatable. To illustrate, consider a few alternative games with similar set ups which are manifestly not beatable.

1) The opponent chosen two numbers, as before, which he holds one in each hand. He allows you to reveal the number in one of the hands, and then asks “in which hand am I holding the correct number?” – without supplying any further definition of the term “correct.”

2) The opponent chooses two numbers, but rather than allowing you to choose a hand to reveal, he simply tells you the value of one of the numbers, and then asks you to guess in which hand the larger number is being held.

3) The opponent sets up the game as in the original problem; however, when he reveals one of the numbers it is written in a language you do not understand.

In each of these cases, some crucial piece of information has been removed, making the game unsolvable. In 1), that piece of information is the knowledge of the relation used to identify the winning hand. In 2), it is the location of the revealed number. In 3), it is the value of the revealed number.

Furthermore, if we consider games played on abstract sets (given some total ordering relation), we’ll find that – as you mentioned – the game as initially described is still winnable (at least for sets which admit an order-preserving mapping to the reals; for sets larger than the reals I’m not so sure the game can be won); however, each of the three changes above breaks the abstract game in the same fashion that it does the real number version.

So, I’d argue that the information is still contained in the structure of the sets involved – for the abstract version of the game, the structure is imposed by the existence of the total ordering, and by the assumption of that ordering in the set up of the game.

As a final thought, consider a version of this game played not on the real numbers but rather on the cardinals. So far as I can tell, this game is not beatable because it is not possible to define a probability distribution over the cardinals (or a mapping from the cardnals to the reals, which amounts to the same thing) since the cardinals are not a set (despite being totally ordered).

• g g says:

This puzzle can be reduced further. This removes much of the puzzle appeal but it makes clear where the information really comes from. I claim that the following setup is logically equivalent to the full puzzle:

You are given two Bernoulli-Variables A and B with unknown success probabilities p and q.
(This is math jargon again for busting it: https://en.wikipedia.org/wiki/Bernoulli_distribution)

Your task is to find the variable with larger success probability. You can choose either A or B to generate one sample.

Stated in this way the strategy is rather clear: Pick one variable, get the sample, stay with it if it is success otherwise switch. This is the same strategy as in the full puzzle.

It is now also clear where the information comes from: The information is in the sample. This is very reassuring because where else would you find information, if not in experiments?

• Brian Matthew says:

I agree with the others. The information comes from the problem space itself. Also we were informed it was generated amd not fetched from QM. The fact that it can be communicated in the universe to a human implies a finite number of significant digits or at least a symbolic representation.

Miscellany

I want to re-emphasize that the intriguing, counter-intuitive thing about this puzzle is that you can achieve greater than 50% success in this guessing game starting from the very first try! Many respondents have sketched methods to achieve such a result by making use of results from previous rounds, but that is not necessary. The solution holds even if the game was played only once. If you missed this aspect of the magic of this puzzle, think about it for a moment. It seems impossible, but apparently it isn’t.

It is interesting to follow the discussion between Jason and g g regarding where the information for this instant success comes from. True, there is information in the structure of numbers, but it isn’t specifically about the unknown number. The successful procedure asks you to conjure an arbitrary number out of your imagination and use it as a guide. Obviously this guide number encodes no specific information about, and has no connection to, the unknown number. Yet it succeeds in increasing your chances of picking the larger number. As in other paradoxes of this type, following the recommended procedure is pretty straightforward and mundane. Logically, it is not hard to understand that it works. It’s only when you consider the result achieved that it seems magical, as though there is something weird going on that you can’t quite put your finger on. In case you missed this aspect, I’ll leave you to ponder it for a few more days before weighing in.

Lincoln Phipps:
I ‘ve read some of your writings, and I respect your opinion. I accept that I was “a bit loose in my wording” in the paragraph you mention, as I was talking in intuitive rather than technical statements. However, the context of my statements was different from what you interpreted them as. So let’s see if I can put it in a way that you might agree with. In the first sentence I was talking about randomness and information from the point of view of evolution: a more precise way to express that would be “we know that randomness (random variation) in evolution, has no preferred directional information.” In the context of this puzzle, you can make a random or arbitrary guess (as proposed by Jason, and further expounded by Erica, g g, Greg Egan, Steven Alexander and others), which by itself contains no information about the unknown number.
You say that I’m “messing up entropy with disorder.” Entropy is always a measure of disorder, so I disagree with you there. In case of informational entropy, the disorder is in the fact that every choice we make has an equal chance of succeeding – you can think of it as “cognitive disorder.” If we have some information about an unknown quantity such as “there is an 80% probability that the first digit is 9” then the disorder has lessened and we can make a guess that is more likely to be correct. I agree that humans are appalling at generating perfectly random numbers, but that’s an impossibly high bar – what we mean by a random guess is an arbitrarily generated number, perhaps by using a random number generator (most of which also generate pseudo-random numbers). As for the term “meaningful” in the latter part of the paragraph, it’s pretty clear that what is meant in the context of astrology etc. is information about the character or future predictions concerning the person in question, generated from random events like planetary positions.
In your example of radioactive decay, I agree that information is received and may be meaningful in many different ways. But in guessing games, we’re talking about predicting the event before it happens, not about receiving information from it.

Burton Voorhees:
You can definitely use astrology or Tarot cards as organizers or intuition pumps, but then any true information about a person that you can collect using them comes from the practitioner’s observation and psychological expertise in reading of the person’s responses and not from the cards themselves. Hence the point holds: the Tarot cards don’t contain the information, you get it using straightforward psychology, albeit in a roundabout way.

Eric T.
Send me a postcard when they discover that the humpback whales were playing “soundoku” on a 1000 mile board ☺.
But seriously, if we do find members of a species with high general intelligence on another planet, I’d be willing to wager that they would find delight in solving their own puzzles. Any creature that lives entirely off its wits as we do needs to be constantly solving problems, and having your brain give you an internal reward for solving puzzles seems to me to be a simple evolutionary way to build in a crucial training and motivating tool.

Assuming the rules allow only positive integers, there is an infinity of larger numbers and a limited number of smaller numbers than a given number. So if the selection process is indeed random, once the first number is selected, there is a higher than 50% chance the second number is larger. If the rules ask for the first selected number to be shown first, then there is a better than 50% chance betting on the other number. If no such rule exists, and which hand is shown first is selected randomly, then chance is 50 – 50.

I think you should show last comment first, otherwise newer comments will be never read if there are too many

• Brian Matthew says:

In addition to my other comment I would like to add more assuming the worst case scenario. Let’s assume the numbers truly are random and they can be transacted to some non-finite self aware structure. The problem space still provides the answer. The fact that the game can be played indefinitely makes the outcome more probable to not be exactly 50-50 over large data sets. We just have to play long enough, no matter how many loses are incurred.

• John Hebbe says:

Please suffer through this. The puzzle: “I write down two different numbers that are completely unknown to you, and hold one in my left hand and one in my right. You have absolutely no idea how I generated these two numbers. Which is larger? You can point to one of my hands, and I will show you the number in it. Then you can decide to either select the number you have seen or switch to the number you have not seen, held in the other hand, as your final choice. Is there a strategy that will give you a greater than 50 percent chance of choosing the larger number, no matter which two numbers I write down?”……..
ANSWER: YES. . . .and with a certainty of 100%……….
The strategy: Tell the presenter to open his other hand. Make your determination based upon what you see. Were any criteria violated when employing this method of solution? I think not.

• Jamie H says:

I think Jason essentially nailed it early on, and Pradeep’s further comments today make me even more assured: If you pick any number as a “guide” there is a set of numbers for which your number will fall between. You can win EVERY one of the ’rounds’ if this is the case (Let’s call this CASE 1) by holding the first hand’s number if your guide number is LESS, and trading to the second choice if your guide number is MORE. In the other two cases, where, CASE-2) both numbers are lower than your guide number, and CASE-3) both numbers are higher than your guide number, you will win 50% in the long haul. Sum up the cases and you are always in the black!

I ran some spreadsheet math using this idea, making pairs of random numbers with large bounds and choosing a guide number (just to see for myself what seemed kind of counterintuitive). I ran the scenario dozens of times – and the winning percentage overall is large.

It is easier to visualize if you , say, bound the possible numbers to between -10 and +10, for example.

Great puzzler!

• Edger says:

I’m not convinced any solution so far can guarantee a probability of strictly greater than 50%. In any case, I don’t have a solution to offer, but I do have a point I want to make that I think needs to be addressed mathematically, after the solution is given.

Imagine the number you choose to look at is N. Now the increasing real line is order-isomorphic to the decreasing real line, with an isomorphism fixing N. That is, there’s no reason why the other number isn’t M, but rather 2N-M. There’s a certain symmetry between M and 2N-M.

For you’re strategy to be able to guarantee strictly more than 50% success, some bit of information (which apparently we are all missing) must break this symmetry. That is, the strategy must be able to weigh M and 2N-M differently.

How does see this playing out? Imagine two “parallel” worlds. In both your strategy is to choose to look at the left hand number. Because you have a complete lack of knowledge as to how the numbers are generated, this or any other scheme is equivalent to random guessing to you anyway. In both worlds the number N will be in the left hand. In one world the number M will be in the right hand. In the other world the number 2N-M will be in the right hand. Because you have exactly the same information in both worlds you will use the same strategy in both worlds. Yet the success rate in one world will equal the failure rate in the other world, no? How is the symmetry broken?

• Colin P says:

After Edgar, I have another point I would like to be addressed but this is about Jason’s strategy specifically. Jason’s strategy involves an algorithm (choose a threshold, view one of Pradeep’s two numbers, compare to threshold, make choice) which I would like to summarise as “Jason sees number 1 and makes choice”. In this case I believe the puzzle as stated can be reduced to the following steps (Puzzle A):

3) Jason sees number 1 and makes choice

It is claimed that Jason’s algorithm gives a greater than 50% chance of winning. Please note that number 2 need never be revealed by Pradeep and we only learn some information about it at step 4.

Now consider this sequence of events (Puzzle B):

2) Jason sees number 1 and makes choice

I contend that in this case when Pradeep selects number 2 it is either higher or lower than number 1, with an equal probability of 50% to either outcome, and since Jason has already made his choice the chance that he made the right choice is exactly 50% also, regardless of the algorithm he employs.

If you agree with me, then the question arises what difference is there between Puzzles A and B such that in Puzzle A Jason achieves a greater than 50% chance of success but in Puzzle B he has only a 50% chance of success? My contention is that since no information is shared about number 2 until step 4, there is no difference probability-wise between Puzzles A and B because steps 2 and 3 are independent events, i.e. Pradeep’s selection of number 2 and Jason’s choice having seen number 1 are made without reference to each other. Therefore I contend this shows that Jason has a chance of 50% success in Puzzle A also, contrary to the assertion.

• Edger: you’re imagining two cases where the player sees N, either as one of the pair (M,N), or as one of the pair (2N-M,N), and asking how any strategy can distinguish between these cases, when in both you only see N. But the symmetry is broken not by what you see or what you do, but by what you would see and do if you had seen the other member of the pair.

In the language of the solution I described (which can be shown to be equivalent to Jason’s solution; the monotonically increasing function I call f would be the cumulative distribution function of whatever probability distribution he used to pick his threshold value), you will stick with the number N with probability f(N). But saying that you do, in fact, see N, does not mean it was impossible for you to have seen the other member of the pair: M or 2N-M. If your strategy is to stick with x with probability f(x), you would stick with these with probability f(M) and f(2N-M) respectively, and you need to account for the possibility that you could have seen them. The probability that you end up choosing the larger of the two numbers with that strategy will be:

(1) If M > N and the pair was (M,N), P(choose M) = 0.5 + 0.5 (f(M)-f(N)) > 0.5

(2) If M > N and the pair was (2N-M,N), P(choose N) = 0.5 + 0.5 (f(N)-f(2N-M)) > 0.5

(3) If N > M and the pair was (M,N), P(choose N) = 0.5 + 0.5 (f(N)-f(M)) > 0.5

(4) If N > M and the pair was (2N-M,N), P(choose 2N-M) = 0.5 + 0.5 (f(2N-M)-f(N)) > 0.5

The “information paradox” arises from the fact that the likelihood of a strategy succeeding needs to be computed over all possible contingencies, even if only a single contingency can actually take place. In any game with cards or dice, you would evaluate a strategy by considering the payoff it yields for every possible hand you could be dealt or every possible fall of the dice (weighted by their respective probabilities of arising), despite the fact that you might play just a single round of the game. (But because we don’t have any idea of how the two numbers of the pair in this guessing game were chosen, the best approach is to treat them as fixed but unknown, and evaluate the strategy by looking at the contingencies whose probabilities we do know: the 50/50 odds of choosing either number initially. If we then find that our strategy works regardless of the specific numbers in the pair, we know that it works, period.)

What makes this particular situation so counter-intuitive is that you learn absolutely nothing from the single number you see about which of the two numbers is greater. But it remains true that the only correct way to evaluate a strategy for this game is to include the fact that you were equally likely to have seen either number. And if your strategy makes it more likely that you stick with x than with y whenever x is greater than y (which you can guarantee by using a monotonically increasing function for the “sticking probability”), you will end up more likely to stick with the greater of the two, and win the game.

• Colin P says:

After Edger, I have another point I would like to be addressed. Let’s call the person who chooses the two numbers the “Host”, the person who attempts to guess which is larger the “contestant”, and the strategy first described by Jason as the “preferred strategy”. The preferred strategy involves an algorithm (choose a threshold, view one of the host’s two numbers, compare to threshold, make choice) which I would like to summarise as “Contestant sees number 1 and makes choice”. In this case I believe the puzzle as stated can be reduced to the following steps (Puzzle A):

1) Host selects number 1
2) Host selects number 2
3) Contestant sees number 1 and makes choice
4) Host reveals outcome

It is claimed that the preferred strategy gives a greater than 50% chance of winning. Please note that number 2 is never revealed by the host and we only learn some information about it at step 4.

Now consider this sequence of events (Puzzle B):

1) Host selects number 1
2) Contestant sees number 1 and makes choice
3) Host selects number 2
4) Host reveals outcome

I claim that in this case when the host selects number 2 it is either higher or lower than number 1, with an equal probability of 50% to either outcome, and since the contestant has already made his choice the chance that he made the right choice is exactly 50% also, regardless of the strategy he employs.

If you agree with me, then the question arises what difference is there between Puzzles A and B such that in Puzzle A the contestant achieves a greater than 50% chance of success but in Puzzle B he has only a 50% chance of success? I believe that since no information is shared about number 2 until step 4, there is no difference probability-wise between Puzzles A and B because steps 2 and 3 are independent events, i.e. the host’s selection of number 2 and the contestant’s choice having seen number 1 are made without reference to each other. Therefore I claim that this shows that the contestant has a chance of 50% success in Puzzle A also, contrary to what has been asserted about the “preferred strategy”.

• Let Agent Y be the person who chooses the numbers

Let Agent Z be the person who observes the numbers.

Y selects the first number. (n1) Whatever mechanism is employed and regardless of the type or classification of numbers by definition the first number is selected from an infinite set of numbers. The first choice is entirely random and therefore the information content [entropy S] is by definition 0. (S = 0)

Y selects the second number. (n2) This time because the ‘a priori’ condition is that the number is to be different it is selected from a set which by definition does not include the first number (n1). This selection is made from a theoretically non-infinite [smaller] set and the entropy or information content cannot by definition be 0 it has to be a finite value. The selection is not purely random. (S > 0). Call this information content ∆S

From the perspective of Y every time the test is run the first selection is always entirely random and has an entropy of 0.

From the perspective of Z ‘the observer’ there now appears a bias. If repeated trials are carried out then the information content of the number first selected by the observer will be non-zero, ∆S on half of the occasions.

Think this means that either (i) the strategy is to always stick to the first selection and as the number of trials approaches infinity the bias works in Z’s favour OR (ii) no strategy is required as over a very large number of trials approaching infinite the bias works in Z’s favour anyway.

• Paul Fabel says:

1) This puzzle is a variant on the 2 envelope paradox and was discussed extensively on wikipedia, stackexhange, and mathoverflow.

See for example this 2009 post:
http://mathoverflow.net/questions/9037/how-is-it-that-you-can-guess-if-one-of-a-pair-of-random-numbers-is-larger-with

2) The following switching strategy ( the switcher first selects x from a standard Gaussian and switches iff the revealed number is less than x) succeeds strictly more than 1/2 the time for each probability distribution by which the host has selected her pair of original numbers.
(the advantage arises when x is strictly between the pair, and otherwise has no effect).

3) This is not a get rich scheme for the switcher. Suppose the host starts with more money than the switcher, they play for the same fixed amount each round ( chosen at the outset by the host), and the loser is the one who busts first. The host can destroy the switcher even if the host must announce her strategy in advance. Here’s a winning strategy for the host: Each round they play for much much less than the difference in their starting bankrolls. On round N, the host picks x from a standard Gaussian, and then adds an independent y taken from a Gaussian with mean 0 and variance (.0001)^N to create the second number x+y. The ratio of the difference in starting bankrolls to the fixed bet overwhelms the round by round advantage enjoyed by the switcher.

4) Formally, is the original question ill posed without slightly more information about how the host selects her pair of numbers? The original question mentions probability but leaves it to the reader to guess/infer what this means. As noted in 2), the question is well posed if we assume each round the host employs some (unknown to the switcher,possibly varying each round, and allowed to depend on past outcomes) probability measure on the plane.

• jon says:

I think it helps to imagine converting the numbers from the real line to a finite interval (0,1) using a function such as arctan(x). Then both numbers are always between 0 and 1. We still don’t know the distribution is, but in some hand-wavy way we can simply pick an arbitrary number and declare that there is some non-zero likelihood that the second number is greater than that number. I wouldn’t want to call it a probability because that to me is a specific mathematical theory that needs careful definitions. The only information revealed by the first number is that the true distribution of numbers resulting from the process is not perfectly flat at that point. This problem seems confined to a nebulous realm where there is not enough information available to perform a proper analysis. One can jump to intuitive conclusions and declare that the probability is greater than 50%, but I think it would not be hard to conjure up a proof by contradiction that there cannot a real probability in the mathematical sense that is greater than 50%. I have in mind the type of proof that shows there there exist non-measurable sets.

• Marcelo says:

Hi Colin.

Jason’s method will work in both of your scenarios. In both cases, seeing the first number is informative about the likelihood of the second number being larger or smaller. In other words, if you know the value of the first number, you can compute the probability of second number being larger or smaller.

To understand this, let’s look at Jason’s method from another perspective. Consider that any number x, no matter how large or small, can be mapped to the [0,1] interval using a suitable monotonic function, for instance f(x) = 1 / ( 1+exp(-x) ). We do this because the value of f(x) can be interpreted as the proportion of all numbers being lower or equal to x. In other words, f(x) is the probability of a random number being lower than x, whereas 1-f(x) is the probability of a random number being larger than x.

Now, let’s call A and B the larger and smaller numbers hidden in the Host’s hands.
If we observed A, we know that the likelihood of the hidden number being larger than A is: 1-f(A). On the contrary, if we observed B, the likelihood of the hidden number being lower than B: is f(B). Since we have equal chances to have observed A or B (assuming that we chose one the host hands tossing a fair coin), the probability of a correct prediction is:

P=0.5*(1-f(A)) + 0.5*f(B)

re-arranging terms:

P=0.5+0.5*(f(B)-f(A))

Since B>A implies that f(B)>f(A) and therefore (f(B)-f(A))>0, we have that P is always greater than 0.5.

This explanation is not mine but extracted from here:
http://blog.xkcd.com/2010/02/09/math-puzzle/comment-page-1/

• Eric Wong says:

I think Jason is essentially correct, except that I believe there is not any limitation in choosing the “threshold”. It can be zero or “10 to the power 10 to the power 10″. It does not make any difference. Paradoxically, the most useful information to the problem is that we have absolutely no information about the numbers before the game begins.

Let G be the arbitrary threshold, n1 be the number you are about to reveal, and n2 be the other number.

Fact 1) For any real number G, there is a bijection between real numbers to the left and right of G.

Fact 2) Before the game begins, you have absolutely no information about n1 and n2.

So before the game begins,

P(n1 < G)=P(n1 > G)=P(n2 < G)=P(n2 > G)=1/2

(The probability that G equals to either n1 or n2 is infinitesimal and can be ignored.)

Because of fact 2, we can assume n1 and n2 are independent.

a) P(n1 < G and n2 > G) = 1/2*1/2 = 1/4
b) P(n1 > G and n2 < G) = 1/2*1/2 = 1/4
c) P(n1 < n2 < G) = 1/2*1/2*1/2=1/8
d) P(n2 < n1 < G) = 1/2*1/2*1/2=1/8
e) P(n1 > n2 > G) = 1/2*1/2*1/2=1/8
f) P(n2 > n1 > G) = 1/2*1/2*1/2=1/8

Using Jason’s strategy, the probability of winning = (a)+(b)+(c)+(e)=3/4, which is incredibly high.

• Paul Fabel says:

If we try to help the switcher by forcing the host to always offer a pair of consecutive numbers, a cash strapped switcher still CANNOT secure a long term advantage, despite favorable odds on each round.

To simplify and clarify the betting problem, suppose the host is forced to announce HOW she selects her pair of numbers, and ALSO on each round to offer a pair of CONSECUTIVE natural numbers, for example 6 and 5 or 127 and 128. Can the host still secure a likely long term win if the host has a slightly greater initial bankroll and can name the fixed betting amount at the outset? Yes!

Here is the host’s strategy. On round N the host first selects uniformly a natural number n from {1,2,3,……,N^N^N^N} and then tosses a fair coin to decide if the 2nd number is n+1 or n-1.

Given P<1, and the initial bankrolls, the host can select a betting amount A so small, that repeatedly playing for stakes A until one or the other player busts, the host will win with probability at least P, regardless of the (essentially irrelevant) strategy of the switcher.

In other words, the host can effectively make the contest an almost unbiased random walk, starting at zero, between the barriers of her bankroll and the negation of her opponent's bankroll, and choose the step size A so that the tiny bias favoring the switcher has almost no chance to offset the huge advantage of the larger initial bankroll of the host.

• Edger says:

I’m sorry for the poor grammar on my previous post everyone.

Paul: Thank you, I think you and the MO post answered my question.

The information, and the break in symmetry in the problem come from the fact that you want a probability. And that in order to obtain a probability you must deal with a specific probability measure. In that case, there’s no question that if it is given that the host chooses to use a specific probability measure to choose the two numbers then the solution given is indeed a solution. And most importantly, as is stated in the MO post, the gain over 50% in probability depends on the probability distribution. This is all good for some reasons, but also unsatisfying for other reasons:

1) It is not the setup Pradeep proposed (which might be ill-posed to begin with).

2) Yes, you get greater than 50% but you’re left with the following unsatisfying trivial result: This is basically the setup in Paul’s point 3). Let epsilon > 0 be given. Assume you are the contestant. Assume the host uses a certain continuous probability distribution to choose one of the numbers. The other number is chosen in a manner Paul describes in his point 3), that is, probabilistically very very close to the first number. Then you can not say that your strategy will give you a success rate of at least (50 + epsilon)%. And yes, I know this is not what you were asked for. In other words, if the experiment is conducted over and over, infinitely many times, whereby the variance in the second number, given the first, is made smaller and smaller, then the strategy will average out to 50% over all the trials. In a sense, in the limit the two numbers are allowed to become equal.

The break in symmetry in one individual trial comes from the guarantee of a non empty interval between the two DISTINCT numbers, regardless of what numbers are chosen, and that a probability distribution will always add weight so some such interval. That is, the probability measure on the plane must assign a measure of 0 to the diagonal. The symmetry is restored in the repeated trial case because the limit of probability measures need not be a probability measure, in the sense of distributions.

• Jamie H says:

Let me try this again. I’m not a mathematician so I cannot use the lingo.

Begin by using the “Jason” solution wherein the player picks a guide number to determine the “Keep or Trade” play after the first number is revealed (If greater than the guide number, keep it, otherwise trade it for the 2nd random number).

There is a subset of possible random number pairs between which the guide number will ALWAYS fall. IF Jason chooses the guide number ZERO, then fully HALF of all pairs of random numbers offered over time will fill this condition.

In this Case, Jason then wins HALF of the time: If the first number revealed is greater than ZERO, he keeps it…and wins. If the First number revealed is negative, he trades it…and wins.

Therefore, by winning the remaining games of the other possible Cases (wherein both random numbers are either 1) larger than or 2) smaller than his guide number, ZERO) at the 50-50 chance-rate, Jason can accrue a total Win score of 75%! (All of the 50% in Case 1, above, plus half of the remaining 50% for the other cases).

Naturally – as the rules point out – this would require a truly random distribution of hidden and revealed numbers.

• sagef says:

so is a lesson with respect to this problem:
we can with our imagination, in a sense ‘reach’ into the unknown randomness sorta stuff and come up with genuine useful stuff, sorta thing?
such as in the implementation of the scientific method, sorta thing eg. postulates, experiments, application of math…

• Paul Atkins says:

Strategy:

If the first number is less than zero switch it otherwise keep it.

Reason:

Both numbers are selected from the set of all numbers which extends from -∞ to +∞
The mid point of this set by definition is 0 and is known
If the first number is less than 0 there is a probability of > 0.5 that the second number will be larger therefore switch it.
If the first number is greater than zero then there is a probability of < 0.5 that the second number will be the larger therefore keep it.

Where does the information come from?

The mechanism for generation of the numbers is unknowable therefore to all intents random [Shannon]
The endpoints of the set from which the numbers are selected, -∞ and +∞ are unknowable
But the mid point 0 is known. This is where the information comes from.

• Eric Wong says:

Further to my previous comment, I would like to justify why it is reasonable to assume n1 and n2 are independent. I have used the principle of maximum entropy. There is a theorem in information theory that the joint entropy of two random variables are maximum when they are independent. H(x,y) <= H(x)+H(y) with equality when x and y are independent.

• g g says:

In your comment on the discussion you state:
“Obviously this guide number encodes no specific information about, and has no connection to, the unknown number. Yet it succeeds in increasing your chances of picking the larger number.”

I do not think this is a full description of the process. The strategy involves TWO random choices: The first choice is which of the two hidden numbers to see and only the second choice, whether to switch or not, involves the random sample.

Your statement describes the situation after the first choice has been made. But this is incomplete because, as Greg Egan pointed out in another comment, you need to consider all contingencies. The success of the strategy ultimately relies on the comparison of the two outcomes in the first step. The joint relevance of the two alternative outcomes creates the connection between the two numbers.

I am pretty sure (without having actually done it) that all these questions can be neatly resolved by a careful description of the two-stage experiment and the respective conditional probabilities. Of course this analysis would remove all the intuitive appeal of the problem and most likely be comprehensible only to people having some familiarity with probability theory.

• John Hebbe says:

The host holds two different numbers, one in each hand. He shows you the number in the hand of your choice. Is it larger than the unrevealed number? Should you swap?

You arrived with two unknown but different numbers, each in an unmarked envelope. Randomness of these four numbers is unimportant but none can be changed once the game begins. The host is indifferent to the fact that you look at one of your numbers. Based upon what you see, you make a decision. This exercise is repeated indefinitely. You come out ahead.

At the outset, the game objective is to determine the higher number. The game began with two numbers, one revealed. No other information. You have introduced, for your own personal use, a third piece of information.

The number showing in the host’s hand is central. He is unconcerned about your strategy and awaits your direction. The game objective is clear. But now this is now a three number game. Vaguely similar to Monty Hall with a twist.

The host showed a number. You opened an unmarked envelope and found a second number. Your number was a lower number. With this second number being lower than the host’s number, mathematical odds are that the next random number revealed will be higher than the central number in order to achieve the long range statistic of 50% probability. Half higher. Half lower. Pick the host’s other hand in this case.

Likewise, if your number is higher than his, stay with his original number. Bear in mind, the game, per se, is impersonal with respect to inputs. The source of any given random number in a series is, by definition, immaterial.

Why the second envelope? If the number in the first envelope was identical to the number in the host’s hand, no new information was provided. My final entry. I apologize for the lack of rigor.

• John Hebbe says:

I notice that in Wikipedia; The Two Envelopes problem, a solution similar to the one offered above appears in the final section entitled Randomized solutions. This may have more appeal to those demanding more rigor. The citation states this: Counter-intuitive though it may seem, there is a way that the player can decide whether to switch or to stay so that he has a larger chance than ½ of finishing with the bigger number, however the two numbers are chosen by the arranger of the game. However, it is only possible with a so-called randomized algorithm: the player must be able to generate his own random numbers. And so on. . . .

I had not read this previously but appreciate this indirect support for my solution.

• sagef says:

@gg: concerning @Pradeep: In your comment on the discussion you state: “Obviously this guide number encodes no specific information about, and has no connection to, the unknown number. Yet it succeeds in increasing your chances of picking the larger number.”
just me maybe but the above brings up what to me was (hopefully a correct (hopefully my terminology is correct)) realization that all three numbers (in their original state) are ‘connected’ and arose from the same set, the set of random numbers. can’t really remember any reference to a set of random numbers from my formal education days, but i expect such a set sort of exists,at least theoretically maybe, lol.
the act of selecting the guide number is like decoding a random number, same thing with selecting a hand to show a number at first. then we do some further decoding when we take an average of the two ‘collapsed’ now known numbers.
the question comes to my mind: as one plays the game would it be worth it to keep stats on the previous plays?
a really weird question would be: is it unwise to wait to dream up your guide number until after seeing your first hand selection number. lol

• Paul Fabel says:

The previous post did not parse correctly— it would be helpful if commenters could preview or delete their own garbled posts before moderation.

>>Today’s puzzle asks you to believe something that seems impossible — that you can somehow win at a number guessing game in which you have absolutely no information.

NO information? But the contestant has information! The contestant knows one of the numbers and also knows the other number is different from the known number.

And the `win’ is of a staggeringly weak nature, since the host can set the upper bound on the contestant’s chances.

For example if the players agree to play for 100000000000 rounds at \$100 per round, the host can easily ensure the contestant’s total expected profit is less than 1 cent, regardless of the contestant’s strategy.

In similar vein, if both players have equal starting bankrolls and they play until one or the other busts, for each p>>Is there a strategy that will give you a greater than 50 percent chance of choosing the larger number, no matter which two numbers I write down?

Yes, there exists a single contestant strategy so that for each pair of distinct numbers x and y chosen in secret by the host, the strategy has a strictly greater than 50% of winning.

(See earlier posts by Jason, Erica Klarreich, Edger, myself, and others-or read the section on randomized solutions to the 2 envelope problem https://en.wikipedia.org/wiki/Two_envelopes_problem)

• Colin P says:

With apologies for the length of this post…

Hi Marcelo and thank you, but whilst I am happy to be proven wrong I do not think you have done so yet, and if you will then I would appeal to you to address those puzzles A and B in my earlier comment, together with the line of reasoning that accompanies them, as an exercise in logic and deductive reasoning, which is how they are presented, and not as an exercise in arithmetic reasoning. Can you find the flaw in my deductive reasoning without resorting to arithmetic reasoning?

You see, I believe the really counter-intuitive thing about this puzzle is not why the arithmetic reasoning described by Jason is right, but why it is wrong. After all, as a piece of arithmetic it is staring us in the face! Surely it is right? But ultimately it has led you to state, “if you know the value of the first number, you can compute the probability of second number being larger or smaller.” In other words, with knowledge of just one number N1, you can predict with a probability different from 50% whether another number N2, randomly chosen, will be larger than N1; and I would claim that this is precisely a type of “proof by contradiction” (quoting Jon) that this arithmetic reasoning contains a flaw.

So I am asking you to find the flaw in my deductive reasoning in the puzzles A and B comment. But as a dissenter it is incumbent on me to try to find the flaw in the arithmetic reasoning too, isn’t it?

Well, I believe the problem is that the particular arithmetic reasoning, and other similar ones, are attempting to deal with “infinities” in a non-rigorous way, those infinities being either explicit and mentioned, or implicit and not mentioned, as in the particular arithmetic reasoning under consideration. And standard arithmetic does not deal well with infinities because as I am sure all here know if one is not careful one can end up with very incorrect results (∞ + 1 = ∞; deduct ∞ from both sides and one has 1 = 0). I believe these infinities and the difficulty of dealing with them rigorously can be avoided by treating the puzzle not as one to be tackled by an arithmetic solution, but as one that is better tackled through logic – for example the deductive reasoning of puzzles A and B.

So why does the arithmetic reasoning look so appealing and where do I claim is the flaw? I believe you can think of it like this. The arithmetic reasoning is persuasive because in our every day experience, indeed in our entire lives, we are conscious of, and only ever deal with, a tiny part of the real number line. So it seems quite natural to think that all numbers that might be selected will somehow fall within the gambit of our experience. But really we are dealing with a much, much, larger issue than what our experience covers. For example a very large number described by (but not invented by) the late mathematician and mathematical puzzle master Martin Gardner is a “googol”, that is 10 raised to the power of 100. That’s a very big number obviously. He went on to describe an even larger number, in fact an incredibly large number, the googolplex, which is 10 raised to the power of a googol. That is a mind-bogglingly large number, it’s a 10 raised to the power of a number which is 1 followed not by a hundred zeros but by a googol of zeros. But large though it is to us, to a god-like entity that can grasp the infinite, which none of us are, the distance from zero to the googolplex is a mere pin-prick on the real number line. Such is the nature of infinity. And my point about the arithmetic reasoning is that given any two real numbers X and Y, the probability that a randomly chosen number Z lies somewhere between them is… zero! And that’s because you can show, by considering more and more of the real number line, that you can make this probability arbitrarily close to zero, and in the limit equal to zero. So in the arithmetic reasoning the infinities lie in the amount of the number line that lies beyond the area under direct consideration. For example if N1 is less than N2 then it is the amount of the number line that is less than N1 and greater than N2. These are both infinite amounts of number line, they make the amount between N1 and N2 trivial, in fact in the limit they make the chance of threshold T being between N1 and N2 zero. I know, sharp intakes of breath all round, counter-intuitive isn’t it? The problem is not really with our intuition, it is with arithmetic involving the infinite.

So to me this is the really counter-intuitive thing about Pradeep’s puzzle, not that the proposed solution is somehow correct, but that it isn’t, for we have an apparent arithmetic proof that it is, but also (I claim) a proof by contradiction that it isn’t.

As an aside, I believe the function 1 / ( 1+exp(-x)) you mention is useful for certain things, but the final range of 0 – 1 is not useful for comparing likelihoods of selecting different parts of the real number line because it does not give equal weight to different parts of the real number line.

Incidentally, the puzzle begins with the words, “I write down…” One might infer from this that we should assume we are dealing with a finite part of the number line – whose upper and lower bounds could be numbers that are writable on a piece of paper for example – in which case the infinities disappear and the arithmetic reasoning holds good. But I don’t believe that this particular sleight of hand is intended by Pradeep. Could be wrong of course, that could be the source of the information he mentions.

But if my attempt here to find the flaw in the arithmetic reasoning leaves you unconvinced, then why not make your own attempt to find the flaw in my logical reasoning in the puzzles A and B discussion instead.

Thanks again.

• Eric Wong says:

As a afterthought, I think my argument that the two numbers n1 and n2 are independent is not foolproof. I now have a simplified, more convincing argument, though the result is weaker:

Select a real number before the game begins. The real number can be generated without any limitation. It does not need to follow any probability distribution. It can even be a fixed number each time. It may be 0 or 10 to power 100. Call the number G. Let n1 and n2 be the two numbers in envelopes.

If both n1 and n2 are on the same side of G, then using Jason’s strategy, we have 50% chance of winning. However, given that we have absolutely no information about n1 and n2, we cannot be 100% certain that both numbers are on the same side of G. In other words, there is always a non-zero probability that n1 and n2 are on different sides of G. In this case, Jason’s strategy must win. Hence, the overall probability of winning is strictly greater than 50%.

• g g says:

Since most of us agree on the successful strategy for choosing the larger number this post will answer the two remaining questions:

1. Where or how is the information created?

2. How can information about one of the numbers tell us something about the other number?

Let’s fix some terminology first. The two numbers are called A and B. The successful strategy is a two stage random experiment.

The first stage of this experiment is to CHOOSE A or B with equal probability 50%.

The second stage is to TEST the number chosen in the first step. This means a sample is drawn from an arbitrary distribution on the real numbers (technical caveat: with non-zero mass for all numbers). The test is called SUCCESS if the sample drawn is less than the chosen number. Otherwise the test FAILED. The probability of success for the test of A is called p_A the one for B is p_B.

This two-stage experiment can be visualised by a tree which branches at each stage. It has a root node, two nodes after the first stage and four nodes (which are leaves) after the second stage. (There seems to be no way to upload such a drawing, so you must do this for yourself.)

Now to the questions:

1. Where is the information created?
Information is created in each of the two stages. This gain in information is evidenced by decreasing probabilities of events and the elimination of possible events after each stage has been performed.

Before performing the first stage there is only one node in the tree, the root. So the probability of being in that node is 100%. No probability can be larger than this and this state has the least possible amount of information.

But after the first stage you are either in the branch of the tree where A was chosen or in the branch where B was chosen. In both cases the probability of being in a node has shrunk and is now only 50%. Note further that before stage one all four ultimate outcomes were possible (A success, A fail, B success, B fail). After stage one only two possibilities remain: Either the two outcomes of the A trial or those of the B trial.

The same thing happens again when you do the stage two experiment. Let us assume A came up in step one. You perform the test and the probability changes. What was before 0.5 is now either 0.5*p_A or 0.5*(1 – p_A) depending on the test result. Again the probability has decreased in both cases, reflecting the gain in information. The number of possible outcomes has likewise reduced to only one which means you have certainty about the ultimate outcome.

In total the two-stage experiment makes sure that you move from a pre-experiment state without any information about the four outcomes into exactly one of four clearly defined and distinct states.

Obviously the reasoning above applies more or less in the same way to every two stage experiment. On the one hand this shows that there is nothing unusual about the creation of information here on the other hand this cannot be the full picture yet, since there is no connection with choosing the larger number. This connection will be established by the answer to the next question.

2. How can information about one of the numbers tell us something about the other number?

This question seems difficult at first, since the information gained is about the four ultimate outcomes of the experiment and not about the numbers directly. In a way this should not come as a surprise. Even with the successful strategy you don’t know the larger number for sure, you can only guess it with a probability larger than 50%.

This is where the relationship between the probabilities p_A and p_B and the respective numbers A and B becomes relevant. As was pointed out in other posts before the crucial fact is: p_A < p_B if and only if A > B. But from this relationship immediately follow relationships between the probabilities of the four ultimate events of the experiment.

Assume for example that A > B:
In this case you know immediately that the event “choose A in first stage and A success in second stage”, has a higher probability (0.5*p_A) than the respective event from the B-Branch (0.5*p_B). This is clear from the construction of the experiment alone, there is no magical “transfer of information” from the A branch to the B branch required. Likewise the event “choose B and B fails” has a higher probability (0.5*(1 – p_B)) than “Choose A and A fails” (0.5*(1 – p_A)). Exactly this connection is exploited by the successful strategy: For both events with larger probability A is proposed by the strategy as candidate for the larger number. Of course this is the smart thing to do under the assumption that A > B.

It is easy to see that the relations between the probabilities in the case A < B is equivalent to p_A > p_B enables you to draw conclusions about all relative probabilities of events and thus about a successful strategy for choice.

As a side remark it is worth pointing out that the successful strategy not only concludes something about a number which was never disclosed based on a number completely unrelated to it. But that it is capable of picking the larger of two numbers (with probability larger than 50%) without seeing any of the numbers in the first place. A careful review of the above will reveal that the actual value of the number chosen in the first stage, has neither bearing on the four ultimate events nor on their probabilities. For the second stage and hence for the full strategy disclosure of the test result alone suffices. Again this should not come as a surprise, since the strategy should work for all numbers, irrespective of their value.

3. Conclusion
The facts behind the answer to 1. and 2. together make the strategy possible. The two stage experiment described in 1. makes sure you end up in one of four distinct events, each having clearly defined probabilities whose relative size with each other is related to the relative size of p_A and p_B.

Then you can apply your knowledge of the relationship between those probabilities and the size of the numbers as described in 2. to take a decision which maximises for each event the probability of picking the larger number.

• Ravi Kumar Meduri says:

A great puzzle and pretty amazing that from the arbitrary guide (which, as Pradeep says, need not have any relation to the two numbers), there is some how magic created that you can now make a better than 50% probability decision on which number is higher. It is a beautiful transformation from the unknown distributions of the two numbers to a known reference.

What continues to intrigue me is what caused this asymmetry that the probability is now no longer 50% but more than that.

The tiny probability, as many have pointed, that the guide lies between the two numbers fundamentally arises out of the fact that the two numbers are different. So in a way, the statement that the number we know has no bearing on whether the number in the other hand is smaller or greater while being true rules out the case where the unknown number is the same as the disclosed number. That is what we exploit. Not being equal can be greater or smaller but that does not matter.

Once you have two numbers and you have a guide in between, it reduces to the first bonus problem (two numbers between 0 and 10). What is beautiful that in the first bonus problem, the guide need not be 5. It can be even 1 (or for that matter number 9 – in fact, any number between 1 and 10) and you still have greater than 50% probability. Similarly, all that matters is that the guide is in between the two numbers and that is enough to give that tiny advantage. Of course, the probability increases if the guide is exactly between the two numbers.

• Jamie H says:

To Ravi Kumar Meduri: The logic in your first two paragraphs of you July 20th post, above, is sound to me – and has been expressed by others here. But your statement starting paragraph three, “The tiny probability, as many have pointed, that the guide lies between the two numbers …” is misleading, because in fact, isn’t it true that for a number in the middle of an infinite distribution, i.e., zero, fully half of all cases will result in that guide (zero) being between the random two numbers? That is not a tiny probability at all, if the game is played for a sufficient number of rounds. And all of these can be won!

• Tom (or is it Ray) says:

I know this is Quanta Magazine and not a Reditt thread and I am not trying to be a troll..

But if this was a “puzzler” on Car talk I think Ray (or is it Tom) will have this reaction:

“Bo – o o o o o o gus!”

If you cannot make any assumption about how the numbers were generated, then there is know way you can make any guess just by looking at one number.

• John Hebbe says:

Thank you Dear Editor, for providing this engaging challenge. Given: (1) There have been no recent entries proposing solutions significantly different from any appearing earlier. We seem to have run out of gas. (2) The more esoteric submissions have gained widespread support. (3) The authors of these solutions are now ‘fine-tuning’ their entries. My fine-tune follows. Conclusion: The contest will end shortly and we can stop holding our breath.

The indirect support for my solution appeared in the Wikipedia entry “The Two Envelopes problem” which I found after developing my approach independently. These attributions appear: “This variant of the problem, as well as its solution, is attributed by McDonnell and Abbott, and by earlier authors, to information theorist Thomas M. Cover.[29] ” The next sentences state: “Counter-intuitive though it might seem, there is a way that the player can decide whether to switch or to stay so that he has a larger chance than 1/2 of finishing with the bigger number, however the two numbers are chosen by the arranger (host) of the game. However, it is only possible with a so-called randomized algorithm: the player must be able to generate his own random numbers. Suppose he is able to produce a random number, let’s call it Z, such that the probability that Z is larger than any particular quantity z is exp(-z). Note that exp(-z) starts off equal to 1 at z=0 and decreases strictly and continuously as z increases, tending to zero as z tends to infinity. So the chance is 0 that Z is exactly equal to any particular number, and there is a positive probability that Z lies between any two particular different numbers. The player compares his Z with the number in Envelope A. If Z is smaller he keeps the envelope. If Z is larger he switches to the other envelope.” So you can argue with me but theirs are heavier guns. I’d like to provide the similarities between their collective, educated analyses/solutions and mine. I feel guilty of plagiarism in a sense.

With some difficulty, you can see the parallels of our solutions. You have to keep ‘Z’s and envelopes sorted out. This and how to properly set up the resulting probability equation. My formula construction which follows may not be worded right but the reasoning behind it is sound and meant to agree with the citations.

In the final analysis, the concluding statement in their solution is this: “To be precise, the probability that he ends with the ‘winning envelope’ is ½ + P(Z falls between the two numbers)/2.” Or, in my solution, the probability that the player’s decision to swap or not is based upon his whether his number is higher or lower than the host’s number) is ½ + P(players random number falls between host number and host hidden number)/2.

• Wiley says:

Nice column. Look forward to solving more puzzles.

Just would like to add a twist and point out one relevant generalization of the original puzzle, which is commonly known as the secretary problem or the googol game.

From Marin Gardner:
“Ask someone to take as many slips of paper as he pleases, and on each slip write a different positive number. The numbers may range from small fractions of 1 to a number the size of a googol (1 followed by a hundred 0s) or even larger. These slips are turned face down and shuffled over the top of a table. One at a time you turn the slips face up. The aim is to stop turning when you come to the number that you guess to be the largest of the series. You cannot go back and pick a previously turned slip. If you turn over all the slips, then of course you must pick the last one turned.”

For the case of 2 slips, we have learned through the discussion, there is a strategy that you can pick the largest number with probability strictly greater than one-half (albeit ineffective). However, the solution to this googol game is the so-called 1/e law – apparently the solution for n=2 does NOT generalize! For example, with 3 slips and the best strategy, it had been proven that one could only achieve one-half probability (the proof is more general and states that the optimal stopping strategy can only depend on the relative ranks of the numbers written down).

So here is my question, why is n=2 special? Why does your arguments NOT apply for n>2? Where does this extra piece of information go?

• Ravi Kumar Meduri says:

To Jamie H – I would agree with you fully that if you know that the numbers are being drawn from an infinite distribution with zero as the median, then the guide can be zero and the probability is not small (75% in fact). My last sentence that the median maximises the probability said exactly that. However, the way the problem is stated, you do not have even that information. That is why, the Wikipedia article says that the numbers are strictly positive.

All I was saying is that fundamentally the asymmetry (> 50% probability) arises from the fact that once the two numbers are different (or could be different), you can be in between and you break the symmetry of 50% by having the guide help you take decisions at better probability than evens. This is just like how a guide of 1 in the first bonus problem helps by at least helping you to take the right decision between 0 and 1.

• Francois says:

If the number is negative, I pick the other hand, if it is positive I stay with it.

• Francois says:

If the random generator use a symmetry around 0, the (discard negative and keep positive) strategy should yield positive results I think. I think such symmetry is likely to occurs in opponent random generator. If there is a symmetry but not around 0, you might be able to crack it over time, and then exploit it the same way. Same reasoning should apply with min/max number if existing.

• J2 says:

A couple of quick observations.

1. If Pradeep gets to pick which hand he shows us, the strategy “swap if shown value is less than t” can, for the wrong choice of t, be guaranteed to lose. For example, “swap if shown value is negative” is a lose if Pradeep always shows us the smaller of two positive numbers. Our free choice of initial hand is critical.

2. A related higher-or-lower game. A computer, which can be trusted to play each game independently and identically distributed, generates a stream of random numbers, R_1, R_2, R_3, …. You pay one penny per random number, winning a prize of one million pounds when the computer spits out some R_n that’s bigger than R_1. How much do you expect to gain from the game? (Don’t play this one at home, kids.)

• Ian says:

Just to point out, if it hasn’t been so pointed before, that the problem is (deliberately, I’m sure) vague. Not only do we not know how each number will be generated, but we don’t even know that the same selection mechanism will ever be repeated (although, granted, finding many different mechanisms is clearly going to challenge the setter’s ingenuity). And without that, it seems to me that there’s a limit to what we can do in trying to accumulate information on past results as a guide to the future (which, in essence, boil down to trying to learn more about “the” mechanism).

My own first thought was to stick with the simple, and go purely with the first digit – swap if it’s less than 5, stick if it’s higher, toss a coin if it IS 5. Although I’m also torn by a feeling that I ought, vaguely as per Liam, to go with Benford’s law, and swap only if the first digit was a 1 or 2 (those being the only first digit values where numbers encountered with higher first digits are statistically more prevalent than numbers with lower ones). Can’t make up my mind whether that’s a blind alley or not, though (and tbh I have no idea how to approach the analysis!).

• sagef says:

@ Ian, i tried your way in excel using two hundred random numbers (100 for each hand). eg having excel choose a hand depending on the first digit of the hand reveled, as you described.
the results over a thousand trials or so were consistently above 60% winners. no where near going near the law of large numbers but just saying your way looks promising.
sorry if the partial example snippet from excel below is poorly formatted.

guess actual
hand hand hand picked largest hand # won total winners
1 2
% correct
1 0.69874 0.797472 1 2 FALSE 76 76.00%
2 0.394047 0.476221 2 2 1
3 0.314367 0.043639 2 1 FALSE
4 0.246315 0.787651 2 2 1
5 0.432576 0.704018 2 2 1
6 0.805849 0.400179 1 1 1
7 0.529443 0.153092 1 1 1
8 0.54313 0.932932 1 2 FALSE
9 0.252285 0.180941 2 1 FALSE
10 0.171844 0.330502 2 2 1

• Francois says:

Yes I agree Ian it is vague. I think that what the columnist wants us to think is not to try to arbitrate randomness, but more the random generation algorithm used by opponent. Of course we have to suppose some kind of consistency. Thinking at true random generator (for example quantum one), it seems that they are either binary, or must return some kind of distribution, but never something uniform over (-inf, + inf), otherwise you would have null probability to get a number with absolute value inferior to any arbitrarily large number – seems physically impossible. So in the transformation algorithm you must have a upper bound and lower bound or some kind, that you can arbitrate by comparing your number to the middle of the range.

• Francois says:

So as a strategy I will switch hands a certain number of time to see a lot of number quickly, noting the smallest and biggest ever encoutered. After a certain time (but we can do it right away) we use the standard comparison the range middle, while still adjusting range bounds when bigger or smaller number are encountered.
Of course we are supposing that the random algorithm used is uniform over the range, which is not specified.

• Colin P says:

I would like to know if the proposed solution can be distinguished from random noise. What I mean is, imagine the following…

A mortal being M has two machines labelled X and Y, each has a coin slot, and each has a coin return tray in which the inserted coin will re-appear either heads up or tails up. M may insert a coin into each machine as often as he likes and record whether the coin returns heads up or tails up.

M knows that inside one of the two machines X and Y (but he does not know which) sits a godlike being G0 who, when a coin appears through the coin slot, generates a 1 or a 0 randomly and if he generates a 1 he returns the coin heads up and if he generates a 0 he returns the coin tails up via that machine's coin return tray. Also M knows that inside the other machine (again he does not know which) sit two godlike beings G1 and G2 who, when a coin appears, play Pradeep's puzzle, G1 as host and G2 as contestant, and when G2 ends up with the higher of G1's two numbers then G2 returns the coin heads up, and when G2 ends up with the lower of G1's two numbers then G2 returns the coin tails up via that machine's coin return tray.

Can you advise M of a way to work out in which machine, X or Y, Pradeep's puzzle is being played, using the stream of heads and tails being returned as a guide? In other words can M work out which machine returns coins with heads up more often than could be attributed to a chance favouring of heads arising from the random walk associated with tossing coins?

• sagef says:

just want to say that in trying to simulate the problem in excel as i attempted to do with Ian's solution of "when shown first hand then keep hand if first digit is above five and switch hands if first digit is below five, flip a coin if the first digit is five" that i was unable to produce a 'satisfying' stream of random numbers. it seems that excel is only able to produce pseudo random numbers within a given range, so the use of excel for the problem is limited to special cases, unless perhaps some one introduced some random number generating software code into excel as a macro, sorta thing.
well anyway i do think Ian's solution is promising for the overall case. one thing i believe i learned from trying to simulate the problem in excel is just how apparently hugely dependent having the winning strategy is on the numbers in hands being 'truly' random.
i find it interesting that one can use that first digit of the shown hand as the 'guide' number that i believe it was Jason and others wrote about, and doing so fits in well with Ian's solution.

• Jamie H says:

To Ravi Kumar Meduri: Thank you for the polite reply! I understand the basis of the asymmetry you propose and concur completely. Perhaps I was nit-picking…

To "Tom (or is it Ray)": Not bogus at all! Look at some of the other responses here and you should see that – for a sufficient sample size (i.e., numbers of "turns" at the game), if you assume a random distribution, there will be a non-zero (and potentially very large) number of times where you can indeed beat this thing. That is the surprise that Pradeep writes about.

This doesn't necessarily mean you can beat it the first turn, of course.

• Max Rockbin says:

Given the Posted answer, the question is,
What is the probability that G lies between A and B?

As the problem is stated, the probability is arbitrarily small. That is, for any probability P, it is trivial to show that the probability of a random integer selected from the entire number line has a smaller chance. "Arbitrarily Small" means 0.

So the problem should be re-stated to assume A and B are bounded inside some finite interval (you don't have to say how big the interval is. You can say it might be of any size. And Then G would be selected randomly – but not outside that same interval). Of course bounding to a finite interval makes the problem much more obvious.

Is that wrong? If A,B and G are selected from the unbounded line, can the probability of G falling between A & B be proven to have some value greater than 0?

• Francois says:

I would like to make the following proposal to you, for the case of a fixed random generator :

1) this game is all about hacking the way opponent generate random number (which can be real random or pseudo random or chaos – it does not matter)
2) it is not physically possible to draw a number uniformely from (-inf, +inf), or (0, +inf). It is not making sense mathematically either, since all proba to have one number (or range in continuous case) are supposed to add up to one, the proba to have one number or a certain range of number is zero.
3) hence we can break either the uniform or infinite condition which yield two possibility for random generation :
a) the range of possible value is non-infinite , which can be then equi-probable . So there is maximum and a minimum bound (quantum measurement of spin for example)
b) the range is continuous and infinite, but with a non uniform density (typicaly bell shaped curve in many natural example for example measurement of the position of a single diffracted photon for true randomness)
4) in both case, we can hack the specificity of the distribution over the long term:
a) by noting the maximum and minimum number ecountered. Then we compare to the middle of the range, and discard if inferior or keep if superior
b) by noting all values, and comparing with the average of all value encoutered. Discard if inferior to average, keep if superior.

If we suspect that other player is using a more elaborate way (with no symmetry for example) then the goal is to find the median of the distribution over the long term (with law of large number):
c) keep track of all value, order them and count them, and then get to the median : if we have n value we compare to the value of the n/2 number (or average of two middle number if n is odd)
We can use this last method for case a) and b).

• Regarding the problem posed, I have no reason to believe that this problem is any different than any other 50:50 problem. That is, it is no different than tossing a coin. And what is and should be astounding is that you claim to be able to beat those well known odds. Well, that will be interesting to see!
The reason your problem is a 50:50 problem (as initially stated, not including the bonus) is because, there are only two possibilities, either it is higher or it is lower, and it cannot be the same (a coin landing on its edge.) The only reason a coin toss is 50:50 and “fair” is because the player has no idea, no information that would lead him to believe otherwise. In the case of your problem here, the range of numbers can be theoretical, and we note there is no information available to us, to prejudice it being known. With no information about the outcome, and exactly two options before us, it is a 50:50 problem, a coin toss problem.
Now theoretically speaking any coin toss might not be exactly 50:50, but we are constrained by definition. We recall, “We have no information…” and the initial draw is not related to the second number. In actuality then, the answer can be theoretical as well, not necessarily proven/ defensible by empirical method. The idea of using a “guide,” some imaginary number, that pops into our heads, is simply a diversion and shouldn’t be relevant, not with independence.
If you’re not satisfied with the coin toss analogy we could see it a different way. If we normalize the problem such that we substitute the numbers (in the initial formulation), which are either larger or smaller, by normalizing them to either -1 or 1 and let the number in the hand, the first number, be a zero, now we can see that it is clearly a 50:50 option problem, and we’ve simplified it to essentially three types of outcomes, rather than the numbers themselves. We start at zero, and then go up or down. In the bonus problem, we can see that since we know the range, 0-10 we will always win (if we play a decent amount of time), but in a generated range without bounds meaning, “you don’t know how I generate the number” then a -1 or 1 suffices to represent the options.
If it is in fact shown that there is a means to “know” a best case outcome ahead of time, then I believe you’ve contradicted your initial premise. Information is/was available somehow, somewhere and the observer and “tosser” are not independent of eachother, but collude. And that is another key point that has not been brought up, independence. To have a fair toss, the player cannot in any way be a part of the outcome of the toss, or in this case, of the choice of numbers. Just as one can toss a coin forever, so too is a limitless number generator generated by a computer; a coin flies through the air differently, each time and in a sense generates “numbers”… acceleration deceleration, momentum etc. One is a mechanical model, one is not. Since you brought up information theory and “selection” , it’s rather clear also, that this exercise is meant to support the notion of some kind of quasi-selection driving or enhancing order, which will also be interesting to see. It is all somewhat reminiscent of the claims of self-organization in molecular systems claimed by (Sousa 2005, Russell et al 2014, and Lane et al, 2010) regarding self “selecting” chemistries. The mystique of selective power that you infer from this sort of game, is invoked by these papers, but nonetheless, will not provide more convincing evidence of the ability of molecules to select themselves. However, I look forward to seeing how you show randomness’ ability to generate order.

Full disclosure: I am the brother of the author. However, this does not give me an inside track on this puzzle, I have never seen it nor discussed it before. The only benefit it gives me is that I have grown up with puzzles, grown up loving puzzles and been wrong so many times, that am not afraid of being wrong again!

Consider the description of the numbers generated in the original puzzle:
– "You have absolutely no idea how I generated these two numbers."
– "No information about the unknown numbers is available to you. I could be a robot or an alien, whose ways of thinking are absolutely foreign to you, or I might use an unimaginably wacky algorithm to generate my numbers."
I think we need to make the assumption that these are real numbers – since one is known to be greater than the other.
This description suggests that we should not be surprised to see any number pop up in the first hand – it could be anywhere in the range negative infinity to positive infinity. And were both the numbers to be truly random numbers from this range, the probability of getting the right answer by switching from one hand to the other based on any algorithm is exactly 0.5. In the very first comment, Sarah has suggested that zero is at the center of the number line, and this is true, but so is negative one million and positive one billion. In each case there are as many numbers above and below the chosen point. The number that turns up in the first hand we pick is at the center of the number line, so there is no advantage gained by switching to the other hand, or settling for this choice.

The issue is that in practice, a random number with a uniform distribution in the range negative infinity to positive infinity is not possible. Such a random number generator would be more likely to generate a number with a quadrillion digits – before the decimal point – than a "short number" like 35 in the illustration. It would be even more likely to generate a number with quintillion digits.

So a practical random number always needs to have a finite range, or a non-uniform distribution. And when the numbers come out of such a distribution, knowing one of the numbers gives you information that will help you choose the larger number with a greater than 0.50 probability.

For example, in Pradeep's first bonus example, the numbers are chosen at random, and between zero and ten. Knowing the range and the distribution gives us an advantage. If we saw that the number in the first hand were less than 5.0, say 2.19234.. (more digits beyond), we'd switch to the other hand, and know that we'd have 78.o765.. percent of winning that round. Overall, our chance of winning this game would be well above 50%. The only time we'd be stuck with a mere 50% chance of winning a round was if the number on the first hand came up as exactly 5.0.

So where does the information come from? From knowing that it is not a random distribution with an infinite range.

• Tim P says:

Wonderful counter-intuitive puzzle. Looking forward to next one.

Sarah L. Monty Hall- chance is 2/3 for the switch. Diagrams clearly didn't help 🙂