MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

# Midline Crises

Those are all the answers I can offer on the Zeno wagering game, but I certainly haven't run out of questions. Here are three more.

First, how dense is the set of numbers included in the Zeno tree, measured as a proportion of all the numbers that might be present? At level n there are 2 n dyadic rationals in all; what fraction of them are Zeno-tree numbers, and how does that fraction evolve as n increases? At the first three levels of the tree the fraction is 1: All the dyadic rationals are included. Then there is a steep linear descent as the fraction goes from 3/4 to 5/8 to 1/2 to 3/8. This series obviously cannot continue or the tree will disappear in three more steps. And indeed the slope begins to flatten out: The next four elements of the series are 9/32, 25/128, 19/128 and 7/64. At this point each level of the tree includes only about a tenth of the dyadic rationals at that level. It seems a reasonable guess that the density will approach zero as n tends to infinity.

Second, how much structure can we find in the Zeno tree? To make this question more concrete, suppose you want to determine which node, on a certain level of the tree, gives the closest approximation to some specified value on the real number line. With the standard binary tree this is easy: You can list a series of left and right turns that describe a path from the root to the closest node. It's not clear to me how to find such a path in the Zeno tree, except by exhaustive search.

Finally there's this big question: If you allow a game to continue arbitrarily long, will one player gain an advantage and hold onto it indefinitely, or will the lead change hands repeatedly? In terms of the random walk, will the walker get stuck on one side, or will the walk cross back and forth over the midline? Of course it's always possible for the walker to get back to midline; all it takes is a sufficiently long sequence of steps in the right direction. But it doesn't necessarily follow that such an event will have a probability greater than zero when the number of steps grows without limit.

For what it's worth, here's what the experimental evidence suggests. In random walks of 10,000 steps, roughly half exhibit no midline crossings at all: The walker sets out either left or right initially and never gets back to the other side. For those walks that do cross the midline, the last observed crossing is usually within the first 10 steps; the latest I have seen is step 101. But trials of 10,000 steps, or even 10 million, prove nothing.