Randomness

9 Randomness

When to Leave It to Chance

I must admit that after many years of work in this area, the efficacy of randomness for so many algorithmic problems is absolutely mysterious to me. It is efficient, it works; but why and how is absolutely mysterious. —MICHAEL RABIN

Randomness can be a deliberate part of solving a difficult problem. Sampling may give a useful estimate when exhaustive calculation is impractical, and random exploration can reveal solutions a fixed search would miss. In contrast to the standard “deterministic” algorithms we typically imagine computers using, where one step follows from another in exactly the same way every time, a randomized algorithm uses randomly generated numbers to solve a problem. For some problems, randomized algorithms produce good answers faster than the best known deterministic methods. And while they do not always guarantee the optimal solutions, randomized algorithms can get surprisingly close to them in a fraction of the time, just by strategically flipping a few coins while their deterministic cousins sweat it out.

The useful question is when randomness helps, how to use it, and how much uncertainty to accept.

One obstacle is our tendency to see a pattern in every sequence of events. As Leonard Mlodinow observed, “The human mind is built to identify for each event a definite cause and can, therefore, have a hard time accepting the influence of unrelated or random factors.” We see patterns and sequences everywhere, often where none exist. We think the world is out to get us when a few bad things happen in a row, and we construct orderly narratives out of the chaos of history. Paul Graham put it succinctly: “The history of ideas is a history of gradually discarding the assumption that it’s all about us.” Even our access to the past is subject to chance: which documents survive, which a researcher stumbles upon, how they are interpreted—all are shaped by randomness. A random process may have predictable aggregate behavior even when individual outcomes are unpredictable. Accepting that distinction helps us use chance without inventing a story for every result.

Sampling

In 1777, Georges-Louis Leclerc, Comte de Buffon, published the results of an interesting probabilistic analysis. If we drop a needle onto a lined piece of paper, he asked, how likely is it to cross one of the lines? Buffon’s work showed that if the needle is shorter than the gap between the lines, the answer is 2 ⁄ π times the needle’s length divided by the length of the gap. For Buffon, deriving this formula was enough. But in 1812, Pierre-Simon Laplace, one of the heroes of chapter 6, pointed out that this result has another implication: one could estimate the value of π simply by dropping needles onto paper. Laplace’s proposal pointed to a profound general truth: when we want to know something about a complex quantity, we can estimate its value by sampling from it. This is exactly the kind of calculation that his work on Bayes’s Rule helps us to perform. In fact, following Laplace’s suggestion, several people have carried out exactly the experiment he suggested, confirming that it is possible—although not particularly efficient—to estimate the value of π in this hands-on way. (One notorious attempt, by Lazzarini in 1901, claimed an impressively accurate result after 3,408 tosses, but subsequent analysis has made Lazzarini’s report seem suspicious—the numbers were almost too good to be true.) Throwing thousands of needles onto lined paper makes for an interesting pastime (for some), but it took the development of the computer to make sampling into a practical method. Before, when mathematicians and physicists tried using randomness to solve problems, their calculations had to be laboriously worked out by hand, so it was hard to generate enough samples to yield accurate results. Electronic computers made much larger simulations practical, including the work associated with Los Alamos after World War II.

Stanislaw “Stan” Ulam was one of the mathematicians who helped develop the atomic bomb. Having grown up in Poland, he moved to the United States in 1939, and joined the Manhattan Project in 1943. After a brief return to academia he was back at Los Alamos in 1946, working on the design of thermonuclear weapons. But he was also sick—he had contracted encephalitis, and had emergency brain surgery. And as he recovered from his illness he worried about whether he would regain his mathematical abilities. While convalescing, Ulam played a lot of cards, particularly solitaire (a.k.a. Klondike). As any solitaire player knows, some shuffles of the deck produce games that just can’t be won. So as Ulam played, he asked himself a natural question: what is the probability that a shuffled deck will yield a winnable game? In a game like solitaire, reasoning your way through the space of possibilities gets almost instantly overwhelming. Flip over the first card, and there are fifty-two possible games to keep track of; flip over the second, and there are fifty-one possibilities for each first card. That means we’re already up into thousands of possible games before we’ve even begun to play. F. Scott Fitzgerald once wrote that “the test of a first-rate intelligence is the ability to hold two opposing ideas in mind at the same time and still retain the ability to function.” That may be true, but no first-rate intelligence, human or otherwise, can possibly hold the eighty unvigintillion possible shuffled-deck orders in mind and have any hope of functioning.

After trying some elaborate combinatorial calculations of this sort and giving up, Ulam landed on a different approach, beautiful in its simplicity: just play the game.

I noticed that it may be much more practical to [try] … laying down the cards, or experimenting with the process and merely noticing what proportion comes out successfully, rather than to try to compute all the combinatorial possibilities which are an exponentially increasing number so great that, except in very elementary cases, there is no way to estimate it. This is intellectually surprising, and if not exactly humiliating, it gives one a feeling of modesty about the limits of rational or traditional thinking. In a sufficiently complicated problem, actual sampling is better than an examination of all the chains of possibilities.

