JANUARY 2005
Last doubts removed about the proof of the Four Color Theorem
At a scientific meeting in France last December, Dr. Georges Gonthier, a mathematician who works at Microsoft Research in Cambridge, England, described how he had used a new computer technology called a mathematical assistant to verify a proof of the famous Four Color Theorem, hopefully putting to rest any doubts about the result that had remained since the first proof of the theorem was announced in 1976.
The story of the Four Color Problem begins in October 1852, when Francis Guthrie, a young mathematics graduate from University College London, was coloring in a map showing the counties of England. As he did so it occurred to him that the maximum number of colors required to color any map seemed likely to be four. The coloring has to meet the obvious requirement that no two regions (countries, counties, or whatever) sharing a length of common boundary should be given the same color.
Guthrie’s question became known as the Four Color Problem, and it grew to be the second most famous unsolved problem in mathematics after Fermat’s last theorem.
In 1976, two mathematicians at the University of Illinois, Kenneth Appel and Wolfgang Haken, announced that they had solved the problem. But there was a twist. Much of their proof was carried out on a computer, and was far too long for humans to check. Although many mathematicians were initially unhappy that much of the proof was a brute force computation that could not be examined by hand, most accepted the result. But some were less sure. What if the computer program had a hidden flaw that meant it did not behave in exactly the way its developers said it did?
Mathematicians grew more confident in the result when, in 1994, another team produced a different computer proof. Still, there always remained some doubts. With Gonthier’s work, which uses a mathematical assistant to check the 1994 proof, those doubts should finally be put to rest.
What makes the new result particularly significant from a reliability point of view is that the proof assistant Gonthiers employed, called Coq, is a widely-used general purpose utility, which can be verified experimentally, unlike the special-purpose programs used in the earlier proofs of the Four Color Theorem. Coq was developed by the French research center INRIA, where Gonthiers was formerly employed, and where much of his work on the Four Color Theorem was done.
Getting one computer to check the work of another in this way amounts to fighting fire with fire. A mathematical assistant is a new kind of computer program that a human mathematician uses in an interactive fashion, with the human providing ideas and proof steps and the computer carrying out the computations and verification. Such systems have been under development over the last thirty years. Other applications include checking the correctness of computer hardware and software.
The Four Color Problem
What makes the four color problem so hard is that it refers to all maps—not just all the maps in all the atlases around the world, but all conceivable maps, maps with millions (and more) of countries of all shapes and sizes. Knowing that you can color some particular map using four colors does not help you at all. You need to produce an argument that will work in all cases.
Since the sizes and shapes of the map regions do not matter, only the way they join together, the Four Color Problem is a question in topology. As we shall see momentarily, it is easily reformulated as a problem about networks (or graphs in the sense that term is used in discrete mathematics), and in fact the network formulation is the one used in most attempts at a solution by professionals, including the eventual successful ones.
After being posed by Guthrie, the four color problem floated around London for over twenty years, being regarded more as a curious brainteaser than a major problem of mathematics. But then, on 13 June 1878, the English mathematician Arthur Cayley asked the assembled members of the London Mathematical Society if they knew of a proof of the conjecture. With this act the real hunt was about to begin.
A year later, one of the members of the London Mathematical Society, a barrister called Alfred Bray Kempe, published a paper in which he claimed to prove the conjecture. But he was mistaken, and eleven years later Percy John Heawood pointed out a significant error in the argument. Heawood was however able to salvage enough to prove that you can color any map with five colors.
Over the years, many professional mathematicians, and an even greater number of Sunday afternoon amateurs, tried to solve the problem, but without success. Like Fermat’s last theorem, there are some “obvious” ways to solve the problem that seem, on the face of it, to work, but have subtle errors, and professional mathematicians grew used to receiving claimed proofs from amateurs who would often remain convinced their solution was correct even after the error was pointed out to them.
Here is how to reformulate the Four Color Problem as a question about networks. Within each region of the given map, you place a single point, known as a node of the network. (You can think of these points as the capital cities of the countries, if you wish.) You then join up the nodes to form a network, in much the same way that you might link cities by a rail network. The rule is that two nodes are joined together if, and only if, their respective map regions share a common boundary, in which case the line joining them has to lie entirely within the two regions, crossing over the common boundary. (In terms of a rail link this would mean that the line cannot cross the territory of any third country.) The network this gives shows at a glance the topological structure of the map it represents. Indeed, the problem of coloring the map (in the sense of Guthrie’s problem) can be reformulated in terms of coloring the network: color the nodes of the network in such a way that any two nodes which are connected together must have different colors. If all networks can be so colored using four colors, so can all maps, and vice versa.
To prove the (network version of the) Four Color Theorem, you start out by assuming that there is a network that cannot be colored with four colors, and work to deduce a contradiction. If there is such a network, there will be (at least) one that has the fewest number of nodes. That’s the one to look at. The idea then is to show that you can find a particular node that can be removed without altering the number of colors needed to color the network. Since that new network has one fewer nodes than the one you started with, and that initial network was chosen to be the smallest that could not be colored with four colors, the new network can be colored with four colors. But then, because of the way you chose the node to remove, that means the original map can be colored with four colors. And there’s the contradiction.
So the crux of the proof is to describe the individual processes which are used to reduce a given network to one with fewer nodes without reducing the number of colors necessary to color the network, and to show that any minimal counterexample to the Four Color Conjecture must of necessity contain at least one node that can be so removed. This is the part that turned out to require computer help. Appel and Haken had to identify and examine around 1500 different ways that a node could be appropriately removed and show that any minimal counterexample network must contain at least one node of one of those 1500 kinds.
Appel and Haken started their computer-assisted investigation in 1972 and four years later they had their answer. It took 1200 hours of computer time, during which the computer had to carry out billions of calculations. The two mathematicians themselves had to analyze by hand some 10,000 portions of networks.
With the Appel-Haken result, something had happened that mathematicians had wondered about since computers had first appeared in the 1950s: machines had finally taken over some of the task of proving theorems. With the recent work of Gonthier, it seems that computers have also become indispensable for checking their own proofs! Mathematics will never be the same again.
A final thought to leave you with as we start a new year. To this day it is not known if there can be a short proof of the Four Color Theorem that a human could follow. Most mathematicians think there is not. But who knows?
References
For a brief account of the Appel and Haken proof, and much of the work that led up to it, see Chapter 7 of my own book Mathematics: The New Golden Age, published by Columbia University Press in 2001. For a comprehensive account of the entire history of the Four Color Problem, see Robin Wilson’s book Four Colors Suffice : How the Map Problem Was Solved, published by Princeton University Press in 2003. You can also listen to a brief radio discussion on the new result between Keith Devlin and host Jacki Lyden on NPR’s popular magazine program Weekend Edition, by clicking here.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs), will be published in April by Thunder’s Mouth Press.
FEBRUARY 2005
NUMB3RS gets the math right
If you’ve read the January 21 issue of Math Games by my fellow MAA Online columnist Ed Pegg Jr., you will have some general background on the new CBS prime-time television series NUMB3RS. (Ed also includes some cool photos from the show.) Normally, columnists try to avoid covering the same story, especially within a couple of weeks of one another, but the launching of a major television series in which the hero is a mathematician is such an unusual event that it surely merits a second look.
For one thing, successful movies or television series have in the past led to a significant upsurge in the numbers of students who opt for various majors at university. Perhaps the most cited instance of this is the large number of AI practitioners who were first inspired to enter the field by the 1968 movie 2001. And I’m told that criminal forensics got a huge boost as a potential career as a result of the TV series CSI.
More generally, surely almost anything that can improve the image of mathematics in the population at large deserves the support of the mathematics community.
The widespread ignorance among the general public of what mathematics is all about is testified by the fact that one of the criticisms of the new series after the first episode was screened on January 23 was that it defied credulity. Many TV critics, it seems, could not believe that mathematics could be used to help solve criminal cases in the way depicted in the program. Yet that first episode, like all the other upcoming episodes in the first season, is based on a real-life case. Not just loosely based on it, but closely so.
[It’s amusing to note that “NUMB3RS doesn’t add up” was the most common comment among the several dozen newspaper reviews I looked at, an oh-so-obvious choice of phrase that was ironic given that one of the critics’ main complaints was that the series lacked originality and adopted a tired and over-used formula!]
I got the inside scoop on the new series shortly before it first aired, when I met with the series’ co-creators, co-producers, and co-writers Nick Falacci and Cheryl Heuton. Their starting point, they told me, was to develop a prime-time television series that featured mathematicians and scientists. At the back of their mind was the late Richard Feynman, the famous physicist at their local university: Caltech. But getting a major studio to commit to a new idea, especially one involving math, was, they discovered, no easy matter. Their solution—which was clearly very successful in terms of getting superstar movie and TV producers Ridley and Tony Scott (whose movie credits include Alien and Top Gun, respectively) to produce the series and CBS to buy it—was to fit their idea into a tried and tested formula: the police procedural detective series.
And so, eventually, NUMB3RS was conceived, a variant of the hugely popular CSI series, with the forensic scientists of CSI replaced by mathematics genius Charlie Eppes, who gets involved in cracking criminal cases through his elder brother Don, an FBI agent.
For the pilot episode, Falacci and Heuton chose a serial rape case that arose in Louisiana in the late 1990s. In that real-life case, a Canadian police detective with a Ph.D. in mathematics read about the case and wrote to the local police to offer his services. He had, he said, developed a formula to determine the likely residence location of the perpetrator, based on the pattern of locations of the crimes.
By then, the local police were willing to try anything, and so they brought the Canadian detective onto the case. What happened next will be familiar to you if you watched the first episode of NUMB3RS. The police scoured the likely residence location determined by the mathematics formula, collecting DNA samples from cigarette butts and other castaway items of all males in the area, and had those samples tested against those from the rape victims.
In the event, none of the samples collected matched, until someone wondered if the perpetrator had recently moved. (Yes, even that part of NUMB3RS was taken right from the real-life case! Why make things up when real life has all the dramatic elements you need.) Thanks to the mathematics, the (real-life) criminal—a police detective as it turned out—was caught.
The mathematical formula you see actor David Krumholtz (who plays the mathematician) write on the blackboard in his home is in fact the equation used in the real case. The other equations you see (and will see) in the series, including the water sprinkler example near the start of episode 1, were written by the series’ principal mathematics advisor, Gary Lordon, the head of mathematics at Caltech, by mathematics graduate students at Caltech, and by other professional mathematicians, a great many of whom the series producers have contacted to ask for help. (They sent a representative to the Joint Mathematics Meetings in Atlanta last month, to extend their network of contacts in the profession.) So much for all those TV critics who thought the plot was too implausible!
The second episode, which was broadcast on January 28, is based on a real life series of bank robberies in Maryland last year. In that case, a mathematician in Arkansas provided the pattern analysis that resulted in the police lying in wait at the bank when the gang struck.
Will the new series be a success? No one knows, not even the heads at CBS who commissioned it. Twenty-five million people watched the first episode, by far the largest of any new TV series this season (Desperate Housewives had garnered 21.6 million), no doubt helped in large part by being screened right after the NFL Super Bowl playoff game between the New England Patriots and the Pittsburgh Steelers. But even without the football, the 17 million viewers who tuned in to the second episode the following Friday night made that the most watched program of the evening.
If the series does go down the tubes after a few episodes, it won’t be because the math is wrong. The producers have gone to great lengths to get the math right. (They also have a real-life FBI agent on the set to make sure the police stuff is correct as well.) Nor is Krumholz’s portrayal of the math genius off the mark. Okay, he’s cuter than most of us, but looks apart, his character seems to me like an amalgam of a half dozen mathematicians I have met. (In preparing for the role, Krumholz hung around Caltech for a while, seeing what real mathematicians are like.) Sure, the writers and the actors employ dramatic license in their portrayal of mathematicians and what is involved in doing mathematics. This is, after all, a prime-time television crime series, not a mathematics lecture or a documentary about mathematicians—neither of which could come close to drawing a television audience of 25 million, even if they followed the Super Bowl final itself. But at heart they get the mathematician and the math right.
Failure of the show is also unlikely to result from viewers being put off by the math. When CBS tested an early version of the pilot, the sample audience was not only intrigued by the math, they said they wanted more of it in the show! Similar highly positive responses to the dramatic portrayal of mathematicians and mathematics followed both of the stage plays Breaking the Code and Proof and each of the movies Good Will Hunting, Pi, and A Beautiful Mind.
For my part, I hope the show is a success. True, I watched the first episode and am following the series purely because of the mathematics angle. I confess that I rarely watch TV, and have never seen a single episode of CSI. (Not because I have anything against TV. I just never seem to have the time to switch it on! Maybe I spend too much time writing MAA columns.) But if NUMB3RS does make it, it could do wonders for the general perception of mathematics among the general public, and perhaps stimulate more young people to go into the field.
And maybe one day, TV critics and others will not be surprised and incredulous when they learn that math is used in different ways in many walks of life.
NOTE: You can listen to a brief radio discussion on NUMB3RS between Keith Devlin and host Scott Simon on NPR’s popular magazine program Weekend Edition, by clicking here.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs), will be published in April by Thunder’s Mouth Press.
MARCH 2005
Mathematics: a natural pursuit
WARNING: This talk makes reference to evolution. Evolution is a theory, not a fact, regarding the origin of living things. The material should be approached with an open mind, studied carefully and critically considered. So there.
I’ve known people who refuse to eat meat because we kill animals to obtain it, who nevertheless are happy to eat seafood. And high on the list, for some of them, is a delicious Maine lobster. After all, just look at it. Can you imagine anything more primitive, anything less likely to have a conscious sense of its own existence? Well, next time you sit down for a lobster dinner, ponder this: You will be tucking in to one of nature’s most accomplished navigators. For the fact is, the common lobster has a geographical location system that humans can match only with the latest, most sophisticated version of GPS, the hugely expensive navigation system that depends upon satellites that orbit the earth, the most accurate timekeeping devices ever devised, masses of computer power, and a pile of advanced mathematics.
What humans accomplish with mathematics and technology, the lobster achieves by being able to “see” the Earth’s magnetic field. Not merely in the sense of detecting the magnetic poles. The lobster’s system is much more sophisticated than that. The Earth’s magnetic field varies from one place to another, in direction, angle to the Earth, and intensity. The lobster appears to be able to use this variation to determine exactly where it is. This was discovered only a few years ago, by ocean scientist Ken Lohmann of the University of North Carolina and his Ph.D. student Larry Boles.
It took Bolas six years of study of the Caribbean spiny lobster in the waters near the Florida Keys before he was convinced that they had this amazing ability. To demonstrate the fact, he tried all kinds of ruses to confuse them. He removed them from the ocean and put them in a lightproof plastic container, drove them around in circles in his boat, took them ashore and drove them around in the back of his pickup truck, placed them next to powerful magnets to distort the Earth’s magnetic field, and then dropped them back in the ocean in a new location. As soon as they were released the lobsters headed off directly towards their home. They did so even when Bolas placed rubber caps over their eyes, so they were not navigating by light. But to be doubly sure, Bolas put some lobsters into a marine tank in his lab and subjected them to an artificial magnetic field that mimicked that of the Earth. The lobsters headed off in exactly the direction they would have had to follow to get home if the field had been the Earth’s natural one.
The researchers suspect that the lobster’s navigational ability may make use of small particles of magnetite, an iron oxide, located in two masses of nerve tissue toward the front of the creature’s body. But whatever the mechanism, now you know that lobsters are born with some pretty sophisticated built-in navigational abilities, do you still fancy that lobster dinner?
The built-in GPS system of the lobster is just one of many built-in, natural mathematical capacities you come across in the natural world, that I describe in my latest book The Math Instinct (Thunder’s Mouth Press, April 2005), from which this month’s column is taken.
Birds provide another example of remarkable navigational ability that I take a close look at in the book. Every year, millions of birds migrate thousands of miles to and from their winter home. How do they know which direction to fly? There are several possibilities, but most of them seem to require mathematical computations that most humans would find challenging. How do the birds do it?
To put the question another way, why is it that a pilot of a Boeing 747 needs a small battery of maps, computers, radar, radio beacons, and navigation signals from GPS satellites—all heavily dependent on masses of sophisticated mathematics—to do what a small bird can do with seeming ease, namely, fly from point A to point B?
To give you some idea of the distances that can be involved, the Arctic Tern flies an annual round trip that can be as long as 22,000 miles, from the Arctic to the Antarctic and back. On the trip south, they make a regular stopover on the Bay of Fundy, fly a grueling, three-day nonstop leg across the featureless north Atlantic, and make their way along the entire west coast of Africa. They return by a different route, coming up the east coast of south and north America. Other sea birds also make amazingly long trips: the Long-tailed Jaeger flies 5,000 to 9,000 miles in each direction, the Sandhill and Whooping Cranes are both capable of migrating up to 2,500 miles per year, and the Barn Swallow logs more than 6,000 miles annually.
How do they find their way? Scientists still have a long way to go before they understand completely how birds navigate. The evidence available today seems to suggest that they use a combination of different methods.
First, the birds may use visual clues. Many animals learn to recognize their surroundings to determine their way. They remember the shape of mountain ridges, coastlines, or other topographic features on their route, where the rivers and streams lie, and any prominent objects that point to their destination. Birds may use this method to locate their nest, but it seems unlikely that it will support flights over long distances. And it clearly cannot be used for navigating over large bodies of water or for flying at night, both of which many species of birds do every year.
Other methods depend on determining the direction of the North Pole. Modern humans usually do this using a compass. How do the birds know which direction is, say, north? One possibility for setting direction is to use the position of the sun in the sky. Many birds have been shown to use the sun to determine where north is. This is not as simple as it might first appear, since the sun changes its position in the sky throughout the day and the pattern of those daily changes itself varies with the seasons of the year. To use the sun to set the direction to north, you have to know where the sun is located in the sky at each time of the day at the precise time of year the journey takes place. For a human navigator, that task alone requires mastery of trigonometry.
Another possibility is that birds discern polarization patterns in sunlight. As the sun’s rays pass though our atmosphere, tiny molecules of air allow light waves traveling in certain directions to pass through, but they absorb others, causing the light to be polarized. We humans can see the polarization effect if we look up into the sky at sunset. The polarized light forms an image like a large bow-tie located directly overhead, pointing north and south. It seems that some birds can detect the gradation in polarization from the nearly unpolarized light in the direction of the sun to the almost 100% polarized light 90 degrees away from the sun, and this provides them with a giant compass in the sky. Honeybees also appear to use the polarized light to find their way on cloudy days, when the sun canÕt be seen. All they need is a small patch of blue sky to see the sun’s rays through, and the polarization effect shows them the way.
One obvious problem with birds using the sun to navigate is what do they do at night? Since many birds fly at night, navigating by the sun is clearly not the only method they use.
One possibility, which works at night as well as by day, is to make use of the Earth’s magnetic field. This, of course, is exactly what we do when we use a magnetic compass. Some birds use a similar method to navigate. For instance, inside the skull of a homing pigeon is a small pod of magnetic particles, which provides the bird with a tiny magnetic compass in its head. By attaching small magnets to the heads of test birds, researchers have shown that homing pigeons navigate by means of the Earth’s magnetic field. The magnets deflect the Earth’s magnetic field around the birds, and cause them to fly off course. (Put crudely, with the magnet attached to its head, the bird thinks that any direction it is facing is north.)
Star navigation provides yet another means of navigating that works at night. This method was used by human sailors in times past. At least one species of birds—Indigo Buntings—is known for sure to use the stars to navigate, and it is generally believed that they all do. It appears that they learn to recognize the pattern of stars in the night sky when they are still fledglings in the nest. A few years ago, a study found that nestling Indigo Buntings in the northern hemisphere watch as the stars in the night sky wheel around Polaris—the north star, which lies due north for those in the northern hemisphere. Scientists speculated that being able to identify Polaris in the night sky could help birds identify north. To test this hypothesis, they showed the birds a natural sky pattern inside a planetarium. The birds flew in a direction consistent with being able to detect the motion of the stars. When the experimenters changed the set up so that Betelgeuse was now the star which the stars rotated around, the birds flew in a direction consistent with Betelgeuse being the pole star. They no longer went where they should have relative to Polaris. So, they werenÕt using the locations of specific star patterns. They were noticing which star the others rotated around. In other words, it wasn’t the star patterns, but how the stars moved that counted. For the birds, “north” was where there was a star around which all other stars moved.
Whatever method the birds use to orient themselves, however, orientatation is just part of navigation. For humans, at least, setting the right course from the orientation requires trigonometry. How do the birds do it?
Scientists don’t know the answer to that question. What we do know, is that when we humans try to emulate the navigational feats of lobsters or migrating birds, we have to resort to mathematics. In human terms, those creatures have built-in mathematical ability: they have brains that have evolved to carry out the trigonometrical calculations necessary to determine north from the position of the sun or to set a course based on a knowledge of where the North Pole lies. They are, in short, natural born mathematicians.
Or are they? Is it reasonable to describe as mathematics an activity that is surely purely instinctive? Can we really say that lobsters and migrating birds do math? Here’s why I think the answer has to be “yes.”
We would all agree, I think, that when we use a calculator or a computer to solve a math problem, we are still doing mathematics. In many instances we would even be prepared to say that the calculator or the computer does the math. What then if some non human living creature solves the same problem? The Indigo Bunting, for example? Is there any justification for denying that it too is doing mathematics?
You might argue that no bird is consciously aware of doing any calculations. But then neither is your hand calculator or your computer. You might then counter, “Ah, but the calculator or computer was designed by human engineers to do mathematics.” To which I would retort, “But lobsters and birds were designed by Nature to do (that particular) mathematics.”
When we approach mathematics as a purely human endeavor, we focus almost exclusively on the conscious performance of computational processes – numerical, algebraic, geometric, etc. – often carried out with the aid of a pencil and paper, or these days some form of electronic computational device such as a calculator or computer. Those kinds of activity are certainly part of mathematics, but if you start from the fact that mathematics—the science of patterns as I like to call it—is about recognizing and manipulating patterns, then viewing the paper-and-pencil stuff we humans do as being all there is to mathematics is like saying that flying is about having wings and flapping them up and down. True, that is how birds fly, but if you take that as being what flying is about you exclude all those jet aircraft that fly around the globe every day. Flying is more fundamental than either birds or airplanes; it is about leaving the ground and moving through the air for extended periods of time. Feathered wings that flap and metal wings engineered by Boeing (that hopefully do not flap) are just two particular ways of performing that activity.
If you are willing to acknowledge that computers can do math—and it is really hard to deny this when there are computer systems that could pass any high school math test, and many university exams come to that—then there really is no justification for denying the same classification to animals that quite plainly solve problems that we humans solve only by mathematics. After all, on the scale of consciousness, computers lie at the very bottom, well below lobsters and birds. This is precisely the point I make in The Math Instinct. Once you get away from the pencil-and-paper view of mathematics we all get from our school days, and you think about the more fundamental activity that those school methods provide just one way of doing, you find that math is all around us. If you want to find the world’s greatest mathematician, you don’t need to travel to Harvard or Stanford or Princeton. Just visit the ocean or look up at the birds in the sky. For Mother Nature turns out to be the greatest mathematician of all. Through evolution, Nature has endowed many of the animals and plants around us with built-in mathematical abilities that, from a human perspective, are truly remarkable.
That’s not only an amazing feature of Nature; it also provides a radical new perspective on mathematics—on what math is and what it means to do math. A perspective that I think could go a long way to helping people overcome the fear they have of what they wrongly perceive to be an unnatural pursuit.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) will be published in April by Thunder’s Mouth Press.
APRIL 2005
What does “DOING MATH” mean?
With a new book out this month, I’ve started the now familiar round of media interviews that, these days, is part and parcel of being an author. So far, one question that always comes up is for me to give my opinion on the controversial remarks made recently by Harvard president Lawrence Summers about a possible genetic basis for there being fewer women than men in math and science.
Since I study neither gender issues nor genetics, and since I am not a scientist (insofar as that is different from being a mathematician), the only “authority” I can bring to the question is in the area of mathematical ability, so that’s what I’ll stick to here.
As it happens, the question is fairly closely related to the topic of that new book that’s got me back onto the media circuit in the first place, namely the innate mathematical abilities of various living creatures, including—but not exclusively—humans. (For a brief overview, see The Math Instinct website at www.mathinstict.com.)
The first thing to observe is that the very question “Are men on average better than women at math?” is not sufficiently precise. Expressed that way, the question implicitly assumes that mathematical ability is a single mental capacity. It’s not.
“Doing math” involves all kinds of mental capacities: numerical reasoning, quantitative reasoning, linguistic reasoning, symbolic reasoning, spatial reasoning, logical reasoning, diagrammatic reasoning, reasoning about causality, the ability to handle abstractions, and maybe some others I have overlooked. And for success, all those need to be topped off with a dose of raw creativity and a desire—for some of us an inner need—to pursue the subject and do well at it.
I guess it’s possible that if you have any one of those specific cognitive abilities I just listed, then you have them all in equal amounts, but frankly I doubt it. In fact, based on oft-repeated claims about the relative mental strengths of men and women when it comes to things like linguistic ability and logical reasoning ability, my list contains some elements often attributed to women and others to men. Whether those claims have any real substance is another matter. But even if they do, it looks to me on the face of it that any differences might pretty well balance out when it comes to doing math.
Still, whether there are aggregate innate gender differences in mathematical ability between men and women is, of course, an entirely empirical question, that could, I suppose, be resolved by doing sufficient research. My own feelings about the entire Summers episode is that much of the debate obscured what I think is a far more important point: that there are plenty of well catalogued data pointing to the enormous effect on math achievement brought about by social and cultural influences and by the often subconscious attitudes teachers bring into the classroom. Those factors influence math performance both across racial and social groups as well as gender. And we can try to do something about it right now. Indeed, many people are doing just that. My money goes on this being the pressure point where a greater effect by far can be achieved.
But that is not what I want to discuss today. I want to go back to that question of what it means to do mathematics. That might seem to be a pretty simple question, but unless you take a particularly dogmatic stance on the matter, it turns out to be extraordinarily difficult to come up with an answer.
One such dogmatic stance is the one I myself was brought up with when I was indoctrinated into the world of professional mathematics in the late 1960s and early 1970s. Namely, that mathematics – and here I am thinking about pure mathematics, which is what I was taught – is about developing rigorous logical proofs about formally defined abstract structures, starting with a set of precisely formulated specific axioms. In short, Hilbert stuff, right down to an acceptance of his famous “tables and beer mugs” remark. I took to it like a duck to water (or maybe beer), and it provided me with immense intellectual satisfaction and a great career for twenty years or more. For me, anything that did not fit that Hilbertian mold simply wasn’t (real) mathematics.
But after a couple of decades of that, my interests began to broaden, and I shifted my focus to trying to apply mathematics—in my case not to the physical, business, or economic worlds, as many of my colleagues were starting to do (I guess it was an age thing, where there is a tendency for both your intellectual interests and your butt to broaden), but to the world of linguistics and social science. I also started to step back from the activity of doing math (either pure or applied) to reflecting on what it really means to “do math.” One outcome of that change in perspective was my book The Math Gene, published in 2000.
The main question considered in The Math Gene was how did the human brain acquire the capacity to think mathematically? To answer that question, I had first to analyze just what “think mathematically” means. Since mathematics is a Johnny-come-lately in the human cognitive field, doing math has to come down to taking mental capacities that were acquired by our ancestors over tens or hundreds of thousands of years of evolution, long before what we usually think of as mathematics came along, and using them in a novel way to perform a new trick (or set of tricks).
The thesis I eventually came up with suggested that doing mathematics makes use of nine basic mental abilities that our ancestors developed thousands, and in some cases millions, of years ago, to survive in a sometimes hostile world. Those nine mental capacities are:
1. Number sense. This includes, for instance, the ability to recognize the difference between one object, a collection of two objects, and a collection of three objects, and to recognize that a collection of three objects has more members than a collection of two. Number sense is not something we learn. Child psychologists have demonstrated conclusively that we are all born with number sense.
2. Numerical ability. This involves counting and understanding numbers as abstract entities. Early methods of counting, by making notches in sticks or bones, go back at least 30,000 years. The Sumerians are the first people we know of who used abstract numbers: Between 8000 and 3000 B.C. they inscribed symbols for numbers on clay tablets.
3. Spatial-reasoning ability. This includes the ability to recognize shapes and to judge distances, both of which have obvious survival value for many animals.
4. A sense of cause and effect. Much of mathematics depends on “if this, then that” reasoning, an abstract form of thinking about causes and their effects.
5. The ability to construct and follow a causal chain of facts or events. A mathematical proof is a highly abstract version of a causal chain of facts.
6. Algorithmic ability. This is an abstract version of the fifth ability on this list.
7. The ability to handle abstraction. Humans developed the capacity to think about abstract entities along with our acquisition of language, between 75,000 and 200,000 years ago.
8. Logical-reasoning ability. The ability to construct and follow a step-by-step logical argument is another abstract version of item 5.
9. Relational-reasoning ability. This involves recognizing how things (and people) are related to each other, and being able to reason about those relationships. Much of mathematics deals with relationships among abstract objects.
All nine capacities are basic mental attributes important to our daily lives. The human brain had acquired them all by 75,000 years ago at the latest.
A question that arose while I was writing The Math Gene, but which I did not pursue very far at the time, was to what extent those nine mental capacities could be found in creatures other than ourselves? To put it bluntly: is doing math a uniquely human activity?
This is where you need to decide what you will accept as “doing math.” Hilbertian purity aside, if your understanding of doing mathematics entails deliberative, purposeful, self-aware, directed, thought about properties and questions concerning numbers, geometric shapes, equations, etc., often (but not necessarily and not always) carried out with the aid of a paper and pencil, then indeed mathematics is a uniquely human activity. But if you do want to make that your definition of doing mathematics, then you should be consistent.
For example, when we use a calculator or a computer to solve a math problem, would you say we are still doing mathematics? Surely yes. But in many cases, the calculator (especially if it is a fancy graphing calculator) or computer (especially if it is running software such as Mathematica) is performing crucial steps that the user initiates but does not actively control, may not be aware of, and may not understand. In such a situation, when pressed, most of us would say that the calculator or the computer “does the math.”
What then if some non-human living creature does something similar? For example, every year, many varieties of birds, fish, and other creatures migrate over hundreds or thousands of miles. In human terms, that necessarily involves solving some fairly advanced problems of navigation, including accurate time keeping, speed measurement, orientation, and trigonometry. Now, no one, I think, would claim that a migrating creature is solving mathematical problems the way humans do. Indeed, it seems highly likely that the creature does not even have any reflective awareness of what it is doing. Most probably it is simply following an innate instinct.
But then, your hand calculator or your computer is not aware of doing anything either. In its own terms (if that has any meaning) it is simply obeying the laws of physics, particularly as they pertain to the flow of electrons. Describing its behavior as “doing math” is to describe it in human terms. The computation is in the eyes of the beholder, not intrinsic to the device itself.
Given that your electronic device has far less conscious experience than any bird or fish, if you are prepared to describe actions of your calculator or computer as “doing math,” why not describe the analogous activities of a migrating creature the same way?
Of course, you might then counter, “Ah, but the calculator or computer was designed by human engineers to do mathematics.” To which I would retort, “But millions of years of evolution by natural selection – a remarkably effective “design process” if ever there was one – is what resulted in that creature being able to do that particular mathematics (i.e., that activity that in human terms amounts to doing math) that is important to its survival.
Once you start down this path of trying to figure out what it means to “do math,” you pretty soon come into some deep philosophical issues. Let’s suppose we have agreed that computers and migrating birds and fish “do math.” Would you say that when a river flows it solves the Navier-Stokes equations (the partial differential equations that describe the way fluids flow—which human mathematicians do not know how to solve, incidentally)? In a sense, the answer has to be yes. But personally I would draw my line—and it’s of necessity going to be a fuzzy line since we are talking about descriptions here—to exclude the river from the “does math” category. Follow that path and everything could be said to be doing math, and the concept becomes meaningless. (Unless you are a physicist and you want to view the entire universe as computation, but that’s another issue.) To me, to be classified as “doing math,” an action by some entity has to lead to a meaningful output. The (loose) definition of “doing math” I take in The Math Instinct is that the activity, or a closely similar one, when performed by a human, would be said to involve doing mathematics. Even so, there are some borderline cases, some of which I consider briefly in the book. (Beavers building dams and spiders constructing webs are two such.)
The problem with approaching mathematics as a purely human endeavor is that we focus almost exclusively on the conscious performance of computational processes—numerical, algebraic, geometric, etc.—often carried out with the aid of a pencil and paper, or these days some form of electronic computational device such as a calculator or computer. Those kinds of activity are certainly part of mathematics, but if you start from the fact that mathematics is about recognizing and manipulating patterns, then viewing the paper-and-pencil stuff we humans do as being all there is to mathematics is like saying that flying is about having wings and flapping them up and down. True, that is how birds fly, but if you take that as being what flying is about you exclude all those jet aircraft that fly around the globe every day. Flying is more fundamental than either birds or airplanes; it is about leaving the ground and moving through the air for extended periods of time. Feathered wings that flap and metal wings engineered by Boeing (that hopefully do not flap) are just two particular ways of performing that activity.
Once you view mathematics as the science of patterns, and think of doing math as reasoning about patterns, and allow for different devices or creatures to “reason” in their own way, recognizing that classifying a particular activity as “computing” or “doing math” is in the eyes of the beholder, you realize that, far from being unique to modern humans, mathematics is all around us. In The Math Instinct, I give many examples of non-human, “natural born mathematicians,” some of them quite amazing. To put the matter somewhat anthropomorphically, through the process of evolution by natural selection, nature has endowed many of the creatures around us with built-in mathematical abilities that, from a human perspective, are often truly remarkable. In short, Mother Nature turns out to be one of the greatest mathematicians of all. Continuing in this anthropomorphic vein, I can’t resist ending with the observation that she (Mother Nature) is female.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
MAY 2005
Street Mathematics
Imagine you are in South America. You are walking through a crowded, bustling, noisy street market, full of activity. You’re actually in the city of Recife in Brazil, but it could be any one of dozens of cities in South America. You walk up to one of the stalls, selling coconuts. It is manned by a largely uneducated twelve-year old boy from a poor background.
“How much is one coconut?” you ask.
“Thirty-five,” he replies with a smile.
You say, “I’d like ten. How much is that?”
The boy pauses for a moment before replying. Thinking out loud, he says: “Three will be 105; with three more, that will be 210. (Pause) I need four more. That is . . . (pause) 315 . . . I think it is 350.”
I didn’t make up this exchange. It is taken verbatim from a report written some years ago by three researchers, Terezinha Nunes of the University of London, England, and Analucia Dias Schliemann and David William Carraher of the Federal University of Pernambuco in Recife, Brazil. The three researchers went out into the street markets of Recife with a tape recorder, posing as ordinary market shoppers. At each stall, they presented the young stallholder with a transaction designed to test a particular arithmetical skill.
The purpose of the research was to determine how effective was traditional mathematics instruction, which all the young market traders had received in school since the age of six.
How well did our young coconut seller do?
If you think about it for a moment, it’s clear that the boy isn’t doing it the quickest way, which is to use the rule that to multiply by 10 you simply add a zero—so 35 becomes 350. The reason he doesn’t do it that way is that he doesn’t know the rule. He’s never learned it. Despite spending six years in school, he has almost no mathematical knowledge at all in the traditional sense. What arithmetical skills he has are self taught at his market stall. Here is how he solves the problem.
Since he often finds himself selling coconuts in groups of two or three, he needs to be able to compute the cost of two or three coconuts; that is, he needs to know the values 2 x 35 = 70 and 3 x 35 = 105. Faced with your highly unusual request for ten coconuts, the young boy proceeds like this. First, he splits the 10 into groups he can handle, namely 3 + 3 + 3 + 1. Arithmetically, he is now faced with the determining the sum 105 + 105 + 105 + 35. He does this is stages. With a little effort, he first calculates 105 + 105 = 210. Then he computes 210 + 105 = 315. Finally, he works out 315 + 35 = 350. Altogether quite an impressive performance for a twelve-year old of supposedly poor education!
But posing as customers was just the first stage of the study Nunes and her colleagues carried out. About a week after they had “tested” the children at their stalls, they went back to the subjects and asked each of them to take a pencil-and-paper test that comprised exactly the same arithmetic problems that had been presented to them in the context of purchases the week before.
The investigators took pains to give this second test in as non-threatening a way as possible. It was administered in a one-on-one setting, either at the original location or in the subject’s home, and included both straightforward arithmetic questions presented in written form and verbally presented word problems in the form of sales transactions of the same kind the children carried out at their stalls. The subjects were provided with paper and pencil, and were asked to write their answer and whatever working they wished to put down. They were also asked to speak their reasoning aloud as they went along.
Although the children’s arithmetic was practically faultless when they were at their market stalls (just over 98% correct), they averaged only 74% when presented with market- stall word problems requiring the same arithmetic and a mere 37% when virtually the same problems were presented to them in the form of a straightforward arithmetic test.
The performance of our young coconut seller was typical. One of the questions he had been asked at his market stall, when he was selling coconuts costing 35 cruzeiros each, was: “I’m going to take four coconuts. How much is that?” The boy replied: “There will be one hundred five, plus thirty, that’s one thirty- five . . . one coconut is thirty-five . . . that is . . . one forty.”
Let’s take a look at this solution. Just as he had in the exchange I described earlier, the boy began by breaking the problem up into simpler ones; in this case, three coconuts plus one coconut. This enabled him to start out with the fact he knew, namely that three coconuts cost Cr$105. Then, to add on the cost of the fourth coconut, he first rounded the cost of a coconut to Cr$30 and added that amount to give Cr$135. He then (apparently, though he did not verbalize this step precisely) noted that the “correction factor” for the rounding was Cr$5, and added in that correction factor to give the (correct) answer Cr$140.
On the formal arithmetic test, the boy was asked to calculate 35 x 4. He worked mentally, vocalizing each step as the researcher requested, but the only thing he wrote down was the answer. Here is what he said; “Four times five is twenty, carry the two; two plus three is five, times four is twenty.” He then wrote down “200” as his answer.
Despite the fact that, numerically, it was the same problem he had answered correctly at his market stall, he got it wrong. If you follow what he said, it’s clear what he was doing and why he went wrong. In trying to carry out the standard right-to-left school method for multiplication, he added the carry from the units-column multiplication (5 x 4) beforeperforming the tens-column multiplication, rather than afterwards, which is the correct way. He did, however, keep track of the positions the various digits should occupy, writing the (correct) 0 from the first multiplication after the (incorrect) 20 from the second, to give his answer 200.
In case after case, Nunes and her colleagues obtained the same results. The children were absolute number wizards when they were at their market stalls, but virtual dunces when presented with the same arithmetic problems presented in a typical school format. The researchers were so impressed—and intrigued—by the children’s market-stall performances that they gave it a special name: They called it street mathematics. Since the Recife children demonstrated that they could handle arithmetic in the appropriate context, when the numbers meant something to them, it seems clear that meaning plays a major role in our ability to do arithmetic. When the children carried out computations at their stalls, both the numbers and the operations they performed on them had meaning, and the operations made sense. Indeed, the children were quite literally surrounded by physical meanings of the arithmetical procedures they performed.
In contrast to street mathematics, the essence of school mathematics, which the Recife children were not able to do, is that it is entirely symbolic; i.e., it operates on symbols that are devoid of meaning. In performing a standard school procedure for addition, subtraction, multiplication, or division, you carry out the very same actions, in exactly the same order, regardless of what the actual numbers are or what they measure. This is the whole point. The methods taught in school are supposed to be universal. Learn them once and you can apply them in any particular circumstance, whatever specific numbers are involved.
In the hands of a person who can master the abstract, symbolic procedures taught in school, those procedures are extremely powerful. Indeed, they underpin all our science, technology, and modern medicine, and practically every other aspect of modern life. Their development marks one of the crowning achievements of the human race. But that doesn’t make them easy to learn or to apply.
The problem is that humans operate on meanings. In fact, the human brain evolved as a meaning-seeking device. We see, and seek, meaning anywhere and everywhere. We can’t avoid it. A computer can be programmed to slavishly follow rules for manipulating symbols, with no understanding of what those symbols mean (in fact no understanding at all), until we tell it to stop. But people can’t do that—at least, not to anything like the same extent. With considerable effort, we (or at least some of us) can learn our multiplication tables and train ourselves to follow a small number of arithmetical procedures. But even then, I think meaning is the key. I believe that mastery of school arithmetic involves the acquisition of some kind of meaning for the objects involved and the procedures performed on them. I don’t think the human brain can perform genuinely meaningless operations at all.
If I’m right, then that means that a crucial component of mathematics education is making sure that the student is able to construct (or otherwise acquire) appropriate meanings for the various abstract concepts and methods he or she is faced with. A particularly intriguing question is whether that can be done without recourse to plain old rote learning. I don’t know the answer to that question. I have some thoughts, and I express them in the latter part of my recent book The Math Instinct, from which this month’s column is taken. But now my time is up for this month.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
JUNE 2005
Staying the course
“I tried, professor, I really did, but I just couldn’t see how to do it.” Surely, every college or university mathematics instructor has faced this lament as a student hands in an incomplete homework assignment.
Sometimes the student is probably being honest. He or she did try. But what does that “try” amount to? Five minutes? Ten? Half and hour? In my experience, it is rare to encounter a student who will spend more than a few minutes on a math problem, let alone the several hours—or more—it might require. Most students don’t know what it means to niggle at problem—to worry it—on and off for days or weeks on end. In their eyes (if they think about it at all), those of us who do mathematics for a living are some kind of alien species, born with a weird brain that finds math easy. We’re not, of course. Our brains are not that different from theirs. Any mathematician who says she or he finds math easy isn’t tackling sufficiently challenging problems. The fact is, what most of our students don’t realize is that mathematicians are not people who find math easy. We don’t. We find it hard. The key factor is that we recognize that, given enough effort, and enough time, it is nevertheless possible.
Not that mathematics is particularly unusual in requiring effort to succeed. Most things do. Take writing, for example. I had a student once in a math course for nonscience majors, which I had structured in large part around writing about mathematics. She came to me to complain about the grade I had given her for an essay. I had deducted marks for the poor structure of her paper, which in truth amounted to little more than a list of points on which an essay might be based. Some of her points were good, and I gave her credit for those. But what she handed in didn’t come close to being a completed essay. She couldn’t see it, and she was indignant that I, a mathematician, would dare to evaluate her writing. I pointed out to her that just because mathematics was my primary professional interest did not mean I was not able to evaluate an essay. And as it happens, I said, writing about mathematics was something I had built a second career around.
I asked her what her major was. English, she proclaimed proudly, adding that she was a writer and wanted to have a career in professional writing. I asked her how many drafts she had gone through in order to produce the work she had handed in. She seemed not to understand my question. To her, writing an essay was a one-shot deal. No period of prior thought and reflection. No first, second, and maybe further, drafts. No revisions. I pointed to a small pile of books in the corner of my office, the complementary copies of my latest book, Life by the Numbers, that had just been sent to me by the publisher. (This was back in 1996.) “You see that book?” I said. “If you took every draft I wrote for that book, and piled them one on top of another, the stack would probably rise to shoulder height. I went through dozens of drafts, trying to get it right.” It soon became clear that I was wasting my time. To her, telling her that it took me so many revisions to produce a version that I—and my editor—felt happy sending to the printers, simply showed what she already assumed: that I was a poor writer.
Faced with students who think that if you don’t get something right immediately, you might as well give up, what hope is there to teach them any mathematics? How could such a student even begin to appreciate the many years—not days or weeks or months, but years—it took San Jose State University professor Dan Goldston and his colleagues to make their recent breakthrough discovery about the pattern of the prime numbers, which I described in a recent news article on MAA Online. Would any of them be able to understand how Goldston could recover from the collapse of what seemed like a correct proof that he announced in 2003, go back to square one, and try again. And keep trying, until the problem finally yielded? Or not; for in mathematics it is always on the cards that a problem will never yield.
I find it a paradoxical feature of American youth that large numbers of them bring a feverish intensity to sporting endeavors, putting in endless hours of dedicated training to become the best in their school, their district, their country, or even the world, yet only a few will put in the same kind of effort to mastering mathematics.
As recently as twenty-five years ago, the situation was very different. Early in my academic career, when my home base was in the UK, I used to come over to the USA frequently for a semester at a time to collaborate with colleagues at various universities, funding my trips by teaching courses as a visiting faculty member. I used to look forward to those trips not only because of the research activities they afforded, but because of the students I would teach. In contrast to most of the students I dealt with at home, many of my American students were highly motivated, hard working, fiercely competitive, and determined to show they were the best in the world. They would go to heroic lengths to avoid being defeated by a problem. Two decades later, living in the US now, I still encounter such students from time to time. But they no longer seem to be in the majority. For most of the young people I meet, the spark I used to see in their predecessors seems to be absent. What has led to this change? Why do so many of them seem to give up so easily? And is there anything we can do about it?
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
JULY-AUGUST 2005
When numbers matter
“Power cables linked to cancer” was the attention grabbing headline in Britain’s Guardian newspaper on June 3. “Children living near high-voltage power lines are substantially more likely to develop leukemia, researchers from Oxford University and the national grid report today in the British Medical Journal,” the article began. “Those living within 200 metres of the overhead cables were 70% more likely to develop the disease than similar children living more than 600 metres away.”
Now, Britain’s Guardian newspaper is hardly a supermarket tabloid that deals in sensational stories of dubious authenticity, but a highly respectable national daily newspaper. And the claims it reported had been accepted for publication in the British Medical Journal. So when I read the article, I had little doubt that the facts reported were true, at least in a literal sense. But that 70% increased risk figure seemed way, way too high to be true, in the sense that I, and presumably most other readers, initially understood it.
To get a better appreciation of that dramatic—and scary—70% figure, let’s consider a hypothetical, numerically simplified scenario. Suppose we have a population of 100,000 children, half living near a power line, half not. Suppose that 10 of the children who do not live near a power line develop leukemia over a given period while 17 who do live near a power line also develop leukemia over the same period. Thus, there are 70% more leukemia cases among the children living near power lines than among those who do not live near power lines. (I took the figures I did precisely to get me that 70% increase; 17 is 70% greater than 10. In a moment I’ll check to see how realistic my estimates are.)
Now look not at the percentages in my example but the actual numbers of leukemia cases involved. The 27 cases in total amount to a mere 0.027% of the population. Breaking this figure down into the two groups, the risk factor for children not living near power lines is 0.010%, the risk for children who do live near power lines is 0.017%. True enough, the latter figure is 70% greater than the first, but these are tiny risks. How realistic are my figures? A Google search reveals that a typical incidence figure for leukemia is 4 to 5 new cases a year per 100,000 people. So if we set the time period in my example at five years, my estimates—guesses would be more accurate—are pretty realistic. In short, the incidence of leukemia is truly tiny, regardless of where you live in relation to power lines.
This is not to say that the difference is not statistically significant. (And it is certainly not to diminish the anguish of the small number who do fall victim to the disease.) Even if we assume that there is a significant correlation between living near power lines and the incidence of leukemia, however, what conclusions can be drawn from the figures? The Guardian article was careful not to conclude that exposure to high voltage power lines can cause leukemia, but many readers will surely make that assumption. Yet as anyone who has taken a college statistics course will know, correlation is not causation. While there may remain the possibility that long-term exposure to the electromagnetic fields surrounding high voltage power lines can lead to cancer, there is another possibility that is, to my mind, far more likely.
What kind of people live close to power lines? By and large, poor people. The pylons are ugly and the lines emit a constant hum, particularly in wet weather. Property values are dramatically lower near power lines. Consequently, people who can afford to live elsewhere, generally choose to do so. Personally, I would not live near a power line (and I don’t) if I had a choice (which I do). Yes, the mere possibility that power line exposure might be detrimental to my health is one of the factors that I take into consideration. But that is part of a whole range of lifestyle choices aimed at living a long, physically healthy life, surrounded by psychologically invigorating scenic beauty (free of nearby power lines), eating good food, and exercising regularly. If I had to put my money on it—and unlike many people who live near power lines I have money to spare that I could waste on such a wager—I would say that it is likely to be one or more factors associated with poverty that give rise to an increased incidence of leukemia, not the effects of an electromagnetic field.
To provide even more perspective, let me add that, given the rare overall incidence of leukemia anyway, from a numerical point of view the disease is likely to be one of the least significant effects of poverty on growing children, and if we do want to take action, it should be directed against poverty, not power distribution companies.
There may indeed be a significant message regarding child health in the Guardian article. But I think it’s about poverty, not power lines.
In fact, the Guardian article carries another message, the one that this column is directed toward. Namely, that numbers, being powerful, are dangerous unless handled properly. What looks on the face of it like an alarming statistic that demands immediate and drastic action turns out after a few moments reflection to be nothing of the kind. Now, when I made my initial estimate of the risks, I had no idea what the real leukemia incidence figures are for a randomly chosen population of 100,000 people. I simply picked numbers that I guessed were roughly of the right order, and which got me quickly to that reported 70% increase figure. I could have looked up the real data behind the Guardian story. But that’s not the point—which is why I didn’t. The real issue as I see it is that it generally doesn’t require more than a few minutes with some sensibly chosen hypothetical figures in order to get a general sense of what a particular statistic might really mean. Do we teach students—tomorrow’s citizens and politicians—to be able to approach in this way the statistics they read? I hope we do. But I worry that we don’t.
Let me leave you with another statistical problem to ponder over the summer months, particularly if your vacation plans call for air travel, when you can pass your time reflecting on the matter while you stand in the security line at the airport. Have the enormous expenditure and inconvenience of the heightened security measures we have put into place led to a net saving of American lives?
You’ll have to do some guesswork here to come up with numbers to play with, just as I did above. You’ll need to come up with a plausible figure for the number of lives that would have been lost through airborne terrorist incidents if we just had the pre- 9/11 security measures, and then you’ll need to produce an estimate for the increased number of road accident deaths caused by the greater numbers of people who, faced with the increased hassle of flying in today’s climate, now choose to drive to their destination rather than fly, whenever they have a choice.
A variant of the same problem: would more lives be saved if the money we now spend on airport security were channeled instead into fitting every new automobile with a device that immobilizes it if the person sitting behind the wheel has more than a certain level of alcohol in his or her breath?
Or suppose—echoes of the post World War II Marshall Plan—we divert funds from increased security and fighting overseas wars to making the lives of people in the known terrorist breeding grounds sufficiently rewarding and full of hope that they have reasons not to be suicide terrorists.
I don’t know the answer to these questions. I’m not sure there are correct answers. There may be too many unknowns. And I’m certainly not advocating any particular actions. (My suspicion is that locking all cockpit doors eliminated most of the risk of further aircraft hijackings, and all that highly visible stuff at the airport is more for show than anything else. Still, I typically fly around 100,000 miles a year, so I personally have a vested interest in keeping the skies free of terrorists. As for Iraq, I can imagine at least one possibly valid reason for invading Iraq, though it’s not the bogus one the nation was given at the time, any more than the dropping of the two atomic bombs in 1945 was really about ending the war in Japan, a case that seems to me to have several similarities to the invasion of Iraq).
But that’s not the point. The point—at least, my point—is that I’m not sure anyone has really thought about the issues from a simple numerical angle. Not even those who make the decisions on our behalf. (If they have, then why haven’t they told us about their considerations?) If no one has made those simple, yet highly informative calculations, that’s a great pity. Humankind has had numbers for ten thousand years now. Using numbers, we can make better decisions. Sometimes, that requires the use of sophisticated mathematics. But quite often, a few quick calculations on the back of an envelope are enough. Not necessarily to get “the right answer.” Rather, just to get a better grasp of the issues. Maybe there’s a shortage of envelopes?
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
SEPTEMBER 2005
Naming theorems
The July 19 edition of The New York Times carried an article profiling the actress Danica McKellar, the former child star who played the part of Winnie Cooper on the television series “The Wonder Years”, and who is currently seen from time to time in the TV series “The West Wing”, playing Elsie Snuffin, a White House speechwriter.
As an undergraduate at UCLA, Ms McKellar majored in mathematics, and in her senior year engaged in an undergraduate research project with fellow student Brandy Winn, supervised by Professor Lincoln Chayes, that resulted in the publication of a paper in a professional research journal. The main result in the paper is now known as the “Chayes-McKellar-Winn theorem”.
Although she returned to acting after she completed her degree, Ms McKellar has maintained her involvement in mathematics through a math Q&A section on her website danicamckellar.com, in which she answers questions sent in by readers.
Reading the Times article made me reflect on how certain theorems acquire names. Since the majority of results are not given names, I suspect that Ms McKellar’s theorem is so called in large part because of her television fame.
Although it is generally regarded as bad form for mathematicians to try to attach their own names to theorems they prove, occasionally a theorem of mathematics does become named after the person who first proved it, but there is no general rule as to how this happens. Most mathematicians prove many theorems in their lives, and the process whereby their name gets attached to one of them is very haphazard. For instance, Euler, Gauss, and Fermat each proved hundreds of theorems, many of them important ones, and yet their names are attached to just a few of them.
Sometimes theorems acquire names that are incorrect. Most famously, perhaps, Fermat almost certainly did not prove “Fermat’s Last theorem”; rather that name was attached by someone else, after his death, to a conjecture the French mathematician had scribbled in the margin of a textbook. And Pythagoras’s theorem was known long before Pythagoras came onto the scene.
Another example of a theorem ascribed to entirely the wrong person is “Wilson’s theorem”, that (p-1)! + 1 is a multiple of p for any prime number p. This result was not proved by Wilson. Wilson guessed it might be true, but a chap called Waring subsequently proved it. In fact, the result was known to Lagrange before Wilson or Waring got into the act.
Sometimes a theorem gets named not after its discoverer but for its content. The famous Four Color Theorem is an example. It says that any map can be colored with at most four colors.
Occasionally, the naming can be quite whimsical. There’s the Ham Sandwich Theorem, which says that the volumes of any n n-dimensional solids can always be simultaneously bisected by a (n-1)-dimensional hyperplane. For n=2 it is known as the pancake theorem. It gets its name because if you take a ham sandwich you can make a single cut with a knife so that both slices of bread and the ham are cut into exactly equal halves. (This would be easy if the sandwich were made perfectly out of rectangular pieces, but most sandwiches are irregular.)
Or there’s the Hairy Ball Theorem. This says that, given a ball with hairs all over it, it is impossible to comb the hairs continuously and have all the hairs lay flat; some hair must be sticking straight up! A more formal version says that any continuous tangent vector field on the sphere must have a point where the vector is zero.
Most theorems in mathematics are proved by one or at most two mathematicians, but occasionally a larger group is involved. The HOMFLY theorem gets its name from the initials of the six mathematicians who proved it: Hoste, Ocneanu, Millett, Freyd, Lickorish, and Yetter.
The Darling-Erdos theorem (about random variables) sounds delightfully intimate until you realize that it was actually proved by two mathematicians, one of whom was called Darling.
Besides theorems, names also get attached to axioms, lemmas, equations, algorithms, and methods. For instance, we have Playfair’s Axiom, Zorn’s lemma, Pell’s equation, and so on.
Actually, Pell’s equation was not due to Pell but to Fermat. Pell simply copied it down from one of Fermat’s letters. Euler read it in Pell’s writing and mistakenly credited it to Pell. (Pell’s equation is actually not a single equation but a KIND of equation, namely a Diophantine equation of the kind y^2 – Ax^2 = 1. So it is misnamed in two ways.)
Though no one has as yet named a theorem after me, I believe I am the only mathematician whose name is attached to an angle. Though perhaps that’s cheating, since it depends on a pun on the word “angle”.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
OCTOBER 2005
Common confusions
I often get letters and emails from people asking me to clear up a confusion with some mathematical issue. Sometimes the confusion is occasioned by something I’ve written in a book or article or said on the radio, other times the question is sparked by something having nothing to do with me. But regardless of the origin, three issues crop up so often that I sometimes wonder if those of us who teach mathematics for a living aren’t always getting the message across quite clearly enough.
For instance, since the publication of my book The Math Gene in 2000, I’ve received a steady stream of messages from readers who believe there is an error in the proof I give there that there are infinitely many primes. There isn’t. The confusion that arises in some readers’ minds comes from my attempt to lay out the standard argument in a completely linear fashion. When I wrote the book, I formulated the proof the way I did because experience had shown me that an argument by cases can cause problems for some people. Unfortunately, eliminating the cases approach results in a different problem—rather, two different problems, as it turned out.
The argument by cases will be familiar to most readers of this column. The idea is to show that if you start to list the primes in order, P(1), P(2), P(3), etc., then the list continues for ever. To show this, you assume you have reached some stage P(N), and you prove that you can always find at least one more prime with which to continue the list. The idea—and it’s a brilliant one, known to the ancient Greeks and described in Euclid’s book Elements—is to consider the number
Q = [P(1) x P(2) x … x P(N)] + 1
obtained by multiplying together all the primes listed so far and then adding 1 to the product. Now the argument splits into two cases. If Q is prime, then since Q is bigger than P(N), it is a prime not already listed. If Q is not prime, then there must be some prime P that divides into Q. But P cannot be any one of P(1), …, P(N), since dividing any of those into Q leaves a remainder of 1. So P is a prime not already listed. Either way, there is a prime not in the list, so the list can be continued.
Now, if you are one of the many people who finds the above argument unproblematic, you may have trouble understanding why anyone would object to it. But believe me, many people do. (One problem that some people have—a problem I hoped to avoid by organizing the argument differently—is to assume that we have in some way identified the next prime to be added to the list. We have not; we’ve just showed that there is at least one more prime out there, and hence the list may be continued by picking the next one, whatever it may be.)
Knowing that the above argument causes some people difficulties, when I wrote The Math Gene, I formulated the proof in a slightly different way, as a proof by contradiction. To whit:
Suppose that there are only finitely many primes. List them all as P(1), P(2), …, P(N). (Thus P(N) is the largest prime.) Now look at the number
Q = [P(1) x P(2) x … x P(N)] + 1
Next we show that Q is prime. To do this, we show that it has no prime divisors. Well, all primes are in the list P(1), …, P(N), and each of those numbers leaves a remainder of 1 when you divide it into Q. Hence Q can have no prime divisors. Hence Q must itself be prime.
But Q is bigger than P(N), and P(N) is supposedly the largest prime, so we have a contradiction. Hence our initial assumption is false, which is to say, there must be infinitely many primes.
Now you might suspect that the reason some people have problems with this argument is that it uses the method of contradiction, and for some of my correspondents that seems to have been the case. But I also get letters from readers who clearly understand how proof by contradiction works, but who nevertheless feel the proof is wrong. Their misconception almost always comes from believing the argument claims that the number
Q = [P(1) x P(2) x … x P(N)] + 1
is prime for any value of N. That is easily seen to be false. For example,
[2 x 3 x 5 x 7 x 11 x 13] + 1 = 30031 = 59 x 509
But the argument I give makes no such claim. The claim that “Q is prime” is made for a specific (and decidedly hypothetical) value of N, namely the N for which P(N) is the supposed largest prime number, and the claim depends on that assumed property of P(N).
Now, I might have avoided problems if I had phrased the last part of my proof to avoid using the phrase “Q is prime”. This can easily be done. I didn’t because I wanted to split the entire proof into small, easily digested pieces, but maybe that was a poor choice. My choice did, however, highlight a problem that is far more fundamental. After engaging in several exchanges with readers who had trouble with my proof, I eventually realized that the problem was, at heart, confusion between variables and fixed, but unknown, constants. (Actually, in the case of my primes proof, a constant that does not exist at all outside the context of the proof!) And here is the lesson to be learned, I think. We mathematicians happily use letters to denote both variables and constants. But many people don’t see the distinction. They see a formula like
Q = [P(1) x P(2) x … x P(N)] + 1
and because N is a letter and not a specific number, such as 3, 6, or 29, they assume it denotes ANY number.
I suspect, but do not know for certain, that computer programmers would not make such an error. They, after all, have to know that once you set a variable X equal to a specific numerical value in a program, then it denotes that specific value, and nothing else, until reset to another specific value. They understand too the difference between a free variable and a variable that is bound by a context, such as being introduced in a subroutine. But I suspect that many students pass through one or more college level mathematics courses without ever coming to grips with the way mathematicians use letters to denote any one of a variable, a fixed but unknown number, or a known specific number.
The second matter that regularly lands upon my desk—or in my email inbox—is occasioned by attempts (in my own writing and that by others) to try to explain the basic ideas of the topological study of surfaces (specifically, orientability) by distinguishing between a wedding band (or cylinder) and a Moebius strip, in terms of the former “having two sides” and the latter “one side”. In my book Mathematics: The New Golden Age, for example, I try to explain orientability by considering what happens when you take a closed loop with an arrowhead in the surface and sliding it around, whereupon, in the case of a Moebius band, the arrow changes from clockwise to counterclockwise when you return to the starting point— something that does not happen in the case of a cylindrical (wedding) band. I illustrate the point with the following diagram.
(The loop starts just to the left of the line and moves around the band in a clockwise direction until it arrives back at the starting line.)
Several readers have written to me over the years saying that the diagram does not show what I claim it does. When you get back to the starting line, they say, the loop is actually on “the other side” of the band, and you have to go around again to get back to the starting point. But if you interpret the diagram as intended, this is not the case. The key issue is, the surfaces that mathematicians study don’t have sides. They just are. That’s why I was careful just now to say that the arrowed loop is in the surface, not “on” it. Strictly speaking, there is nothing for the loop to be “on”; it can only be in the surface. The two “sides” that a physical band exhibits are features of the physical model, not the mathematical surface it is intended to represent. (A more mathematical way of saying this is that the two “sides” that you see are part of the three-dimensional space surrounding the surface, not the surface itself.)
To carry out the loop transportation process physically, and have it represent what is really going on in terms of the mathematical surface being represented, it’s best to create the band from a strip of a clear material such as a slide for an overhead projector, and then draw the loop in successive positions as you move around the band, being careful to copy the arrow’s direction faithfully at each stage. Then, although you have to draw the loop on one (physical) side of the material, since you can see it easily well from either (physical) side, it’s easier to imagine the loop being in the surface and not “on” it. Do that and you will indeed see that the loop-arrow changes direction when you have transported it around the band and back to its starting point.
The third confusion that I get asked to clear up (or accused—often with great vehemence—of getting wrong in my writing) concerns probability. But I’ve already used up my monthly allotment of space, so I’ll turn to that in a later column. Stay tuned.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
NOVEMBER 2005
Common confusions II
Last month in this column I discussed some of the confusions about mathematical issues that occasion people to contact me. By far the most common topic concerns probability. Probability calculations cause so many problems for so many people that there is little chance that I can do more than scratch the surface in this column, so I’m going to zero in on just one issue. It is, however, the issue that, over many years of corresponding with people who have written to me, I have come to believe is the root of the majority of the problems: What exactly does a numerical probability tell us?
For the kinds of example that teachers and professors typically use to introduce students to probability theory, the issue seems clear cut. If you toss a fair coin, they say, the probability that it will come down heads is 0.5 (or 50%). [Actually, as the mathematician Persi Diaconis demonstrated not long ago, it’s not exactly 0.5; the physical constraints of tossing an actual coin result in roughly a 0.51 probability that it will land the same way up as it starts. But I’ll ignore that wrinkle for the purposes of this explanation.] What this means, they go on to say, is that, if you tossed the coin, say, 100 times, then roughly 50 times it would come down heads; if you tossed it 1,000 times, it would come down heads roughly 500 times; 10,000 tosses and heads would result roughly 5,000 times; and so forth. The actual numbers may vary each time you repeat the entire process, but in the long run you will find that roughly half the time the coin will land on heads. This can be expressed by saying that the probability of getting heads is 1/2, or 0.5.
Similarly, if you roll a fair die repeatedly, you will discover that it lands on 3 roughly 1/6 of the time, so the probability of rolling a 3 is 1/6.
In general, if an action A is performed repeatedly, the probability of getting the outcome E is calculated by taking the number of different way E can arise and dividing by the total number of different outcomes that can arise from A. Thus, the probability that rolling a fair die will result in getting an even number is given by calculating the number of ways you can get an even number (namely 3, since each of 2, 4, and 6 is a possible even number outcome) and dividing by the total number of possible outcomes (namely 6, since each of 1, 2, 3, 4, 5, 6 is a possible outcome). The answer, then, is 3 divided by 6, or 0.5.
Notice that the probability is assigned to a single event, not the repetition of the action. In the case of rolling a die, the probability of 0.5 that the outcome will be even is a feature of the action of rolling the die (once). It tells you something about how that single action is likely to turn out. Nevertheless, it derives from the behavior that will arise over many repetitions, and it is only by repeating the action many times that you are likely to observe the pattern of outcomes that the probability figure captures.
Probability is, then, an empirical notion. You can test it by experiment. At least, the kind of probability you get by looking at coin tossing, dice rolling, and similar activities is an empirical notion. What causes confusion for many people is that mathematicians were not content to leave the matter of trying to quantify outcomes in the realm of games of chance.
Consider the following scenario. Suppose you come to know that I have a daughter who works at Google; perhaps you meet her. I then tell you that I have two children. This is all you know about my family. What do you judge to be the likelihood (dare I say, the probability?) that I have two daughters? (For the purposes of this example, we’ll assume that boys and girls are born with exactly 50% likelihood.)
If you are like many people, you will argue as follows. “I know Devlin has one daughter. His other child is as likely to be a boy as a girl. Therefore the probability that he has two daughters is 1/2 (i.e., 0.5, or 50%).”
That reasoning is fallacious. If you reason correctly, the probability to assign to my having two daughters is 1/3. Here is the valid reasoning. In order of birth, the gender of my children could be B-B, B-G, G-B, G-G. Since you know that one of my children is a girl, you know that the first possibility listed here does not arise. That is, you know that the gender of my children in order of birth is one of B-G, G-B, G-G. Of these three possibilities, in two of them I have one child of each gender, and in only one do I have two daughters. So your assessment of the likelihood of my having two daughters should be 1 out of 3.
But even if you figure it out correctly, what exactly is the significance of that 1/3 figure? As a matter of fact, I do have two children and one of my children is a daughter who works at Google. Does anyone believe that I live in some strange quantum-indeterminate world in which my other child is 1/3 daughter and 2/3 son? Surely not. Rather, that 1/3 probability is a measure of your knowledge of my family.
As it happens, I have two daughters. So, if you asked me what probability I would assign to my having two daughters, I would say probability 1.
Does this mean that different people can rationally assign different probabilities to the same event? Not in the case of things like coin tossing or dice rolling. But that’s not what’s going on here. The probability I asked you to calculate a moment ago was a quantitative measure not of my family but of your knowledge of my family. And there is no reason why the measure you should ascribe to your knowledge is the same as I ascribe to mine. We know different things.
In my experience, it’s when probabilities are attached to information (as in this last case) that most people run into problems.
The concept of probability you get from looking at coin tossing, dice rolling, and so forth is generally referred to as “frequentist probability”. It applies when there is an action, having a fixed number of possible outcomes, that can be repeated indefinitely. It is an empirical notion, that you can check by carrying out experiments.
The numerical measure people assign to their knowledge of some event is often referred to as “subjective probability”. It quantifies your knowledge of the event, not the event itself. Different people can assign different probabilities to their individual knowledge of the same event. The probability you assign to an event depends on your prior knowledge of the event, and can change when you acquire new information about it.
Having made the distinction, however, I should point out that it is not as clear cut as might first appear. Sometimes a subjective probability is more psychological than mathematical, such as when someone says “I’m 99% certain I turned the gas off before I left.” At the other end of the spectrum, any frequentist probability can be viewed as a subjective probability. For instance, the probability of 1/2 that I assign to the possibility of getting a head when I toss a fair coin ten minutes from now is, when thought of as a measure of my current knowledge about a future event, a subjective probability according to the definition just given. (Clearly, when we quantify our information about a future occurrence of a repeatable action, where the frequentist notion of probability applies, we should assign the frequentist value.)
I am sure (90.27% sure, to be precise!) that a confusion between the frequentist and subjective notions of probability is what lies behind the problem many people having in understanding the reasoning of the notorious Monty Hall problem that I discussed in this column a couple of years ago (July 2003). That problem is posed to appear to be about a physical situation (where a prize is hidden) but in fact it is not; it’s about your individual knowledge of that situation, and how that knowledge changes as you receive additional information.
In fact, there is an entire branch of probability theory devoted to the way probabilities may be updated as new information arises: Bayesian inference. I discussed Bayesian theory in this column back in February 2000.
Although probability theory arose in studies of outcomes at the gaming tables of sixteenth and seventeenth century Europe, and despite the fact that scenarios such as tossing coins or rolling dice provide simple, easily understandable introductory examples, there are today so many important applications of Bayesian inference, that I have come round to the belief that those of us in the math ed business would better serve our students if we introduced probability from the very start as a measure of our knowledge of things that happen in the world, not a measure of the world itself. The outcomes of gambling games and state lotteries would then be just one special category where the probabilities we ascribe to our knowledge may be computed with total precision.
Finally, let me end with a fascinating idea put forward by the great Italian mathematician Bruno de Finetti (1906-1985) to add numerical precision to even highly subjective probability assessments. I’ll use de Finetti’s idea to examine my earlier example of the person who says they are “99% certain” they turned off the gas. It’s possible to replace that vague “99% certain” figure by a more meaningful certainty measure by asking the individual who makes the claim to play a “de Finetti game.”
Let’s suppose you are the person who makes the claim. I now offer you a deal. I present you with a jar containing 100 balls, 99 of them red, 1 black. You have a choice. Either you draw one ball from the jar, and if it’s red, you win $1m. Or we can go back and check if the gas is on, and if it is not, I give you $1m.
Now, if your “99% certain” claim were an accurate assessment of your confidence, it would not make any difference whether you choose to pick a ball from the jar or go back with me and check the status of the gas stove. But I suspect that, when it comes to the crunch, you will elect to pick a ball from the jar. After all, there is only 1 chance in 100 that you will fail to win $1m. You’d be crazy not to go for it.
By electing to pick a ball, you have demonstrated that, what I will call your rational confidence that you have turned off the gas, is at most 99%.
Now I offer you a jar that contains 95 red balls and 5 black, with choosing a red ball again netting you $1m. Assuming you again choose to select a ball rather than go and check out the gas, we may conclude that your rational confidence that you have turned off the gas is at most 95%. If it were really more than that, you should decline the ball-picking offer and go with me to check out the gas at your home. (So much for your “99%” claim!)
Then I offer a jar with 90 red balls and 10 black. If you choose to pick a ball this time, your rational confidence that you have turned off the gas can be at most 90%.
And so on.
Eventually, you decide you would prefer to check the gas to selecting a ball from the jar. If that happens when there are N red balls in the jar, then your rational confidence is precisely N%. The de Finetti procedure has established an exact correspondence between your subjective probability and a frequentist probability.
Neat, eh?
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
DECEMBER 2005
Monty Hall revisited
In last month’s column, titled “Common Confusions II”, I discussed some of the problems that many people have reasoning about probabilities. As I expected, among the emailbag the column generated were several emails from individuals who were sure that I had made a mistake in the example I gave—notwithstanding the fact that the entire column was about how many people get that particular example wrong! (For the record, my solution was correct.)
With some trepidation, toward the end of my article I referred back to an earlier column in which I had discussed the infamous Monty Hall Problem. My trepidation was not unfounded. I also received emails from readers who looked back at that earlier piece and were absolutely convinced that the solution I had given (in that earlier column) was wrong. More interesting were emails from people who posed slight variants of the original Monty Hall problem. In this week’s column, I’ll consider the most common of those variants.
The Monty Hall story so far. In the 1960s, there was a popular weekly US television quiz show called Let’s Make a Deal. Each week, at a certain point in the program, the host, Monty Hall, would present the contestant with three doors. Behind one door was a substantial prize; behind the others there was nothing. Monty asked the contestant to pick a door. Clearly, the probability of the contestant choosing the door with the prize was 1 in 3 (i.e., 1/3). So far so good.
Now comes the twist. Instead of simply opening the chosen door to reveal what lay behind, Monty would open one of the two doors the contestant had not chosen, revealing that it did not hide the prize. (Since Monty knew where the prize was, he could always do this.) He then offered the contestant the opportunity of either sticking with their original choice of door, or else switching it for the other unopened door. (As the game was actually played, some weeks Monty would simply let the contestant open their chosen door. The hypothetical version of the game described here, where Monty always opens the door and makes the “switch or stick” offer, is the one typically analyzed in statistics classes.)
The question now is, does it make any difference to the contestant’s chances of winning to switch, or might they just as well stick with the door they have already chosen?
When they first meet this problem, many people think that it makes no difference if they switch. They reason like this: “There are two unopened doors. The prize is behind one of them. The probability that it is behind the one I picked is 1/3, the probability that it is behind the one I didn’t is the same, that is, it is also 1/3, so it makes no difference if I switch.”
A common variant is for people to think that the two probabilities are not 1/3 and 1/3, but 1/2 and 1/2. Again, the intuition is that they are faced with two equally likely outcomes, but instead of regarding them as two equal choices that remain from an initial range of three options, they view the choice facing them as a completely new situation.
Surprising though it may seem at first, however, either variant of this reasoning is wrong. Switching actually doubles the contestant’s chance of winning. The odds go up from the original 1/3 for the chosen door, to 2/3 that the other unopened door hides the prize.
There are several ways to explain what is going on here. Here is what I think is the simplest account.
Imagine you are the contestant. Suppose the doors are labeled A, B, and C. Let’s assume you (the contestant) initially pick door A. The probability that the prize is behind door A is 1/3. That means that the probability it is behind one of the other two doors (B or C) is 2/3. Monty now opens one of the doors B and C to reveal that there is no prize there. Let’s suppose he opens door C. (Notice that he can always do this because he knows where the prize is located.) You (the contestant) now have two relevant pieces of information:
[1] The probability that the prize is behind door B or C (i.e., not behind door A) is 2/3.
[2] The prize is not behind door C.
Combining these two pieces of information, you conclude that the probability that the prize is behind door B is 2/3.
Hence you would be wise to switch from the original choice of door A (probability of winning 1/3) to door B (probability 2/3).
Now, if you have never seen this problem before, or have still not managed to “see the light”, there is really little point in you reading on. (Besides, you probably can’t resist spending your time instead emailing me to tell me my reasoning is fundamentally flawed.) But if you have, perhaps with great effort, come to convince yourself that the above reasoning is correct, then prepare yourself for another shock.
Consider a slightly modified version of the Monty Hall game. In this variant, after you (the contestant) have chosen your door (door A, say), Monty asks another contestant to open one of the other two doors. That contestant, who like you has no idea where the prize is, opens one at random, let us say, door C, and you both see that there is no prize there. As in the original game, Monty now asks you if you want to switch or stick with your original choice. What is your best strategy?
If you adopt the reasoning I gave earlier for the original Monty game, you will arrive at the same conclusion as before, namely that you should switch from door A to door B, and that exactly as before, if you do so you will double your likelihood of winning. Why? Well, you will reason, you modified the probability of the prize being behind door B from 1/3 to 2/3 because you acquired the new information that there was definitely no prize behind door C. It does not matter, you will say, whether door C was opened (to reveal no prize) by deliberate choice or randomly. Either way, you get the same crucial piece of information: that the prize is not behind door C. The original argument remains valid. Doesn’t it?
Well, no, as a matter of fact it doesn’t. In the original Monty problem, Monty knows from the start where the prize is, and he uses that knowledge in order to always open a door that does not hide a prize. Moreover, you, the contestant, know that Monty plays this way. This is crucial to your reasoning, although you probably never realized that fact.
Here, briefly, is the argument for the variant game:
You choose one door, say, door A. The probability that the prize is there is 1/3.
The probability that the prize is behind one of door B and door C is 2/3.
The other contestant has a choice between door B and door C. The odds she faces are equal. Assume she picks door C. The probability that she wins is 1/2 x 2/3 = 1/3.
The probability that she loses is likewise 1/2 x 2/3 = 1/3. And that’s the probability that you win if you switch. Exactly the same as if you did not.
Confused? As sometimes arises in mathematics, when you find yourself in a confusing situation, it may be easier to find the relevant mathematical formula and simply plug in the appropriate values without worrying what it all means.
In this case, the formula you need is due to an 18th Century English Presbyterian minister by the name of Thomas Bayes. Bayes’ formula languished largely ignored and unused for over two centuries before statisticians, lawyers, medical researchers, software developers, and others started to use it in earnest during the 1990s.
Bayes’ formula shows you how to calculate the probability that a certain proposition S is true, based on information about S, when you know:
(1) the probability of S in the absence of any information;
(2) the information about S;
(3) the probability that the information would arise regardless of whether S or not;
(4) the probability that the information would arise if S were true.
Let P(S) be the numerical probability that the proposition S is true in the absence of any information. P(S) is known as the prior probability.
You obtain some information E.
Let P(S|E) be the probability that S is true given the information E. This is the revised estimate you want to calculate. It is called the posterior probability.
A quantity such as P(S|E) is known as a conditional probability – the conditional probability of S being true, given the information E.
Let P(E) be the probability that the information E would arise if S were not known to be true and let P(E|S) be the probability that E would arise if S were true.
The ratio P(E|S)/P(E) is called the likelihood ratio for E given S.
Bayes’ theorem says that the posterior probability P(S|E) is derived from the prior probability P(S) by multiplying the latter by the likelihood ratio for E given S:
P(S|E) = P(S) x P(E|S) / P(E)
Notice how the formula reduces the problem of computing how probable S is, given the information, to computing how probable it would be that the information arises if S were true.
When you apply Bayes’ formula to the Monty Hall problem, you begin with an initial value for the probability attached to a proposition that the prize is behind the unchosen door B, say, namely 1/3. This is the prior probability. Then you modify that probability assessment based on the new information you receive (in this case, the opening of door C to reveal that there is no prize behind it) to give a revised, or posterior probability for that proposition, which works out to be 2/3.
Here is the computation in full detail.
You select door A, and Monty opens door C to reveal that there is no prize there. So you now know that p(C) = 0. What are your new estimates for p(A) and p(B)?
We will apply Bayes’ formula. Let E be the information that there is no prize behind door C, which you get when Monty opens that door. Then:
p(A|E) = p(A) x p(E|A) / p(E)
p(B|E) = p(B) x p(E|B) / p(E)
We need to calculate the various probabilities on the right of these two formulas.
p(A) = p(B) = 1/3.
p(E|A) = 1/2, since if the prize is behind A, Monty may pick either of B, C to reveal that there is no prize there.
p(E|B) = 1, since if the prize is behind B, Monty has no choice if he wants to open a door without a prize, he must open C.
p(E|C) = 0, since if the prize is behind C, Monty cannot open it.
Since A, B, C are mutually exclusive and exhaust all possibilities:
p(E) = p(A).p(E|A) + p(B).p(E|B) + p(C).p(E|C)
= (1/3).(1/2) + (1/3).(1) + (1/3).0
= 1/2
Hence, applying Bayes’ formula:
p(A|E) = p(A) x p(E|A) / p(E) = (1/3) x (1/2) / (1/2) = 1/3
p(B|E) = p(B) x p(E|B) / p(E) = (1/3) x (1) / (1/2) = 2/3
Thus, based on what you know after Monty opened door C to show that there was no prize there, you estimate the chance of winning if you stick is 1/3 and if you switch is 2/3. So you should switch.
Now let’s consider the variant game where another contestant opens door C and you both see that there is no prize there. This time, the various probabilities are:
p(A) = p(B) = 1/3.
p(E|A) = p(E|B) = 1/2, since if the prize is behind A, the other contestant may pick either of B, C to reveal that there is no prize there.
p(E|C) = 0, since if the prize is behind C, if the other contestant were to open it, you would see the prize.
Thus:
p(E) = p(A).p(E|A) + p(B).p(E|B) + p(C).p(E|C)
= (1/3).(1/2) + (1/3).(1/2) + (1/3).0
= 1/3
Hence, applying Bayes’ formula:
p(A|E) = p(A) x p(E|A) / p(E) = (1/3) x (1/2) / (1/3) = 1/2
p(B|E) = p(B) x p(E|B) / p(E) = (1/3) x (1/2) / (1/3) = 1/2
Thus, it makes no difference whether you stick or switch.
So there you have it.
Whether you believe it is another matter.
Devlin’s Angle is updated at the beginning of each month.
Mathematician Keith Devlin (email: devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and The Math Guy on NPR’s Weekend Edition. Devlin’s newest book, THE MATH INSTINCT: Why You’re a Mathematical Genius (along with Lobsters, Birds, Cats, and Dogs) was published recently by Thunder’s Mouth Press.
profkeithdevlin.org 