COMPUTING SCIENCE

# Foolproof

Mathematical proof is foolproof, it seems, only in the absence of fools

Who's on First?

Donald E. Knuth of Stanford University once appended a note to a computer program: "Beware of bugs in the above code; I have only proved it correct, not tried it." Coming from Knuth, the warning is a joke, but if you hear it from me, you should take it seriously.

Allow me to bring back Socrates and the slave boy for a little exercise in probability theory. They are arguing about sports: In a best-of-seven tournament (such as the baseball World Series), what is the probability that the contest will be decided in a four-game sweep? Assume that the teams are evenly matched, so that each team has a 50-50 chance of winning any single game.

Socrates:In a best-of-seven series, how many ways can a team score a clean sweep?

Boy:Just one way. You've got to win four in a row, with no losses.

Socrates:And how many ways could we form a five-game series, with four wins and a single loss?

Boy:Well, youcould lose either the first, the second, the third or the fourth game, and win all the rest.

Socrates:And what about losing the fifth game?

Boy:If you win the first four, you don't play a fifth.

Socrates:So to build a five-game series, we take a four-game series and insert an additional loss at each position except the last, is that right?

Boy:I guess.

Socrates:Therefore we can create a six-game tournament by taking each of the five-game series and inserting an additional loss in each of five positions. Thus we have 4´5, or 20, six-game series.

Boy:If you say so.

Socrates:Then each of the 20 six-game series can be expanded in six different ways to make a seven-game series, and so there are 120 seven-game variations. Adding it all up, we have 1+4+20+120 cases, for a total of 145. Exactly one of these cases is a clean sweep, and so the probability is 1?145.

At this point the boy, who knows something about baseball, points out that of 98 best-of-seven World Series, 19 have been won in a clean sweep, suggesting an empirical probability nearer to 1?5 than to 1?145. Socrates is not swayed by this fact.

Socrates:Do not be distracted by mere appearances; here we studyidealbaseball. Let me demonstrate by another method.

Boy:Go for it.

Socrates:Suppose for the moment that the teams always play a full schedule of seven games. Since each game can have either of two outcomes, there are 2^{7}, or 128, possible sequences. Now go through the list of 128 patterns and remove all of those in which play continues after a team has already achieved four victories. I find that there are 70 distinct patterns remaining. Two of those patterns are clean sweeps—one for each team—and so the probability is 1?35.

Boy:You're getting warmer. Try this: Winning four games in a row has a probability of 1?2´1?2´1?2´1?2, or 1?16. Either team can have the clean sweep, so the combined probability is 1?16+1?16=1?8.

Deductive logic has led us to three different answers, at least two of which must be wrong. Although I have made Socrates the fool in this comedy of errors, I cannot conceal that the blunders are actually my own. A few years ago I had occasion to perform this calculation, and I got a wrong answer. How did I know it was wrong? It disagreed with a simple computer experiment: a program that simulated a million random World Series and produced 124,711 four-game clean sweeps. (That's almost exactly 1?8.)

What does it mean that I put greater trust in the output of a computer program than in my own reasoning? Well, I am *not* arguing that computer simulations are superior to proofs or more reliable than deductive methods. It's not that there's something wrong with classical mathematics. All three of the approaches discussed in my pseudo-Socratic dialogue can be made to yield the right answer, if they are applied with care. But proof is a tool that can also prove you a fool.

For those who believe they could never possibly commit such an error, I offer my congratulations, along with a reminder of the infamous Monty Hall affair. In 1990 Marilyn vos Savant, a columnist for *Parade* magazine, discussed a hypothetical situation on the television game show "Let's Make a Deal," hosted by Monty Hall. A prize is hidden behind one of three doors. When a contestant chooses door 1, Hall opens door 3, showing that the prize is not there, and offers the player the option of switching to door 2. Vos Savant argued (correctly, given certain assumptions) that switching improves the odds from 1?3 to 2?3. Thousands disagreed, including more than a few mathematicians. Even Paul Erd?os, a formidable probabilist, got it wrong. It was a computer simulation that ultimately persuaded him.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Arts Lab**: Bringing Postnatural History into View

**Engineering**: Robert Wilson: Fermilab’s Master Physicist, Sculptor, and Engineer

**Computing Science**: Clarity in Climate Modeling

**Foreign-Language PDFs**