When he says “better,” note that he doesn’t necessarily mean that sampling will offer you more precise answers than exhaustive analysis: sampling estimates have uncertainty, which generally decreases as the number of independent, representative samples grows. More samples do not fix a biased simulation. For solitaire, the observed win rate also depends on how the games are played; losses do not necessarily establish that a deal was unwinnable. What he means is that sampling is better because it gives you an answer at all, in cases where nothing else will. Ulam’s insight—that sampling can succeed where analysis fails—was also crucial to solving some of the difficult nuclear physics problems that arose at Los Alamos. A nuclear reaction is a branching process, where possibilities multiply just as wildly as they do in cards: one particle splits in two, each of which may go on to strike others, causing them to split in turn, and so on. Exactly calculating the chances of some particular outcome of that process, with many, many particles interacting, is hard to the point of impossibility. But simulating it, with each interaction being like turning over a new card, provides an alternative. Ulam developed the idea further with John von Neumann, and worked with Nicolas Metropolis, another of the physicists from the Manhattan Project, on implementing the method on the Los Alamos computer. Metropolis named this approach—replacing exhaustive probability calculations with sample simulations—the Monte Carlo Method, after the Monte Carlo casino in Monaco, a place equally dependent on the vagaries of chance. The Los Alamos team was able to use it to solve key problems in nuclear physics. Today the Monte Carlo Method is one of the cornerstones of scientific computing.

Biological systems also use variation to explore possibilities. Our immune systems must contend with a vast variety of possible pathogens; to anticipate threats, they generate a varied repertoire of receptors on lymphocytes, partly through random rearrangement, and select among those cells. Ant colonies, too, forage by moving randomly until one ant finds food and leaves a pheromone trail; other ants then encounter the trail at random and reinforce it, collectively coordinating their search without any central control. In both cases, randomness allows a limited set of simple components to explore an enormous space of possibilities when there is little prior knowledge about what will be encountered. These are useful analogies to sampling, rather than literal implementations of the Monte Carlo Method.

Many of these problems, like calculating the interactions of subatomic particles or the chances of winning at solitaire, are themselves intrinsically probabilistic, so solving them through a randomized approach like Monte Carlo makes a fair bit of sense. But perhaps the most surprising realization about the power of randomness is that it can be used in situations where chance seemingly plays no role at all. Even if you want the answer to a question that is strictly yes or no, true or false—no probabilities about it—rolling a few dice may still be part of the solution.

Randomized Algorithms

Michael Rabin helped demonstrate how broadly randomness could be used in computer science. Born in 1931 in Breslau, Germany (which became Wrocław, Poland, at the end of World War II), Rabin was the descendant of a long line of rabbis. His family left Germany for Palestine in 1935, and there he was diverted from the rabbinical path his father had laid down for him by the beauty of mathematics—discovering Alan Turing’s work early in his undergraduate career at the Hebrew University and immigrating to the United States to begin a PhD at Princeton. Rabin would go on to win the Turing Award—the computer science equivalent of a Nobel—for extending theoretical computer science to accommodate “nondeterministic” cases, where a machine isn’t forced to pursue a single option but has multiple paths it might follow.

On sabbatical in 1975, Rabin came to MIT, searching for a new research direction to pursue. He found it in one of the oldest problems of them all: how to identify prime numbers. Algorithms for finding prime numbers date back at least as far as ancient Greece, where mathematicians used a straightforward approach known as the Sieve of Eratosthenes. The Sieve of Eratosthenes works as follows: To find all the primes up to n, write down the numbers from 1 to n, discard the first number because it is not prime, and then cross out all the numbers that are multiples of 2, besides itself (4, 6, 8, 10, 12, and so on). Take the next smallest number that hasn’t been crossed out (in this case, 3), and cross out all multiples of that number (6, 9, 12, 15). Keep going like this, and the numbers that remain at the end are the primes.

For millennia, the study of prime numbers was believed to be, as G. H. Hardy put it, “one of the most obviously useless branches” of mathematics. But it lurched into practicality in the twentieth century, becoming pivotal in cryptography and online security. As it happens, it is much easier to multiply primes together than to factor them back out. With big enough primes—say, a thousand digits—the multiplication can be done in a fraction of a second while the factoring could take literally millions of years; this makes for what is known as a “one-way function.” In RSA, for instance, a key’s public modulus is the product of two large secret primes. Recovering those factors from a suitably chosen modulus is computationally difficult with known classical methods. Other cryptographic systems rely on different mathematical problems. This cryptographic application suddenly made algorithms for finding and checking primes incredibly important. And while the Sieve of Eratosthenes is effective, it is not efficient. If you want to check whether a particular number is prime—known as testing its “primality”—then following the sieve strategy requires trying to divide it by all the primes up to its square root. Trial division of a six-digit number requires checking at most the 168 primes less than 1,000—not so bad. For a twelve-digit number, the upper bound rises to the 78,498 primes less than 1 million, and all that division quickly starts to get out of control. The primes used in modern cryptography are hundreds of digits long; forget about it.

At MIT, Rabin ran into Gary Miller, a recent graduate from the computer science department at Berkeley. In his PhD thesis, Miller had developed an intriguingly promising, much faster algorithm for testing primality—but there was one small problem: it didn’t always work. Miller had found a set of equations (expressed in terms of two numbers, n and x ) that are always true if n is prime, regardless of what values you plug in for x . If they come out false even for a single value of x , then there’s no way n can be prime—in these cases, x is called a “witness” against primality. The problem, though, is false positives: even when n is not prime, the equations will still come out true some of the time. This seemed to leave Miller’s approach hanging. (Miller had shown that if the generalized Riemann hypothesis were true, the minimum number of potential witnesses that would need to be checked is small enough to make the algorithm efficient—but the hypothesis was, and remains, unproven.)

