June 4, 2004
Magician-turned-mathematician uncovers bias in coin flipping
By ESTHER LANDHUIS
Persi Diaconis has spent much of his life turning scams inside out. In 1962, the then 17-year-old sought to stymie a Caribbean casino that was allegedly using shaved dice to boost house odds in games of chance. In the mid-1970s, the upstart statistician exposed some key problems in ESP research and debunked a handful of famed psychics. Now a Stanford professor of mathematics and statistics, Diaconis has turned his attention toward simpler phenomena: determining whether coin flipping is random. Could a simple coin toss -- used routinely to decide which team gets the ball, for instance -- actually be rigged?
Diaconis set out to test what he thought was obvious -- that coin tosses, the currency of fair choices, couldn't be biased. "Mathematicians are always doing that," he says. "You know, everybody knows it's true, and then we prove it. So what, right?"
Wrong. Diaconis had good reason to suspect that surprising truths lurk beneath common assumptions. He had uncovered them time after time. For example, people had long supposed that a few shuffles were sufficient to randomize a deck of cards -- until 1992, when Diaconis and Columbia University's David Bayer proved that thorough mixing requires seven shuffles.
A decade later, in 2002, a large manufacturer of card-shuffling machines for casinos summoned Diaconis to determine whether their new automated shufflers truly randomized the deck. (They didn't.) Visiting the company's Las Vegas showroom was a homecoming of sorts for Diaconis. Having left his New York City home at 14 to travel with a sleight-of-hand expert named Dai Vernon, the high-school dropout spent the next decade honing his skills in magic. At a certain crooked Caribbean gambling house, Diaconis tried devising schemes to prevent him and other globetrotting magicians from getting cheated.
Diaconis had no idea this mission would prompt a career shift. To bet strategically, one had to calculate the odds that a die with one-hundredth of an inch shaved off an edge would tumble out of the box on any given side. At a friend's suggestion, he bought himself a copy of William Feller's textbook An Introduction to Probability and Its Applications but couldn't read it because he didn't know calculus. He was 18 at the time.
At 24, Diaconis began taking evening math classes at the City College of New York. He performed magic tricks during the day to pay his way through school. After his first semester of advanced calculus, Diaconis was "very raw," recalls Tony D'Aristotile, who taught the course. "He was nothing special at the time."
But D'Aristotile, now a math professor at the State University of New York-Plattsburgh, saw that the kid had chutzpah. "Barely six to nine months after he struggled with my advanced calculus course, he was applying to the finest graduate schools to continue his study," says D'Aristotile, who has taught probability courses at Stanford the past four summers. "He was shooting for Harvard."
With bare-bones mathematical skills and no high school diploma, 26-year-old Diaconis was a long shot for a spot in Harvard's graduate program in statistics. Fortunately, he had a few aces up his sleeve. Right before leaving home to become a professional magician, Diaconis had managed to get two of his card tricks published on the puzzle page of Scientific American magazine. Martin Gardner, the publication's mathematical games columnist, touted those submissions as two of the 10 best card tricks ever invented. A recommendation letter from Martin Gardner was enough to lure Fred Mosteller Â a statistician on the selection committee who had dabbled with magic Â into taking Diaconis as one of his graduate students. "Magic and Fred Mosteller got me into Harvard," Diaconis says. Three years later, in 1974, he completed his doctorate and joined the Stanford statistics faculty.
Teaming up with colleague Joseph Keller, now a professor emeritus of mathematics, Diaconis resurrected the shaved dice problem. But this time around, he had the mathematical acumen to realize it was nearly impossible to solve. "You can't really do the physics of a bouncing, rolling solid on a rough surface," he says. "It's just too complicated."
So Diaconis and Keller did what mathematicians typically do when faced with such travails: They made assumptions and approximations and devised theoretical models. The two came up with very different models that, amazingly enough, gave the same answer to three decimal places.
But Diaconis wasn't satisfied. Determined to know whether their models fit real data, the young professor approached a company specializing in gambling products and ordered a set of carefully made shaved dice. He enlisted his graduate students to perform 1,000 rolls of 10 dice -- 10,000 rolls in total -- on a craps table constructed in the Statistics Department library for this purpose. The problem was, human counting error swamped whatever minuscule effects came from the hundredth of an inch shaved off the dice. Furthermore, distinguishing the two models would have required at least a million rolls.
Of flipping coins and falling cats
It wasn't long before the unmanageable analysis of a bouncing, rolling die morphed into a somewhat easier one -- the study of a flipped coin. Diaconis started by showing that the outcome of a coin toss depends not on chance but physics.
"If you hit a coin with the same force in the same place, it always does the same thing," he says.
To make his point, Diaconis commissioned a team of Harvard technicians to build a mechanical coin tosser -- a 3-pound, 15-inch-wide contraption that, when bolted to a table, launches a coin into the air such that it lands the same way every single time. Diaconis himself has trained his thumb to flip a coin and make it come up heads 10 out of 10 times. But what he really wanted to know was whether unrehearsed tosses -- by ordinary folk who flip coins with unpredictable speeds and heights and catch them at different angles -- would show that the outcome of the act was, in fact, random.
To analyze the motion of a tossed coin, Diaconis solicited help from Richard Montgomery, a math professor at the University of California-Santa Cruz. Montgomery had developed the Falling Cat Theorem -- a theory that explains how a cat dropped from any angle always manages to land on its feet. Surely this expertise in angular momentum could also apply to falling coins, Diaconis thought. Staring at a picture of tumbling felines on Montgomery's office wall a few years ago, he blurted, "You're the man for me."
A collaboration was born. Diaconis and Montgomery started meeting once a week, at Stanford or UC-Santa Cruz, to discuss their ideas. In about eight months, they arrived at a startling prediction: A flipped coin is biased to land on the same side it starts out on.
But their pencil-and-paper model couldn't predict the size of the bias. And if the bias turned out so small that it would take, say, 10 million tosses to detect a heads advantage, the pages of yellow pad calculations would prove, for all practical purposes, meaningless. Determining the size of the bias would require watching real people flip real coins. To model a flipped coin with quantitative precision, they needed to analyze its spinning, spiraling motion at multiple, consecutive points along its trajectory. This task called for a camera capable of capturing, in many frames, a split-second event.
Diaconis first approached statistics Associate Professor Susan Holmes, who is also his wife, and asked if he could try her computer's camera. The resolution was too low. Diaconis and Holmes went out and bought a slow-motion camera. Still too low. They tried physics Professor Aharon Kapitulnik's slow-motion camera. Not good enough.
'Social mathematician' -- no oxymoron here
Diaconis has no qualms about discussing his work, tribulations and all, with others. (He jokes that you can always spot extroverted mathematicians -- they're the ones who look at your feet.) "I'm a very social mathematician," he says. "What that means is, when I'm stuck on a problem, I feel free to call somebody who's an expert and try to talk them into helping."
While he and Holmes were analyzing the coin toss images, for instance, coffee-shop conversations with physics professors Kapitulnik and Stephen Shenker spurred them to consider the effects of air resistance, an important factor they had neglected in previous analyses.
In a similarly casual manner, as a visiting professor at Cornell University from 1996 to 1998, Diaconis sparked collaborations between department members who hadn't talked with each other for years. Holmes calls him a "social enabler," a role she attributes to his background in magic. "He was already used to sitting around in coffee shops and bars, exchanging ideas with these old magicians," she says. "He just transported that idea to mathematics. Why can't we sit around in a coffee shop and talk mathematics?"
Diaconis is also a matchmaker, bridging different academic fields. For more than five years, he and chemistry Professor Hans Andersen have met weekly to chat about their research over lunch. Several months ago, Diaconis recognized that Andersen's work in the statistical mechanics of fluids sounded similar to a mathematical theory being developed by of one of his colleagues, mathematics Professor Horng-Tzer Yau, who came to Stanford last fall. "I'd talked to both of them, often without so much understanding," Diaconis says. "But it sounded to me as if they were talking about the same thing."
In March he brought Andersen and Yau together for lunch. Sure enough, chatting face-to-face about their research for the first time, the two discovered they were working on overlapping problems. But mathematicians and chemists use different terms to describe the same concept, which makes cross-disciplinary conversations difficult. "Persi was the link here," Andersen says. "He's willing to spend the time to learn the language of other disciplines."
Mathematics doctoral student Joe Blitzstein agrees, noting that the most important thing he's learned from Diaconis, his thesis adviser, is "how to recognize that one problem is really the same as another, in a different guise."
Though Diaconis had made a key conceptual leap by connecting falling cats and flipped coins, he still hadn't found a camera that could adequately capture the complex motion of a split-second coin toss. Without these images, it would be impossible to derive the quantitative model needed to calculate the size of a coin flip's predicted bias. Desperate, the social mathematician sought help from psychology and electrical engineering Professor Brian Wandell. Over a latte at Bytes CafÃ© in the Packard Electrical Engineering Building a year ago, Diaconis asked Wandell, an expert in human vision and color perception, if he knew anything about slow-motion photography. He couldn't have picked a better person. Two years earlier, a team led by Wandell and electrical engineering Professor Abbas El Gamal had built a speedy digital camera that shoots 10,000 frames per second Â 400 times faster than a typical camcorder.
Diaconis next coaxed Ali Ercan, an electrical engineering doctoral student in El Gamal's lab, into helping collect the data. For each coin flip, they wanted at least 10 consecutive frames -- good, crisp images of the coin's position in the air. From these sequences they would derive the angular momentum vectors they needed to describe, in quantitative terms, the coin's complicated motion.
Thanks to Ercan's efforts, Diaconis had video footage of 25 coin flips ready for analysis. The problem was, neither he nor his collaborator Montgomery knew how to extract meaningful numbers from that sprawling mess of two-dimensional computer images. Diaconis didn't even own a computer. (He still doesn't. He says he got sick of adjusting to new operating systems and noted, after not using computers for several years, that "nothing bad happened to me. And I said, 'Well, I could either learn the current system or learn differential geometry. I think I'll learn differential geometry this year.'")
In situations like these, the academic partnership forged by Diaconis and Holmes' marriage becomes instrumental. Initially, Holmes had no plans to get involved in the coin-tossing project. She prefers applying her statistics knowledge to biological problems with "big, messy data sets." However, realizing her computing skills could help her husband through a bottleneck in his analysis, she "plunged into it like a warrior," Diaconis says. After a week spent combing through textbooks, downloading computer programs and e-mailing world experts on image analysis, Holmes figured out how to derive from the video clips the coveted angular momentum vectors. Once again, the coin-tossing study had been salvaged.
Preliminary analysis of the video-taped tosses suggests that a coin will land the same way it started about 51 percent of the time. "It's a gem-like example of what we know that isn't so," Diaconis says. Though a skeptic since childhood, he believed that "if you flipped a coin vigorously, it was going to be fair.
"But it's not so bad," he says. "One in a hundred is pretty close, actually. It gives me faith that probability assumptions can be validated and useful, but you have to look at them case by case."
Esther Landhuis is a former News Service intern.
This release was written by science writer Esther Landhuis, a former News Service intern. Photos of Diaconis are available at http://newsphotos.stanford.edu