Communications of the ACM
Last byte
Puzzled: Probability and Intuition
1. It is your last night in Las Vegas as you celebrate your 29th birthday. Standing at the roulette table with $105 in your pocket, you resolve to make 105 successive $1 bets on the number 29. You will win $36 (minus your $1 bet) each time the ball lands on "29," but, unfortunately, this happens with probability only 1/38; the rest of the time you simply lose your dollar. Use your intuition. What is the probability that, after the 105 bets, you come out ahead?
2. A hundred people board a fully booked aircraft. Unfortunately, the first person in line somehow loses his/her boarding pass while entering and takes a random seat. Each successive passenger then sits in his/her proper seat, if available; otherwise, each one rather wimpily takes a random vacant seat. Again, use your intuition. What is the probability that the last passenger finds the properly assigned seat unoccupied?
3. The Random Arcade, a favorite hangout of local video gamers, boasts a line of n gumball machines. Each machine is unpredictable but produces an average of one gumball each time it is operated; for example, it may be that Machine no. 1 produces two balls half the time and the rest of the time none at all.
What is the maximum possible probability that if you put a coin in each machine, you will be rewarded with a total of more than n gumballs?
This puzzle (stated in terms of sequences of independent random variables) is due to Uriel Feige of the Weizmann Institute of Science, Rehovot, Israel. My intuition, and perhaps yours, too, suggests that the best possible situation is if each gumball machine disgorges n+1 gumballs with probability 1/(n+1), otherwise it gives nothing. That way, you succeed as long as at least one of the n machines pays off. What is your success probability?
Failure requires that every machine refuses to cooperate, happening with probability (1 - 1/(n+1))n. So you succeed with probability one minus that expression. For n = 1 through 6, this gives success probabilities of 1/2, 5/9, 37/64, 369/625, 4,651/7,776, and 70,993/117,649; to the nearest thousandth, these numbers are .500, .556, .578, .590, .598, and .603. The numbers approach 1 - 1/e ~ .632 from below as n increases. Thus, the answer appears to be 1 - 1/e.
However, despite some serious effort, no one has managed to prove that you can't do better than 1 - 1/e. Feige himself showed that the success probability can never exceed 12/13 ~ .923. Can you improve on his bound?
Footnotes
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1536616.1536642
©2009 ACM 0001-0782/09/0800 $10.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
No entries found