Rabin realized that this was a place where a step outside the usually deterministic world of computer science might be valuable. If the number n is actually nonprime, how many possible values of x would give a false positive and declare it a prime number? The answer, Rabin showed, is no more than one-quarter. For a fixed composite n, at most one-quarter of eligible bases x will let it pass. Each independent, uniformly chosen base therefore reduces the upper bound on the chance that a composite number passes every round by another factor of four. After ten rounds, that bound is one in four to the tenth power—less than one in a million. This is a bound on a composite passing the test, rather than the posterior probability that a number which passed is composite. Still not enough certainty? Check another five times and you’re down to one in a billion.

Vaughan Pratt, another computer scientist at MIT, implemented Rabin’s algorithm and started getting results late one winter night, while Rabin was at home having friends over for a Hanukkah party. Rabin remembers getting a call around midnight: “Michael, this is Vaughan. I’m getting the output from these experiments. Take a pencil and paper and write this down.” And so he had that 2^400 − 593 is prime. Denote the product of all primes p smaller than 300 by k . The numbers k × 338 + 821 and k × 338 + 823 are twin primes. These constituted the largest twin primes known at the time. My hair stood on end. It was incredible. It was just incredible.

The Miller-Rabin primality test, as it’s now known, provides a way to quickly identify even gigantic prime numbers with an arbitrary degree of certainty. Here we might ask a philosophical question—about what the meaning of “is” is. We’re so used to mathematics being a realm of certainty that it’s jarring to think that a number could be “probably prime” or “almost definitely prime.” How certain is certain enough? For example, the worst-case probability that a composite passes forty independent rounds is less than one in a million billion billion. In other words, that’s a decimal that begins with twenty-four zeros—less than one false prime for the number of grains of sand on Earth. This standard comes after a mere forty applications of the Miller-Rabin test. It’s true that you are never fully certain—but you can get awfully close, awfully quick.

Though you may have never heard of the Miller-Rabin test, your laptop, tablet, and phone know it well. Several decades after its discovery, it is still the standard method used to find and check primes in many domains. It has been widely used in generating cryptographic keys, though secure communications do not all depend on this particular test. For decades after Miller and Rabin’s work, it wasn’t known whether there would ever be an efficient algorithm that allows testing primality in deterministic fashion, with absolute certainty. In 2002, one such method did get discovered by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena at the Indian Institute of Technology—but randomized tests such as Miller-Rabin remain attractive because of their practical speed. And for some other problems, randomness still provides the only known route to efficient solutions. One curious example from mathematics is known as “polynomial identity testing.” If you have two polynomial expressions, such as 2x^3 + 13x^2 + 22x + 8 and (2x + 1) × (x + 2) × (x + 4), working out whether those expressions are in fact the same function—by doing all the multiplication, then comparing the results—can be incredibly time-consuming, especially as the number of variables increases. Here again randomness offers a way forward: just generate some random x s and plug them in. If the two expressions are not the same, it would be a big coincidence if they gave the same answer for some randomly generated input. And an even bigger coincidence if they also gave identical answers for a second random input. And a bigger coincidence still if they did it for three random inputs in a row. For general polynomial identity testing, the book describes a gap between efficient randomized methods and known deterministic ones. Error bounds depend on the degree of the polynomials and the range from which inputs are sampled; agreement on a few arbitrary inputs alone is not a guarantee.

The success of randomized algorithms has prompted computer scientists to explore derandomization: the process of systematically removing randomness to see whether deterministic algorithms can achieve the same efficiency. This typically involves finding functions that generate sequences indistinguishable from random yet simple enough to compute quickly. Whether such methods can close the gap for all problems where randomized approaches work well remains an open question, touching on deep issues in complexity theory. For practical use, the choice depends on the available algorithms, their cost, and the error you can tolerate.

In Praise of Sampling

The polynomial identity test shows that sometimes our effort is better spent checking random values—sampling from the two expressions we want to know about—than trying to untangle their inner workings. To some extent this seems reasonably intuitive. Given a pair of nondescript gadgets and asked whether they are two different devices or two copies of the same one, most of us would start pushing random buttons rather than crack open the cases to examine the wiring. And we aren’t particularly surprised when, say, a television drug lord knifes open a few bundles at random to be reasonably certain about the quality of the entire shipment. There are cases, though, where we don’t turn to randomness—and maybe we should.

Arguably the most important political philosopher of the twentieth century was Harvard’s John Rawls, who set for himself the ambitious task of reconciling two seemingly opposite key ideas in his field: liberty and equality. Is a society more “just” when it’s more free, or more equal? And do the two really have to be mutually exclusive? Rawls offered a way of approaching this set of questions that he called the “veil of ignorance.” Imagine, he said, that you were about to be born, but didn’t know as whom: male or female, rich or poor, urban or rural, sick or healthy. And before learning your status, you had to choose what kind of society you’d live in. What would you want? By evaluating various social arrangements from behind the veil of ignorance, argued Rawls, we’d more readily come to a consensus about what an ideal one would look like. What Rawls’s thought experiment does not take into account, however, is the computational cost of making sense of a society from behind such a veil. How could we, in this hypothetical scenario, possibly hope to hold all of the relevant information in our heads? Set aside grand questions of justice and fairness for a moment and try to apply Rawls’s approach merely to, say, a proposed change in health insurance regulations. Take the probability of being born, perhaps, as someone who grows up to become a town clerk in the Midwest; multiply that by the distribution of the different health care plans available to government employees across various midwestern municipalities; multiply that by actuarial data that offer the probability of, for instance, a fractured tibia; multiply that by the average medical bill for the average procedure for a fractured tibia at a midwestern hospital given the distribution of possible insurance plans.… Okay, so would the proposed insurance revision be “good” or “bad” for the nation? We can barely hope to evaluate a single injured shin this way, let alone the lives of hundreds of millions.

