COMPUTING SCIENCE

# Wagering with Zeno

# In Search of Zeno's Urn

It's entirely possible that these questions have already been answered somewhere in the literature on probability models. Knowledgeable friends have pointed me to two areas in particular: urn models and reinforced random walks. I have not yet found any discussion of a model that I can recognize as being isomorphic to the Zeno game, but I've found some fascinating reading along the way.

Urn models are the 18th-century ancestor of the Powerball lottery: You mix up a bunch of balls in a container and draw them out one by one. Of particular relevance is a class of models studied by George Pólya, Bernard Friedman, David A. Freedman and a number of others, including recently Robin Pemantle. In one version, an urn initially holds one white ball and one black ball. Then each time a ball is drawn at random from the urn, that ball is put back in along with an extra ball of the same color. When the process is repeated many times, will the ratio of black to white balls settle down to some fixed value, or will it keep fluctuating? The answer is that in any single long run, the ratio will tend to a stable value, but the value itself is a random variable. If you try the experiment again, it will come out differently.

The reinforced random walk was invented by Persi Diaconis and has also been studied by Pemantle. The idea is to watch a random walker stepping from node to node through a network. Visiting a node increases the probability that the same node will be chosen the next time the walker is nearby. The question asked is whether the walker can range freely throughout the graph forever or will get trapped in some local neighborhood. The answer seems to depend on the details. On a one-dimensional lattice (like the line of integers), the walker gets stuck in a five-node region. But a variation that associates probabilities with the links between nodes rather than the nodes themselves allows the walker to escape confinement and visit every node infinitely often. On two-dimensional infinite lattices the fate of the walker is unknown.

It is unclear to me whether the Zeno game belongs to the same family as these models. The Zeno mechanism includes no explicit reinforcement of probabilities; on the other hand, it does have an indirect form of positive feedback, because movement away from the center reduces the step size and thereby makes it harder to move back. Perhaps the Zeno process can be reformulated in a way that will make the correspondence with known work clearer. But the analysis of all such models is a subtle art. Every time I think I'm getting close to an answer, it seems the problem has moved on a little further down the road.

© Brian Hayes

# Bibliography

Freedman, David A. 1965. Bernard Friedman’s urn.

*Annals of Mathematical Statistics*36:956–970.Friedman, Bernard. 1949. A simple urn model.

*Communications on Pure and Applied Mathematics*2:59–70.Hayes, Brian. 2002. Follow the money.

*American Scientist*90:400–405.Johnson, Norman L., and Samuel Kotz. 1977.

*Urn Models and Their Application: An Approach to Modern Discrete Probability Theory*. New York: Wiley.Krapivsky, P. L., and S. Redner. 2004. Random walk with shrinking steps.

*American Journal of Physics*72:591–598.Pemantle, Robin. 2007. A survey of random processes with reinforcement.

*Probability Surveys*4:1–79.Steinsaltz, David. 1997. Zeno’s walk: A random walk with refinements.

*Probability Theory and Related Fields*107:99–121.

EMAIL TO A FRIEND :