Opinion
Computing Applications Last byte

Puzzled: Probability and Intuition

Welcome to three new puzzles. Solutions to the first two will be published next month; the third is (as yet) unsolved. In each puzzle, the issue is how your intuition matches up with the mathematics.
Posted
  1. Article
  2. Author
  3. Footnotes
Dartmouth College Professor Peter Winkler

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?

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More