Rawls’s philosophical critics have argued at length about how exactly we are supposed to leverage the information obtained from the veil of ignorance. Should we be trying, for instance, to maximize mean happiness, median happiness, total happiness, or something else? Each of these approaches, famously, leaves itself open to pernicious dystopias—such as the civilization of Omelas imagined by writer Ursula K. Le Guin, in which prosperity and harmony abound but a single child is forced to live in abject misery. Rawls proposed principles of justice to guide the choice, rather than leaving it open or treating it simply as expected happiness under a lottery. Sampling offers a separate, practical analogy: it can help us learn how a policy affects people in different circumstances.

MIT’s Scott Aaronson says he’s surprised that computer scientists haven’t yet had more influence on philosophy. Part of the reason, he suspects, is just their “failure to communicate what they can add to philosophy’s conceptual arsenal.” He elaborates: One might think that, once we know something is computable, whether it takes 10 seconds or 20 seconds to compute is obviously the concern of engineers rather than philosophers. But that conclusion would not be so obvious, if the question were one of 10 seconds versus 10^(10^10) seconds! And indeed, in complexity theory, the quantitative gaps we care about are usually so vast that one has to consider them qualitative gaps as well. Think, for example, of the difference between reading a 400-page book and reading every possible such book, or between writing down a thousand-digit number and counting to that number.

Computer science gives us a way to articulate the complexity of evaluating all possible social provisions for something like an injured shin. But fortunately, it also provides tools for dealing with that complexity. And the sampling-based Monte Carlo algorithms are some of the most useful approaches in that toolbox. When we need to make sense of, say, national health care reform—a vast apparatus too complex to be readily understood—our political leaders typically offer us two things: cherry-picked personal anecdotes and aggregate summary statistics. The anecdotes, of course, are rich and vivid, but they’re unrepresentative. Almost any piece of legislation, no matter how enlightened or misguided, will leave someone better off and someone worse off, so carefully selected stories don’t offer any perspective on broader patterns. Aggregate statistics, on the other hand, are the reverse: comprehensive but thin. We might learn, for instance, whether average premiums fell nationwide, but not how that change works out on a more granular level: they might go down for most but, Omelas-style, leave some specific group—undergraduates, or Alaskans, or pregnant women—in dire straits. A statistic can only tell us part of the story, obscuring any underlying heterogeneity. And often we don’t even know which statistic we need. Since neither sweeping statistics nor politicians’ favorite stories can truly guide us through thousands of pages of proposed legislation, a Monte Carlo–informed computer scientist would propose a different approach: sampling. A close examination of random samples can be one of the most effective means of making sense of something too complex to be comprehended directly. When it comes to handling a qualitatively unmanageable problem, something so thorny and complicated that it can’t be digested whole—solitaire or atomic fission, primality testing or public policy—sampling offers one of the simplest, and also the best, ways of cutting through the difficulties.

We can see this approach at work with the charity GiveDirectly, which distributes unconditional cash transfers to people living in extreme poverty in Kenya and Uganda. It has attracted attention for rethinking conventional charity practices on a number of levels: not only in its unusual mission, but in the level of transparency and accountability it brings to its own process. One practice described in the book concerned success stories. “If you regularly check our website, blog, or Facebook page,” writes program assistant Rebecca Lange, “you may have noticed something you don’t often see: stories and photos of our recipients.” The problem isn’t that the glowing stories proffered by other charities aren’t true. Rather, the very fact that they were deliberately chosen to showcase successes makes it unclear how much information can be gleaned from them. So GiveDirectly decided to put a twist on this conventional practice as well. Under the practice described, each Wednesday GiveDirectly selected a recipient at random, sent a field officer to interview them, and published the notes without selecting for a favorable outcome. For instance, here’s their first such interview, with a woman named Mary, who used the money for a tin roof: “She was able to make a better house and that was a tinned house. She was also able to buy a sofa set for her own house. Her life has changed because she used to have a leaking roof soaking up everything in the house whenever it rained. But because of the transfer she was able to make a better tinned house.” “We hope that this gives you confidence in all types of information we share with you,” Lange writes, “and maybe even inspires you to hold other organizations to a higher bar.”

The Three-Part Tradeoff

At once it struck me what quality went to form a Man of Achievement, especially in Literature, and which Shakespeare possessed so enormously—I mean Negative Capability, that is, when a man is capable of being in uncertainties, mysteries, doubts, without any irritable reaching after fact and reason. —JOHN KEATS

There is no such thing as absolute certainty, but there is assurance sufficient for the purposes of human life. —JOHN STUART MILL

Computer science is often a matter of negotiating tradeoffs. In our discussion of sorting in chapter 3, for instance, we noted the tradeoff between time spent up front on sorting versus the time spent later on searching. And in the discussion of caching in chapter 4, we explored the tradeoff of taking up extra space—caches for caches for caches—to save time. Time and space are at the root of the most familiar tradeoffs in computer science, but recent work on randomized algorithms shows that there’s also another variable to consider: certainty. As Harvard’s Michael Mitzenmacher puts it, “What we’re going to do is come up with an answer which saves you in time and space and trades off this third dimension: error probability.”

