The Counterintuitive Power of Randomness

By Jordana Cepelewicz

Each week Quanta Magazine explains one of the most important ideas driving modern research. This week, senior math writer Jordana Cepelewicz unpacks how randomness has become one of mathematicians’ most powerful tools.

Sometimes an idea’s time arrives. In the late 1940s, the idea that randomness can be a powerful tool arrived in New Jersey. Claude Shannon, an electrical engineer at the Bell Telephone Laboratories in Murray Hill, used random codes to show that it is possible to transmit information over arbitrarily noisy channels. Independently, Paul Erd?s, a Hungarian mathematician working at the Institute for Advanced Study, some 30 miles to the southwest, used arguments depending on randomness to prove a seminal result in graph theory. Mathematical graphs are collections of points with lines connecting some of them. Erd?s showed that in small enough graphs, it’s possible to avoid creating groups of points, called cliques, that are all connected or all disconnected.

In physics, the role of randomness had undergone a profound change during the previous generation, as the discovery of quantum mechanics indicated that the universe is inherently random. But while physicists saw randomness as a challenge to be overcome, mathematicians and engineers figured out how to put it to use. As Rahul Santhanam of the University of Oxford explained , there’s something paradoxical about the way randomness helps mathematicians solve problems.

They often use it to prove that a given mathematical structure exists without specifying how to build it. For example, Erd?s’ proof of the existence of clique-less graphs didn’t specify how to make them. Instead, he showed that if you consider the set of all possible graphs of a given size, and choose one at random, the chance that you’ll find a graph without a “forbidden” clique is greater than zero. Which means that such a graph must exist.

Shannon’s result was the beginning of a discipline called information theory , which explores how much information can theoretically be transmitted in particular circumstances — though it does not necessarily spell out the best way to do so. Like Erd?s, Shannon didn’t specify how to create a scheme for reliable transmission over a noisy channel. But, using randomness, he proved that such a way must exist.

Since then, mathematicians have used randomness as a tool not just in graph theory and information theory, but also in geometry, analysis (an advanced form of calculus), combinatorics (the study of counting methods) and computer science. Earlier this year, Avi Wigderson of the Institute for Advanced Study won a Turing award , one of the top honors in computer science, in part for his work studying connections between randomness and computation.

In recent years, mathematicians have been probing the limits of probabilistic methods and gaining intuition for where they might fail. “It’s very, very natural to try to use randomness to try to push things through,” one mathematician told me. However, “randomness only gets you so far.”

What’s New and Noteworthy

Still, it gets you very, very far. Researchers have continued to follow in Erd?s’ footsteps, using randomness to prove many results in an area called Ramsey theory, which studies the unavoidable formation of cliques in graphs. In 2020, for instance, two mathematicians improved the lower bound on numbers that quantify how big a graph must get before certain patterns become inevitable. The following year, Quanta reported on a proof that marked major progress toward resolving one of the oldest problems in Ramsey theory, a question about how long disordered strings can be. And last year, I wrote about yet another Ramsey result where randomness was crucial.

Probabilistic methods have also made it possible to prove the existence of other kinds of structures. In 2017, mathematicians heaped one random process on top of another , only to find that consistent geometric patterns arise amid all that disorder. “The disorder converges to a universal form,” wrote Kevin Hartnett. “At the precise moment when a random system seems most chaotic, exquisite geometric order peers through.” Last year, I wrote about how mathematicians used a probabilistic method to prove that there are infinitely many configurations known as subspace designs — objects related to error-correcting codes — “whose existence is not at all obvious,” as one mathematician told me.

In all this work, mathematicians have to be clever about how they employ randomness. In 2022, for instance, I covered a groundbreaking proof of the Kahn-Kalai conjecture, a major problem that asked when phase transitions occur in graphs and other systems. Two mathematicians gave the answer by randomly selecting pieces of graphs and sets until they gradually built up the structures they needed, rather than applying randomness in one fell swoop.

Randomness seems like the very antithesis of everything math purports to be — the steadfast pursuit of logic, the search for patterns and structure, the crafting of neat and airtight arguments. And yet it’s become one of the subject’s most useful instruments.

Around the Web

• Noga Alon and Joel Spencer wrote a book, The Probabilistic Method , on the development and use of randomness as a tool in combinatorics. It’s a standard reference in the field.
• Slate has a 2022 book excerpt on what it means to be truly random, and how to generate randomness with machines.
• The YouTube channel Numberphile has a 2014 video that introduces basic problems in Ramsey theory.