You are here

Digital Dice: Computational Solutions to Practical Probability Problems

Princeton University Press
Number of Pages: 

Over the last few years, Paul Nahin has written a variety of books such as An Imaginary Tale, Dueling Idiots, When Least is Best, and Chases and Escapes. I’ve read most of his books and enjoyed each one. Anyone reading his writing will find it detailed, well-presented, and there is always a hint of humor and a bit of story telling to animate his prose. Digital Dice is no exception to this and it has the added advantage of being participatory by definition  — the reader is expected to work on the problems and not just read the book.

Let’s begin with a quick overview. Nahin presents 21 problems for you to solve. Some have closed form solutions but the point to the book (and the fun!) is to deviate from analytics and write a program to simulate the problem conditions and then with a random number generator and lots of trials, find the solution with your simulation. Some of the problems are easily stated and easily coded. Others require more thought to code, say with a flow chart, but all the problems are recreational and delightful to ponder.

After Nahin presents the problems, he gives you detailed solutions. For each solution, there is a program listed in MATLAB code. Nahin explains each line of his program and he includes line numbers for reference which are not a part of MATLAB code. Of course, you would ideally have your own code to think about but if not, well, just reading the solutions is satisfying. Ordinarily, I would find a non-open source program discouraging because not all readers may have it. However, Nahin’s code is easy to read and can be easily translated to another language. He even goes to lengths to avoid the built-in vector operations of MATLAB because other languages don’t have them. The only two exceptions that are MATLAB dependent are quite minor: the “convhull” function to find the find the convex hull of a set of points and “hist” function to plot the histogram of a data set. Everything else is straightforward to translate.

If a closed form solution is available, Nahin provides it with considerable detail and explanations along the way. He compares the analytical answer to the simulation results so that the reader can see the performance of the simulation. Naturally, he gives graphs in the solutions and even drawings to illustrate some problems.

Let’s look at a few of the problems. My favorite is “The toilet paper dilemma.” A toilet stall has two fresh rolls of paper. Folks enter the stall at random and independently. Some folks are “big choosers” who always take paper from the big roll, and likewise some folks are “little choosers.” If the rolls are even in size each chooses to take from nearest roll. Now, let p be the probability of a big chooser entering a stall and q = 1-p the probability of a little chooser entering the stall. Each enters independently and at random. Let n be the starting length of the roll and let Mn(p) be average number of portions of paper left on a roll when the other roll empties. The problem is to explore the nature of M200(p) as p varies from 0 to 1.

Nahin does not, however, just state this problem. He tells the story of how Donald Knuth first wrote about this problem and he shows you a lovely recursion for Mn(p) with a simple, illustrative diagram. Only after he has thoroughly explained the problem does he ask you to find the solution.

Here’s another beautiful, counter-intuitive problem: Parrondo’s paradox. Two people are gambling in a game, say A. A, you are asked to show, is a loser for you. So, you also play another game with your opponent, say B. B is also a loser for you. What can you do to reverse your odds? Well, you can play both A and B but randomly switch between them. The trick, beyond the details of the game that I leave for you to read in the book, is that two losing games can be combined to form a winning game. With the right probabilities one losing game can rescue the other so that together they are a winning game.

As a third and final fun problem example, there is the optimal stopping problem. Nahin expresses it as a dating problem. You want to find a suitable spouse but you can’t date everyone and you don’t want to choose the first person you meet. What strategy should you employ, on average, to find a good spouse?

That’s a sampling and there are another 18 others worth exploring, coding, and enjoying.

Finally, please note that the problems are not new so you may well find some quite familiar. Even so, there should be a few to interest you and enjoy. If you have seen all the problems, well, the stories that pepper the text are fun, too.

David Mazel is an engineer in Washington, DC. He received his Ph.D. in electrical engineering from Georgia Tech and is interested in signal processing, billiards, and agent-based simulations. In his spare time, he enjoys mathematics with his children and playing with the family golden retriever.

Date Received: 
Monday, February 11, 2008
Include In BLL Rating: 
Paul J. Nahin
Publication Date: 
David S. Mazel

ntroduction 1

The Problems 35
1. The Clumsy Dishwasher Problem 37
2. Will Lil and Bill Meet at the Malt Shop? 38
3. A Parallel Parking Question 40
4. A Curious Coin-Flipping Game 42
5. The Gamow-Stern Elevator Puzzle 45
6. Steve's Elevator Problem 48
7. The Pipe Smoker's Discovery 51
8. A Toilet Paper Dilemma 53
9. The Forgetful Burglar Problem 59
10. The Umbrella Quandary 61
11. The Case of the Missing Senators 63
12. How Many Runners in a Marathon? 65
13. A Police Patrol Problem 69
14. Parrondo's Paradox 74
15. How Long Is the Wait to Get the Potato Salad? 77
16. The Appeals Court Paradox 81
17. Waiting for Buses 83
18. Waiting for Stoplights 85
19. Electing Emperors and Popes 87
20. An Optimal Stopping Problem 91
21. Chain Reactions, Branching Processes, and Baby Boys 96

MATLAB Solutions To The Problems 101
1. The Clumsy Dishwasher Problem 103
2. Will Lil and Bill Meet at the Malt Shop? 105
3. A Parallel Parking Question 109
4. A Curious Coin-Flipping Game 114
5. The Gamow-Stern Elevator Puzzle 120
6. Steve's Elevator Problem 124
7. The Pipe Smoker's Discovery 129
8. A Toilet Paper Dilemma 140
9. The Forgetful Burglar Problem 144
10. The Umbrella Quandary 148
11. The Case of the Missing Senators 153
12. How Many Runners in a Marathon? 157
13. A Police Patrol Problem 160
14. Parrondo's Paradox 169
15. How Long is the Wait to Get the Potato Salad? 176
16. The Appeals Court Paradox 184
17. Waiting for Buses 187
18. Waiting for Stoplights 191
19. Electing Emperors and Popes 197
20. An Optimal Stopping Problem 204
21. Chain Reactions, Branching Processes, and Baby Boys 213

Appendix 1. One Way to Guess on a Test 221
Appendix 2. An Example of Variance-Reduction in the Monte Carlo Method 223
Appendix 3. Random Harmonic Sums 229
Appendix 4. Solving Montmort's Problem by Recursion 231
Appendix 5. An Illustration of the Inclusion-Exclusion Principle 237
Appendix 6. Solutions to the Spin Game 244
Appendix 7. How to Simulate Kelvin's Fair Coin with a Biased Coin 248
Appendix 8. How to Simulate an Exponential Random Variable 252
Appendix 9. Index to Author-Created MATLAB m-Files in the Book 255

Glossary 257
Acknowledgments 259
Index 261
Also by Paul J. Nahin 264

Publish Book: 
Modify Date: 
Monday, July 7, 2008