Asked for his favorite example of this tradeoff into uncertainty, he doesn’t hesitate. “A colleague just said that there should be a drinking game that every time this term appears on one of my slides, you have to take a drink. Have you ever heard of Bloom filters?” To understand a Bloom filter, Mitzenmacher suggests considering a search engine tracking which URLs it has visited. The web is comprised of well over a trillion distinct URLs, and the average URL weighs in at about seventy-seven characters long. When the search engine looks at some URL, how can it check whether that page has already been processed? Just storing a list of all the URLs that have been visited would take a huge amount of space, and repeatedly searching that list (even if it were fully sorted) could prove a nightmare. In fact, it could well be that the cure is worse than the disease: in other words, checking every time to make sure that we’re not reindexing a page might be more time-consuming than just indexing the occasional page twice. But what if we only needed to be mostly sure this URL was new to us? That’s where the Bloom filter comes in. Named for Burton H. Bloom, a Bloom filter uses several hash functions to mark positions in a compact bit array. A clear bit proves that an item has not been inserted; all marked bits mean that it may have been. Clear bits act as “witnesses” to novelty. The primality test can establish that “n is not prime,” while the filter can establish that “I have not seen n before.” A standard Bloom filter can give false positives for membership, but not false negatives when used correctly. If you’re willing to tolerate an error rate of just 1% or 2%, storing your findings in a probabilistic data structure like a Bloom filter will save you significant amounts of both time and space. And the usefulness of such filters is not confined to search engines: Bloom filters have been used in web-browser security checks and in some Bitcoin protocols. Says Mitzenmacher, “The idea of the error tradeoff space—I think the issue is that people don’t associate that with computing. They think computers are supposed to give you the answer. So when you hear in your algorithms class, ‘It’s supposed to give you one answer; it might not be the right answer’—I like to think that when [students] hear that, it focuses them. I think people don’t realize in their own lives how much they do that and accept that.”

Hills, Valleys, and Traps

The river meanders because it can’t think. —RICHARD KENNEY

Randomness has also proven itself to be a powerful weapon for solving discrete optimization problems, like assembling the calendar for NCAA basketball or finding the shortest route for a traveling salesman. In the previous chapter we saw how relaxation can play a big role in cutting such problems down to size, but the tactical use of randomness has emerged as an arguably even more important technique. Imagine you’re putting together a globe-trotting ten-city vacation, your own version of the traveling salesman problem: you’ll start and finish in San Francisco and visit Seattle, Los Angeles, New York, Buenos Aires, London, Amsterdam, Copenhagen, Istanbul, Delhi, and Kyoto. You might not be too worried about the total length of the route, but you probably do want to minimize the monetary cost of the trip. The first thing to note here is that even though ten cities hardly sounds like a lot, the number of possible itineraries is ten factorial: more than three and a half million. Checking every route by hand is impractical, especially when flight prices and schedules must also be compared. You have to work smarter than that.

For your first attempt at an itinerary, you might look at taking the cheapest flight out of San Francisco (let’s say it’s Seattle), then taking the cheapest flight from there to any of the other remaining cities (call it Los Angeles), then the cheapest from there (say, New York), and so forth, until you’re at your tenth city and you fly from there back to San Francisco. This is an example of a so-called greedy algorithm, which you can also think of as a “myopic algorithm”: one that shortsightedly takes the best thing available every step of the way. In scheduling theory, as we saw in chapter 5, a greedy algorithm—for instance, always doing the shortest job available, without looking or planning beyond—can sometimes be all that a problem requires. In this case, for the traveling salesman problem, the solution given by the greedy algorithm probably isn’t terrible, but it’s likely to be far from the best you can do.

Once you’ve assembled a baseline itinerary, you might test some alternatives by making slight perturbations to the city sequence and seeing if that makes an improvement. For instance, if we are going first to Seattle, then to Los Angeles, we can try doing those cities in reverse order: L.A. first, then Seattle. For any given itinerary, we can make eleven such two-city flip-flops; let’s say we try them all and then go with the one that gives us the best savings. From here we’ve got a new itinerary to work with, and we can start permuting that one, again looking for the best local improvement. This is an algorithm known as Hill Climbing—since the search through a space of solutions, some better and some worse, is commonly thought of in terms of a landscape with hills and valleys, where your goal is to reach the highest peak. Eventually you reach a route that cannot be improved by the adjacent swaps you are trying. That says nothing about larger rearrangements. It’s here that the hill climbing stops. Does this mean you’ve definitely found the single best possible itinerary, though? Sadly, no. You may have found only a so-called “local maximum,” not the global maximum of all the possibilities. The hill-climbing landscape is a misty one. You can know that you’re standing on a mountaintop because the ground falls away in all directions—but there might be a higher mountain just across the next valley, hidden behind clouds.

Consider the lobster stuck in the lobster trap: poor beast, he doesn’t realize that exiting the cage means backtracking to the cage’s center, that he needs to go deeper into the cage to make it out. A lobster trap is nothing other than a local maximum made of wire—a local maximum that kills. In the case of vacation planning, local maxima are fortunately less fatal, but they have the same character. Even once we’ve found a solution that can’t be improved by any small tweaks, it’s possible that we are still missing the global maximum. The true best itinerary may require a radical overhaul of the trip: doing entire continents in a different order, for instance, or proceeding westward instead of eastward. We may need to temporarily worsen our solution if we want to continue searching for improvements. And randomness provides a strategy—actually, several strategies—for doing just that.

Out of the Local Maximum

One approach is to augment Hill Climbing with what’s known as “jitter”: if it looks like you’re stuck, mix things up a little. Make a few random small changes (even if they are for the worse), then go back to Hill Climbing; see if you end up at a higher peak. Another approach is to completely scramble our solution when we reach a local maximum, and start Hill Climbing anew from this random new starting point. This algorithm is known, appropriately enough, as “Random-Restart Hill Climbing”—or, more colorfully, as “Shotgun Hill Climbing.” It’s a strategy that proves very effective when there are lots of local maxima in a problem. For example, computer scientists use this approach when trying to decipher codes, since there are lots of ways to begin decrypting a message that look promising at first but end up being dead ends. In decryption, having a text that looks somewhat close to sensible English doesn’t necessarily mean that you’re even on the right track. So sometimes it’s best not to get too attached to an initial direction that shows promise, and simply start over from scratch.

