Duelling Idiots and Other Probability Puzzlers
By Paul J. NahinPRINCETON UNIVERSITY PRESS
Copyright © 2000 Princeton University Press
All right reserved.
ISBN: 978-0-691-15500-5
Contents
Acknowledgments....................................................................ixPreface............................................................................XXiIntroduction.......................................................................3The Problems.......................................................................151. How to Ask an Embarrassing Question.............................................152. When Idiots Duel................................................................163. Will the Light Bulb Glow?.......................................................224. The Underdog and the World Series...............................................265. The Curious Case of the Snowy Birthdays.........................................276. When Human Flesh Begins to Fail.................................................347. Baseball Again, and Mortal Flesh, Too...........................................34S. Ball Madness....................................................................369. Who Pays for the Coffee?........................................................4210. The Chess Champ versus the Gunslinger..........................................4511. A Different Slice of Probabilistic, Pi.........................................4912. When Negativity Is a No-No.....................................................5013. The Power of Randomness........................................................5114. The, Random Radio..............................................................5215. An Inconceivable Difficulty....................................................5516. The Unsinkable Tub Is Sinking! How to Find Her, Fast...........................5717. A Walk in the Garden...........................................................5515. Two Flies Stuck on a Piece of Flupper—How Far Apart?.....................6119. The Blind Spider and the fly...................................................6220. Reliably Unreliable............................................................6521. When Theory Fails, There Is Always the Computer................................71The Solutions......................................................................81Random Number Generators...........................................................176"Some Things Just Have to be Done By Hand!"........................................198MATLAB Programs....................................................................202Index..............................................................................267
Chapter One
The Problems 1. How to Ask an Embarrasing Question (A Warm-up Question Requiring Only Arithmetic)
Suppose you are assigned the following task: You are to determine the fraction of the population that practices a certain private act (use your imagination). If you could gather a large number of randomly selected people together into a large room or auditorium, you could then simply have each person fill out an anonymous questionnaire. Since no one could be identified from such a form, people would presumably tell the truth. But suppose this is not possible, and your task is to be accomplished over time through individual encounters. It is clear that you cannot just ask people, because they may or may not answer truthfully when confronted with the embarrassing question (EQ); you can't even use the form, because now no one "gets lost in the crowd." So how can you gather accurate data? You can use the following clever technique that I found described in a medical journal article.
You, or a member of your staff, give each person in the survey a fair coin as he or she arrives at your office. You then ask the individual to briefly step into a private room. There, all alone, the person flips the coin. If it shows tails, then the person writes the answer (YES or NO) to the EQ on a piece of paper. If, on the other hand, the coin shows heads, then the subject flips the coin a second time and writes the answer (YES or NO) to the non-EQ, "Did the coin show heads on the second toss?" After that, the person returns to your office and gives you the paper.
Now, each such piece of paper will have a single YES or NO on it, and eventually you'll have, let's say, 10,000 such pieces of paper. You do not know which question each particular person was actually answering, and yet you can now calculate the answer to your question: What percentage of the population (or, at least, of the people in the survey) practices the "private act"? Explain why this is so, and illustrate your analysis by calculating the percentage of people that practice the private act if 6,230 write YES and 3,770 write NO.
2. When Idiots Duel
Duelling problems are of strong interest to most people, perhaps because of their "life-or-death" nature. Here is one that is also, I think, amusing. A and B decide to duel but, being poor, they have just one gun (a six-shot revolver) and only one bullet. Being dumb, as well, this does not deter them and they agree to "duel" as follows: They will insert the lone bullet into the gun's cylinder, A will then spin the cylinder and shoot at B (who, standing inches away, is impossible to miss). If the gun doesn't fire then A will give the gun to B, who will spin the cylinder and then shoot at A. This back-and-forth duel will continue until one fool shoots the other. What is the probability that A will win? Also, how many trigger pulls will occur, on average, before somebody wins? The second question has meaning, of course, only if there is a large number of pairs of duelling idiots; for any particular pair, the duel occurs just once and lasts for a well-defined, specific number of trigger pulls.
(If A and B point the gun at themselves, then this foolish business is simply the two idiots alternately playing what is usually called "Russian roulette." A less violent—but perhaps not by much—form of the idiots' duel can be found in the 'sudden death' playoff between two pro football teams that are tied at the end of regulation play. There, A is the team that gets first possession of the ball.)
The methodical way to attack our two questions is to write out what mathematicians call the sample space of the experiment; that is, to write down all the possible outcomes of the duel. So, if we define two events as
a = gun fires for A
x = gun does not fire,
then the sample points for which A wins are
a xxa xxxxa and so on
That is, A wins only on those sample points that are of odd length. So, the answer to the first question is simply the sum of the probabilities of all the odd length sample points, i.e.,
P(A) = 1/6 + (5/6)2 1/6 + (5/6)4 1/6 + ...
where the sum has an infinite number of terms. Each term comes from the observation that if the duel lasts for exactly k trigger pulls, then the gun did not fire on the first k - 1 trigger-pulls and did fire on the kth one. The sum is easy to calculate. Just write P(A) = 1/6 S where
S = 1+(5/6)2 +(5/6)4 + ....
So, S is a geometric series, summed by the standard trick; i.e., multiply through by (5/6)2 to get
(5/6)2, S = (5/6)2 +(5/6)4 + ...
and then subtract. Thus,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
and so
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
P(A) is greater than 1/2, which means A has the better shot at winning the duel than does B; that is, of course, because A has the first shot.
For the second question, if we define D to be the duration of the duel (measured in trigger-pulls), then the average or expected value of D is given by the formula
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Since P(D = k) = (5/6)k-1 1/6, then
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Or, E(D) = 1/6 S, where now
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
This sum may look nasty to do because it is not a geometric series (with the increasing coefficient in each new term), but that is not the case. We can sum S using the same trick as before. So, multiplying through by 5/6, we have
5/6 S = 5/6 + 2 (5/6)2 + 3 (5/6)3 + ...
and so
S - 5/6 S = 1/6 S = 1 + (5/6) + (5/6)2 + (5/6)3 + ...
Now, the sum on the right-hand side is a geometric series. Using the multiply-and-subtract trick one more time (I'll let you do it), we get 1/6 S = 6. So, E(D) = 1/6 S = 6.
On average, then, a duel will last for six trigger pulls. Since this is just an average, however, then some duels will be shorter (perhaps just one trigger pull) and others will be much longer. To study the magnitude of the variation in the durations of many duels we can use a computer simulation. The MATLAB program idiotsl.m (Program 1 in the MATLAB programs at the end of this book) simulates 10,000 duels and keeps track of who wins and how long each duel lasts. The heart of the simulation is MATLAB's internal random number generator named rand. As with every high-level scientific programming language I am familiar with, the generator returns a number from a distribution that is uniformly distributed from 0 to 1 each time rand is called. (This is probably the right time to take a look at the historical essay at the end of the book, which has some discussion of random number generators in general and of MATLAB's generator in particular.) So, to simulate the firing of a six-shot revolver with just one bullet in the cylinder, simply call rand and see if the returned number is between 0 and 1/6 (gun fires) or greater than 1/6 (gun does not fire). The cylinder spin before each trigger pull makes the probability that the gun fires with each trigger pull 1/6, and is also independent of all previous trigger pulls.
When I ran idiotsl.m five times, for example, here is what was produced:
Run P(A) Average Number of Trigger Pulls 1 0.5517 6.0089 2 0.5508 5.9424 3 0.5496 6.097 4 0.5492 5.917 5 0.5513 5.9285
These results are in fairly good agreement with the theoretical answers, although the estimates for P(A) are a bit on the high side. It is interesting to note, from Figure 2.1, that a significant number of duels lasted longer than ten trigger pulls, and a few were longer than twenty trigger pulls.
Now, here's your problem. Our two idiots have decided, after reading the preceding analysis, to use a different procedure. They still have just one gun and one bullet but now, with each exchange of the gun, they get one additional trigger pull. That is, A puts the bullet in the cylinder, spins it and then shoots at B. If the gun doesn't fire, A gives the gun to B, who spins the cylinder and then shoots at A. If the gun doesn't fire, B spins the cylinder again and gets a second try. If the gun still doesn't fire, B gives the gun to A, who gets a maximum of three trigger pulls (with a spin of the cylinder between pulls), and so on. Calculate P(A) theoretically, as well as the average number of trigger pulls over many such duels. (Hint: The second question actually requires no calculation; just think of the physics of the duel.)
A final comment: I have used these duelling problems in my classes for years, never suspecting that truth is indeed stranger than fiction. After all, only idiots would actually enter into such foolish competitions, right? Well, I was wrong, as you can read for yourself in the book by Kevin McAleer, Dueling: The Cult of Honor in Fin-de-siècle Germany, Princeton University Press, 1994. It appears that (in Germany, at least) there was no shortage of real "duelling idiots" who took turns shooting at each other.
3. Will the Light Bulb Glow?
Imagine n switches in series to form a row of switches. Then, put n such rows in parallel to give a sheet of n2 switches. Then put n such sheets in series, as shown in Figure 3.1. Imagine that each of the n3 switches is, independently, either closed with probability p or open (as each is shown in the figure) with probability 1 - p. What is the probability P1(n, p) that the lamp glows?
This problem was originally given to electrical engineering students, who needed no further explanation (but not everybody is an EE.) So, the one physical concept you need to know is that for the bulb to glow there must be at least one complete path from the positive (+) terminal of the battery, through the bulb, and back to the negative (-) terminal of the battery.
As a variation on this problem, imagine that the n sheets are connected in parallel, rather than in series. (Parallel means to connect together the negative terminal of the battery and points A1, A2, ..., An, and then connect together the positive terminal of the battery and points B1, B2, ..., Bn). What is the probability P2(n, p) that the lamp will glow? Use a computer to study how P1 and P2 behave numerically as functions of n and p.
A little twist on this question converts it into one about what is called a random process; i.e., a problem in which time plays a central role. This is generally not a topic in a first course in probability, except perhaps in the second semester of a year-long course, but with a little help to get you started, you should be able to do this problem. Imagine that you have a circuit path as shown in Figure 3.2, consisting of just three series-connected modules of parallel-connected switches. Imagine further that each of the modules has an arbitrarily large number of switches, i.e., n -> ∞ where n is the number of parallel switches in a module. Initially, at time t = 0, all the switches are open. Then, once each microsecond, one of just two events occurs: Either nothing happens with probability 0.97, or at random with probability 0.03, exactly one switch (somewhere) closes and stays closed. So, sooner or later, as the modules evolve through time, there will come a time when, for the first time, at least one switch in each module will be closed and the electrical path between terminals a and a' will be completed and the bulb will glow. Your problem is to plot the probability of the bulb's glowing, as a function of time (in units of microseconds).
As a hint to get you started, define the state of the path aa' at any time t to be the number of modules that have at least one switch closed. (Notice that to have a completed path we need only one switch closed in each module; more than one switch closed in any given module doesn't affect the time at which the path is completed.) At time t = 0, then, the path is in state 0 and the path is completed for the first time as it enters state 3. So, if we write pk(t) as the probability the path is in state k at time t, then the answer to your problem is the plot of p3(t). To do this, first explain why the following difference equations are valid (see Problems 10 and 19 for more on difference equations in probability); then, use a computer to find p3(t) from them and from the initial probabilities p0(0) = 1, p1(0) = p2(0) = p3(0) = 0:
p0(t + 1) = 0.97 p0(t) p1(t + 1) = 0.03 p0(t) + 0.98 p0(t) p2(t + 1) = 0.02 p1(t) + 0.99 p2(t) p3(t + 1) = 0.01 p2(t) + p3(t).
Or, in matrix form,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
With [p0(0) p1(0) p2(0) p3(0)] = [1 0 0 0]. Or, even more compactly,
[p.bar](t + 1) = [p.bar](t)[P.bar], [p.bar](0) = [1 0 0 0],
where p(t) is called the state vector of the path and P (the 4 × 4 matrix) is the state transition probability matrix of the path. Notice that each row of P sums to one. Can you explain why? Probably, if you think about what each of the P(i, j) probabilities denotes.
This last problem is a very simple example of what is called a Markov chain, after the great Russian mathematician Andrei Andreevich Markov (1856–1922), who pioneered this extremely important branch of probability with a paper in 1906. Markov must have been quite an interesting fellow; he was well-known for speaking his mind without regard to political consequences. When the Czarist government organized a celebration in 1913, for example, in honor of the three-hundredth year anniversary of the house of Romanov, Markov responded by counter-organizing a celebration of the two-hundredth year anniversary of the publication of the weak law of large numbers in James Bernoulli's seminal Ars Conjectandi (1713). Luckily for Markov, the authorities dismissed his loudly expressed liberal views as simply those of an eccentric academic crank, or his career would surely have ended long before his natural death (after much suffering, following an eye operation). Problem 8 has some more discussion of Markov chains.
4. The Underdog and the World Series
The mathematics of the doggy problem has applications far removed from dogs and missiles. For example, the World Series is, as a first and crude approximation, a Bernoulli sequence of trials. Each trial is, of course, the playing of an individual game. Suppose the stronger team has probability p (>½, of course) of winning any particular game. What is P(p), the probability that the weaker team wins the series? (For those who don't follow baseball, the modern World Series is a best-of-seven competition; i.e., the first team to win four games wins the series.) In addition, find an expression for D(p), the average duration (in games) of the World Series as a function of p, and use the following actual historical data to estimate p (this is very crude, as it assumes p has been constant for nearly a century, but this is for fun).
Historical Data
From 1905 through 1999 there have been 91 World Series played by the modern rules. The first series, in 1903, was best-of-nine and so has been excluded, as were the series for 1919, 1920, and 1921, for the same reason. The series for 1904 was simply not scheduled, and the 1994 series was canceled because of a players' strike.
5. The Curious Case of the Snowy Birthdays
Probably the two most famous numbers in mathematics beyond arithmetic are π and e. Both are irrational (neither is equal to a ratio of integers), so their decimal expansions never repeat. Both can be computed with any desired degree of precision, however; π has been computed to several billion decimal places and e to not so many (but still a lot). There are many famous formulas for performing such calculations, for example
π = 4 (1 - 1/3 + 1/5 - 1/7 + 1/9 - ...
and
e = 1/0! + 1/1! + 1/2! + 1/3! + ....
Such exact formulas are not the only way to estimate π and e, however; there are random techniques, too. One well-known approach to experimentally estimate π is often presented in probability textbooks, based on the so-called Buffon needle tossing experiment (after Georges-Louis Leclerc (1707–1788), who became the Comte de Buffon). First proposed in a now-lost 1733 paper, and again in 1777 in his "Essai d'Arithmétique Morale," it is now too well-known to be suitable as a challenge problem; therefore, I will simply describe it and give the answers (there are two answers, with textbooks usually discussing only the simpler one). Imagine a surface upon which are ruled straight, parallel lines spaced distance d apart. If a short needle of length l ("short" means l ) is tossed randomly onto the surface, then the probability that the needle intersects a line is 2l/πd (see just about any modern undergraduate probability textbook for how to derive this result). The case for a long needle (l > d) is actually no more difficult to analyze, although I have not seen it done in any of the textbooks I've looked at; the result is the somewhat more complicated expression
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
Notice that if l = d, the two expressions give the same probability of 2/π, and that as l -> ∞ the probability of a long needle intersecting at least one line approaches 1 (which makes obvious physical sense, since as l -> ∞, the only way it would not intersect any lines is to land exactly parallel to the ruled lines, an event with a vanishingly small probability).
(Continues...)
Excerpted from Duelling Idiots and Other Probability Puzzlersby Paul J. Nahin Copyright © 2000 by Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
