Randomness, often seen as the opposite of order, was the focus of a recent lecture at Stony Brook University delivered by Avi Wigderson, the 2021 Abel Prize laureate and Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study in Princeton. The event took place on November 12 at the Della Pietra Family Auditorium in the Simons Center for Geometry and Physics as part of the Simons Center’s Della Pietra Lecture Series.
In his talk titled "Randomness," Wigderson explained how unpredictability has influenced areas such as computer science, physics, mathematics, game theory, and cryptography. He emphasized that randomness is not just a feature of nature but also a fundamental tool for understanding it.
“Randomness has fascinated humanity for millennia,” Wigderson said. “It’s been used to settle disputes, in gambling, in statistics, in science. The question is not only whether the universe is inherently deterministic or probabilistic, but whether we can tell the difference.”
Using examples like coin tosses and digital algorithms, Wigderson illustrated how perfect randomness means every possible outcome has an equal chance—regardless of patterns that may appear more random to human observers. He noted that while people often see mixed sequences as more likely than long streaks when flipping coins repeatedly, mathematically all specific sequences have equal probability.
He also discussed how randomization has become essential to modern computation. Randomized algorithms allow computers to perform calculations quickly where exact methods would be impractical or impossible due to time constraints. For example, he described estimating molecular arrangements—a process that would take longer than the age of the universe using deterministic methods—as achievable through random sampling techniques.
Wigderson addressed sources and limitations of randomness: “Where do random bits come from? Some companies literally sell randomness, harvested from atmospheric noise or radioactive decay. But is that really random, and does it matter if it isn’t perfect?”
He introduced pseudorandomness—deterministic processes designed to appear truly random even under scrutiny by advanced computers—and highlighted its importance for fields like cryptography and data security. “Randomness,” he said, “is in the eye of the beholder. What looks unpredictable to one observer might be predictable to another with more computational power. That means randomness isn’t an absolute property of nature — it’s relative to our ability to compute.”
To demonstrate this point further: “The experiment doesn’t change,” he said about coin tossing with advanced prediction tools available; “but the observer does. What’s random to us is deterministic to someone with greater computational resources.”
Wigderson outlined how research into pseudorandomness has led to progress in error-correcting codes and mathematical discovery and described connections between efficiency and probability within computing theory: “Every efficient randomized algorithm can, in theory, be simulated deterministically if just one sufficiently hard problem exists.” This relationship underscores deep links between randomness and computation.
“When we talk about pseudorandomness,” he said,“we’re really talking about creating order that looks like chaos. It’s one of the few areas where mathematics allows us to imitate nature.”
He concluded by stressing that randomness aids understanding rather than hindering it: “Randomness lets us explore, approximate, and predict in ways that deterministic thinking alone cannot… Even in a world that may be deterministic at its core, the appearance of chance gives us new ways to make sense of it.”
For those interested in learning more about these concepts,Wigderson recommended his book "Mathematics and Computation: A Theory Revolutionizing Technology and Science," which provides an introduction accessible free online.