But there’s also a third approach: instead of turning to full-bore randomness when you’re stuck, use a little bit of randomness every time you make a decision. This technique, developed by the same Los Alamos team that came up with the Monte Carlo Method, is called the Metropolis Algorithm. The Metropolis Algorithm is like Hill Climbing, trying out different small-scale tweaks on a solution, but with one important difference: at any given point, it will potentially accept bad tweaks as well as good ones. We can imagine applying this to our vacation planning problem. Again, we try to tweak our proposed solution by jiggling around the positions of different cities. If a randomly generated tweak to our travel route results in an improvement, then we always accept it, and continue tweaking from there. But if the alteration would make things a little worse, there’s still a chance that we go with it anyway (although the worse the alteration is, the smaller the chance). This gives the search a chance to leave a local maximum. Escape can still take a long time, and a better route is not guaranteed within a fixed computing budget.

Whether it’s jitter, random restarts, or being open to occasional worsening, randomness is incredibly useful for avoiding local maxima. Chance is not just a viable way of dealing with tough optimization problems; in many cases, it’s essential. Some questions linger, however. How much randomness should you use? And when? And—given that strategies such as the Metropolis Algorithm can permute our itinerary pretty much ad infinitum—how do you ever know that you’re done? Physics suggested a useful way to control that randomness over time.

Simulated Annealing

In the late 1970s and early ’80s, Scott Kirkpatrick considered himself a physicist, not a computer scientist. In particular, Kirkpatrick was interested in statistical physics, which uses randomness as a way to explain certain natural phenomena—for instance, the physics of annealing, the way that materials change state as they are heated and cooled. Perhaps the most interesting characteristic of annealing is that how quickly or slowly a material is cooled tends to have tremendous impact on its final structure. As Kirkpatrick explains: “Growing a single crystal from a melt [is] done by careful annealing, first melting the substance, then lowering the temperature slowly, and spending a long time at temperatures in the vicinity of the freezing point. If this is not done, and the substance is allowed to get out of equilibrium, the resulting crystal will have many defects, or the substance may form a glass, with no crystalline order.”

Kirkpatrick was then working at IBM, where one of the biggest, trickiest, and most hallowed problems was how to lay out the circuits on the chips that IBM was manufacturing. The problem was ungainly and intractable: there was an enormous range of possible solutions to consider, and some tricky constraints. It was better in general for the components to be close together, for instance—but not too close, or there would be no room for the wires. And any time you moved anything, you’d have to recompute how all the wires would run in the new hypothetical layout. At the time, this process was led by something of a cryptic guru-type figure within IBM. As Kirkpatrick recalls, “The guy who was the best at IBM at squeezing more circuits on a chip … he had the most mysterious way of explaining what he was doing. He didn’t like to really tell you.” Kirkpatrick’s friend and IBM colleague Dan Gelatt was fascinated by the problem, and quickly hooked Kirkpatrick, who had a flash of insight. “The way to study [physical systems] was to warm them up then cool them down, and let the system organize itself. From that background, it seemed like a perfectly natural thing to treat all kinds of optimization problems as if the degrees of freedom that you were trying to organize were little atoms, or spins, or what have you.”

In a simple particle model, “temperature” is related to average kinetic energy from random motion; it is not itself velocity. This was directly analogous, Kirkpatrick reasoned, to the random jitter that can be added to a hill-climbing algorithm to make it sometimes backtrack from better solutions to worse ones. In fact, the Metropolis Algorithm itself had initially been designed to model random behavior in physical systems (in that case, nuclear explosions). So what would happen, Kirkpatrick wondered, if you treated an optimization problem like an annealing problem—if you “heated it up” and then slowly “cooled it off”? Taking the ten-city vacation problem from above, we could start at a “high temperature” by picking our starting itinerary entirely at random, plucking one out of the whole space of possible solutions regardless of price. Then we can start to slowly “cool down” our search by rolling a die whenever we are considering a tweak to the city sequence. Taking a superior variation always makes sense, but we would only take inferior ones when the die shows, say, a 2 or more. After a while, we’d cool it further by only taking a higher-price change if the die shows a 3 or greater—then 4, then 5. Eventually we’d be mostly hill climbing, making the inferior move just occasionally when the die shows a 6. Finally we’d start going only uphill, and stop when we reached the next local max.

This approach, called Simulated Annealing, seemed like an intriguing way to map physics onto problem solving. But would it work? The initial reaction among more traditional optimization researchers was that this whole approach just seemed a little too … metaphorical. “I couldn’t convince math people that this messy stuff with temperatures, all this analogy-based stuff, was real,” says Kirkpatrick, “because mathematicians are trained to really distrust intuition.” At IBM, Kirkpatrick and Gelatt’s simulated annealing algorithms produced layouts that improved on the specialist’s results. Rather than keep mum about their secret weapon and become cryptic guru figures themselves, they published their method in a paper in Science, opening it up to others. Over the following decades, that paper accumulated thirty-two thousand citations in the count reported by the book. Simulated annealing became a widely used optimization technique. Intriguingly, a 2014 study suggests that some jellyfish use a form of simulated annealing when searching for food—wandering more widely (randomly) when they are “hot” with hunger, then slowing their search as they become satiated.

