9478

The Three-Tower Problem

There are three piles of chips. Two piles are chosen at random and a chip is moved from the first choice to the second. This procedure is continued until one of the piles becomes empty. The Demonstration shows simulations of this process. You can see the probabilities of the duration of the process and read the expected value and variance of the duration.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Snapshot 1: The development of the current number of chips in the three piles are shown with red, blue, and green paths. In this example, each of the three piles initially has five chips. After 70 steps, the first pile becomes empty; at this point, the other two piles have six and nine chips, respectively. When the piles initially have five chips each, the expected duration of the process is 25 and the most probable duration is 12. The duration cannot be 1, 2, 3, or 4 steps (these probabilities are zero). The process stops, with high probability, before 100 steps. However, there is no upper limit for the duration.
Snapshot 2: Here, the game only lasted six steps. The minimum number of steps is five when each pile starts with five chips.
Snapshot 3: Each pile now starts with 10 chips. The process lasted 312 steps, while the expected duration is 100. We could calculate that the probability that the game lasts at least 312 steps is 0.017.
It can be shown (see [3] and [1, pp. 39-40]), that if the piles initially have , , and chips, the expected duration of the process is . For example, if , the expected duration is . The whole distribution and the mean and variance of the duration of the process is computed in [2]. For example, the probability that the duration is is
,
where and .
The exact general expected duration is unknown for four piles. See [2] for an explanation of why no simple solutions can be expected for four or more piles.
The three-tower process can also be interpreted as a gambler's ruin process with three gamblers, as follows. A randomly chosen gambler loses a coin and another randomly chosen gambler gets it. The game continues until one of the three gamblers is ruined. For the original gambler's ruin problem with two gamblers, see The Gambler's Ruin.
References
[1] J. Andel, Mathematics of Chance, New York: Wiley, 2001.
[2] F. T. Bruss, G. Louchard, and J. W. Turner, "On the N-Tower-Problem and Related Problems," Advances in Applied Probability, 35(1), 2003, pp. 278–294.
[3] A. Engel, "The Computer Solves the Three Tower Problem," American Mathematical Monthly, 100(1), 1993, pp. 62–64. doi:10.2307/2324818.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+