Can Information Rise From Randomness?

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

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.

Ready for our first conundrum?

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?

2. 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?

3. 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?

4. 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.