At its core, simulated annealing is a strategy for managing the tension between exploring new possibilities and exploiting the best ones found so far—the exploration-exploitation tradeoff we’ve encountered in other guises. Randomness provides a particularly elegant way to calibrate this balance. There’s a simple algorithm from multi-armed bandit theory, for instance, called Epsilon Greedy: with probability epsilon (a small number) you choose an option at random, and the rest of the time you stick with the best option known. So when you walk into a restaurant, you might occasionally close your eyes and point at the menu, but mostly order your favorite. Unfortunately, this guarantees that you will always spend some proportion of your time exploring, even after the best choice is long obvious, resulting in linearly accumulating regret—not ideal. A smarter variant, which we might call Epsilon-Over-N Greedy, decreases the chance of random exploration over time: the first time you eat out, you choose randomly with probability 1 (always); the second time, probability 1/2; the third, 1/3; and on the Nth visit, you explore with probability 1/N. This schedule reduces random exploration, but a probability of exactly that form does not by itself guarantee logarithmic regret. Such bounds require assumptions about rewards and enough exploration relative to the differences between options.

There is also a more sophisticated Bayesian approach, Thompson Sampling, named after the physician who originally posed the two-armed bandit problem in 1933. Thompson’s idea was to use Bayes’s Rule to compute the probability that each option is the best, and then choose each option with exactly that probability. Early on, when you know nothing, the options are chosen almost equally. As data accumulate, you increasingly favor the apparent winner, but still occasionally take a chance on the underdog—just enough to change your mind if the evidence shifts. Thompson Sampling has logarithmic regret bounds in standard stationary bandit settings under suitable assumptions. For everyday choices, these methods suggest exploring while uncertainty is high and concentrating more on promising options as evidence accumulates. A changing environment may call for renewed exploration.

Randomness, Evolution, and Creativity

In 1943, Salvador Luria didn’t know he was about to make a discovery that would lead to a Nobel Prize; he thought he was going to a dance. A recent immigrant to the United States from Mussolini’s Italy, where his Sephardic Jewish family had lived, Luria was a researcher studying how bacteria developed immunity from viruses. But at this moment his research was far from his mind, as he attended a faculty gathering at a country club near Indiana University. Luria was watching one of his colleagues play a slot machine: “Not a gambler myself, I was teasing him about his inevitable losses, when he suddenly hit the jackpot, about three dollars in dimes, gave me a dirty look, and walked away. Right then I began giving some thought to the actual numerology of slot machines; in doing so it dawned on me that slot machines and bacterial mutations have something to teach each other.”

In the 1940s, it wasn’t known exactly why or how bacterial resistance to viruses (and, for that matter, to antibiotics) came about. Were they reactions within the bacteria to the virus, or were there simply ongoing mutations that occasionally produced resistance by accident? There seemed no way to devise an experiment that would offer a decisive answer one way or the other—that is, until Luria saw that slot machine and something clicked. Luria realized that if he bred several generations of different lineages of bacteria, then exposed the last generation to a virus, one of two radically different things would happen. If resistance was a response to the virus, he’d expect roughly the same amount of resistant bacteria to appear in every one of his bacterial cultures, regardless of their lineage. On the other hand, if resistance emerged from chance mutations, he’d expect to see something a lot more uneven—just like a slot machine’s payouts. That is, bacteria from most lineages would show no resistance at all; some lineages would have a single “grandchild” culture that had mutated to become resistant; and on rare occasions, if the proper mutation had happened several generations up the “family tree,” there would be a jackpot: all the “grandchildren” in the lineage would be resistant. Luria left the dance as soon as he could and set the experiment in motion. After several days of tense, restless waiting, Luria returned to the lab to check on his colonies. Jackpot. Luria’s discovery was about the power of chance: about how random, haphazard mutations can produce viral resistance. But it was also, at least in part, due to the power of chance. He was in the right place at the right time, where seeing the slot machine triggered a new idea.

Tales of discovery often feature a similar moment: Newton’s (possibly apocryphal) apple, Archimedes’ bathtub “Eureka!,” the neglected petri dish that grew Penicillium mold. Indeed, it’s a common enough phenomenon that a word was invented to capture it: in 1754, Horace Walpole coined the term “serendipity,” based on the fairy tale adventures of The Three Princes of Serendip (Serendip being the archaic name of Sri Lanka), who “were always making discoveries, by accidents and sagacity, of things they were not in quest of.”

This double role of randomness—a key part of biology, a key part of discovery—has repeatedly caught the eye of psychologists who want to explain human creativity. An early instance of this idea was offered by William James. In 1880, having recently been appointed assistant professor of psychology at Harvard, and ten years away from publishing his definitive Principles of Psychology, James wrote an article in the Atlantic Monthly called “Great Men, Great Thoughts, and the Environment.” The article opens with his thesis: “A remarkable parallel, which to my knowledge has never been noticed, obtains between the facts of social evolution and the mental growth of the race, on the one hand, and of zoölogical evolution, as expounded by Mr. Darwin, on the other.”

At the time James was writing, the idea of “zoölogical evolution” was still fresh—On the Origin of Species having been published in 1859 and Mr. Darwin himself still alive. James discussed how evolutionary ideas might be applied to different aspects of human society, and toward the end of the article turned to the evolution of ideas: “New conceptions, emotions, and active tendencies which evolve are originally produced in the shape of random images, fancies, accidental out-births of spontaneous variation in the functional activity of the excessively unstable human brain, which the outer environment simply confirms or refutes, adopts or rejects, preserves or destroys—selects, in short, just as it selects morphological and social variations due to molecular accidents of an analogous sort.” James thus viewed randomness as the heart of creativity. And he believed it was magnified in the most creative people. In their presence, he wrote, “we seem suddenly introduced into a seething caldron of ideas, where everything is fizzling and bobbing about in a state of bewildering activity, where partnerships can be joined or loosened in an instant, treadmill routine is unknown, and the unexpected seems the only law.” (Note here the same “annealing” intuition, rooted in metaphors of temperature, where wild permutation equals heat.)

