A Demonstration of a Theorem of Paul Erdős

Speed: Number of trials: 0

Explanation: Consider the following experiment. Place a black pebble and a white pebble in an empty urn. Then repeat the following step over and over: Remove a randomly selected pebble at random from the urn, then return that pebble to the urn along with another pebble of the same color. That is, if the removed pebble is white, drop two white pebbles into the urn; if the removed pebble is black, then drop two black pebbles into the urn. Keep track of the fraction of pebbles in the urn that are white. This fraction starts at 0.5. After one step, there are three pebbles in the urn and the fraction of white pebbles is either 1/3 or 2/3. After two steps, there are four pebbles in the urn, and the fraction of white pebbles is 1/4, 2/4, or 3/4. The question is, what happens or can happen to the fraction in the long run?

This web page simulates this experiment, and the results are shown as a graph in the black area above. The graph plots the fraction of white pebbles as a function of the number of steps. Steps increase from left to right, with one step per pixel. The fraction of white pebbles is zero at the bottom of the black rectangle and is one at the top. A randomly selected color is used for the graph. When the number of steps reaches the width of the black area, the experiment is terminated. A new experiment is begun, starting again with one black and one white pebble, and another random colors is selected for the new graph. Think about what you expect to happen before you run the simulation.

The "Fast" speed is about 10 times faster than the "Slow" speed, and the "Faster" speed is 5 times faster again. At the "Fastest" speed, an entire experiment is completed and the entire graph for that experiment is added to the picture at once. To see what tends to happen in the long run, run at "Fastest" speed for a while. (Note: To change the size of the black rectangle, change the window size and then reload this page.)

(Erdős proved that in a given experiment, in the long run the fraction of white pebbles will approach a constant value, with probability one. Furthermore, in multiple experiments, the limit values are evenly distributed in the interval from zero to one.)