The modern instantiation of James’s theory appears in the work of Donald Campbell, a psychologist who lived a hundred years later. In 1960, Campbell published a paper called “Blind Variation and Selective Retention in Creative Thought as in Other Knowledge Processes.” Like James, he opened with his central thesis: “A blind-variation-and-selective-retention process is fundamental to all inductive achievements, to all genuine increases in knowledge, to all increases in fit of system to environment.” And like James he was inspired by evolution, thinking about creative innovation as the outcome of new ideas being generated randomly and astute human minds retaining the best of those ideas. Campbell supported his argument liberally with quotes from other scientists and mathematicians about the processes behind their own discoveries. The nineteenth-century physicists and philosophers Ernst Mach and Henri Poincaré both seemed to offer an account similar to Campbell’s, with Mach going so far as to declare that “thus are to be explained the statements of Newton, Mozart, Richard Wagner, and others, when they say that thought, melodies, and harmonies had poured in upon them, and that they had simply retained the right ones.”

When it comes to stimulating creativity, a common technique is introducing a random element, such as a word that people have to form associations with. For example, musician Brian Eno and artist Peter Schmidt created a deck of cards known as Oblique Strategies for solving creative problems. Pick a card, any card, and you will get a random new perspective on your project. (And if that sounds like too much work, you can now download an app that will pick a card for you.) Eno’s account of why they developed the cards has clear parallels with the idea of escaping local maxima: “When you’re very in the middle of something, you forget the most obvious things. You come out of the studio and you think ‘why didn’t we remember to do this or that?’ These [cards] really are just ways of throwing you out of the frame, of breaking the context a little bit, so that you’re not a band in a studio focused on one song, but you’re people who are alive and in the world and aware of a lot of other things as well.” Being randomly jittered, thrown out of the frame and focused on a larger scale, provides a way to leave what might be locally good and get back to the pursuit of what might be globally optimal.

And you don’t need to be Brian Eno to add a little random stimulation to your life. Wikipedia, for instance, offers a “Random article” link, and Tom has been using it as his browser’s default homepage for several years, seeing a randomly selected Wikipedia entry each time he opens a new window. While this hasn’t yet resulted in any striking discoveries, he now knows a lot about some obscure topics (such as the kind of knife used by the Chilean armed forces) and he feels that some of these have enriched his life. (For example, he’s learned that there is a word in Portuguese for a “vague and constant desire for something that does not and probably cannot exist,” a problem we still can’t solve with a search engine.) An interesting side effect is that he now also has a better sense not just of what sorts of topics are covered on Wikipedia, but also of what randomness really looks like. For example, pages that feel like they have some connection to him—articles about people or places he knows—show up with what seems like surprising frequency. (In a test, he got “Members of the Western Australian Legislative Council, 1962–1965” after just two reloads, and he grew up in Western Australia.) Knowing that these are actually randomly generated makes it possible to become better calibrated for evaluating other “coincidences” in the rest of his life.

In the physical world, you can randomize your vegetables by joining a Community-Supported Agriculture farm, which will deliver a box of produce to you every week. As we saw earlier, a CSA subscription does potentially pose a scheduling problem, but being sent fruits and vegetables you wouldn’t normally buy is a great way to get knocked out of a local maximum in your recipe rotation. Likewise, book-, wine-, and chocolate-of-the-month clubs are a way to get exposed to intellectual, oenophilic, and gustatory possibilities that you might never have encountered otherwise.

You might worry that making every decision by flipping a coin could lead to trouble, not least with your boss, friends, and family. And it’s true that mainlining randomness into your life is not necessarily a recipe for success. The cult classic 1971 novel The Dice Man by Luke Rhinehart (real name: George Cockcroft) provides a cautionary tale. Its narrator, a man who replaces decision-making with dice rolling, quickly ends up in situations that most of us would probably like to avoid. But perhaps it’s just a case of a little knowledge being a dangerous thing. If the Dice Man had only had a deeper grasp of computer science, he’d have had some guidance. First, Hill Climbing accepts moves that improve the objective being optimized. Second, the Metropolis Algorithm accepts worsening moves less often as their cost increases; the relationship is exponential, rather than simply inverse proportionality. These are search rules, not instructions to act on every appealing idea in life. Third, from Simulated Annealing: you should front-load randomness, rapidly cooling out of a totally random state, using ever less and less randomness as time goes on, lingering longest as you approach freezing. Temper yourself—literally. This last point wasn’t lost on the novel’s author. Cockcroft himself apparently turned, not unlike his protagonist, to “dicing” for a time in his life, living nomadically with his family on a Mediterranean sailboat, in a kind of Brownian slow motion. At some point, however, his annealing schedule cooled off: he settled down comfortably into a local maximum, on a lake in upstate New York. In the account quoted by the book, he was in his eighties and content living there. “Once you got somewhere you were happy,” he told the Guardian, “you’d be stupid to shake it up any further.”

Use randomness for a purpose: choose a representative sample, try a different starting point, or introduce a prompt that breaks a familiar line of thought. Then evaluate what the experiment produces.