MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

# Climbing Zeno's Tree

In an effort to puzzle out these patterns, I tried constructing the tree of all possible outcomes for games of a given depth. In other words, I listed the two available moves from the starting state x =1/2, then for each of these positions I wrote down the two possible outcomes of another coin flip, and so on. (Eventually I wrote a program to do the calculations and draw the tree.)

Before plunging into the intricacies of the Zeno tree, it's worth pausing to look at a simpler model—a random walk in which the step size is halved with every step. Starting at x =1/2, the walker goes either left or right a distance of 1/4, then 1/8, then 1/16, etc. Tabulating all possible walks of this kind yields a binary tree that fans out to reach all the dyadic rationals. The branches bifurcate symmetrically, and each branch is completely isolated from all the others. The descendants of two neighboring nodes will come arbitrarily close but never touch. In a wagering game based on this rule, winning the first round is enough to put you in the lead forever. Even if you lose every subsequent bet, your share of the wealth can never fall below 1/2.

The Zeno game tree starts out exactly like this tidy binary tree—the first three levels are identical—but then things start to get weird. In the lower levels of the tree there's a lot of disorder, with various gaps between adjacent nodes, and many crossing branches. Even more remarkable, many paths through the tree bifurcate and then immediately come together again. (Strictly speaking, a structure with loops of this kind isn't a tree at all, but it will do no harm to continue using the term.)

We can understand a lot of what's going on in the Zeno tree by looking at two specific fragments. First is the loop formed below the node at 1/4. One path descending from this node goes left to 1/8 and then right to 3/16; another path goes right to 3/8 and then left to meet up at 3/16. The fact that these two routes converge on precisely the same point is not some miraculous numerical coincidence; it's just a matter of working out the arithmetic:

When the dust settles, this identity comes down to the proposition that a half of three halves is three quarters, and likewise three halves of a half is three quarters.

The second interesting spot in the tree is right next door—the pair of paths descending from the node at 3/8. The branch to the left, as we've already seen, goes to 3/16, and then the next turn right on this path lands at 9/32. The alternative route heads right from 3/8 to 9/16; however, on the next leftward bend this path fails to rejoin its partner at 9/32. Instead the branch stops short at 11/32. The reason is that this path crosses the midline of the tree at x =1/2, and for points to the right of this line distance is measured not from 0 but from 1. The two branches fail to meet because the equation no longer holds:

This mechanism effectively divides the tree into three vertical zones. For all points to the left of 1/3 and to the right of 2/3, a node's two children are both on the same side of the midline and thus are governed by the same rule for calculating step lengths. As a result, these zones form a fairly regular latticelike structure, made up of diamond-shaped panes that grow narrower toward the periphery. In the middle zone, by contrast, all nodes have one child on each side of the midline, where different rules apply. The result is chaos.

The structure of this tree begins to illuminate some of the observations made about the statistical distribution of Zeno-game outcomes. For example, a simple counting argument explains the existence of gaps in the distribution. Every node of a binary tree has two descending links, which is just enough to reach all the dyadic rationals, whose population doubles at each level of the tree. But when links from two or more nodes converge on the same child node, then other nodes must be missing from the tree. (If I have two children and my spouse has two children, that doesn't necessarily mean we have four children.)

Counting can also explain why some game endings are more common than others—such as why 3/16 turns up twice as often as 1/16. Think of playing a Zeno game as tracing a pathway through the tree, starting at the root (level 0) and continuing down to some final node. At each interior node, the path turns left or right with equal probability. In the simple binary tree, this procedure yields the same probability for all the nodes at a given level. In particular, at the third level each of the eight nodes is reached with probability 1/8. In the Zeno tree, however, two different paths both lead to the third-level node at 3/16. Since there are two ways of getting to this node, the probability of landing there is doubled.

The path-counting analysis can be understood more clearly if we suppress some of the clutter and disorder in the Zeno tree. Suppose a random walk always takes steps of size x /2, adopting the rule that governs the left half of the Zeno tree but applying it everywhere. The corresponding tree has a uniform lattice structure in which it's easy to count paths (see illustration at left) . Every interior node has two parents, and the number of ways of reaching the node is simply the sum of the number of ways of reaching the parents. Hence the path counts correspond to the entries in Pascal's triangle.

There's something else notable about this tidied-up version of the Zeno tree: All the numbers that appear in the lattice take a very specific form: 3 m /2 n . Thus the numerators are drawn from the series 1, 3, 9, 27, 81,..., and the denominators follow the now-familiar progression 2, 4, 8, 16, 32.... These are the very numbers that appear with higher-than-average frequency in the Zeno game, and it's clear why. The highest path counts run down the middle of the lattice, supporting the observation that numbers such as 3/32, 9/64 and 27/256 are extraordinarily popular.

Of course the real Zeno tree is not so tidy; the lattice is torn apart between any two nodes on opposite sides of the midline. As a result of these trans-midline events, factors other than 3 can enter the numerator; they form shadow lattices of their own, visible in some parts of the tree. Thus the probabilities calculated from the simple lattice are at best approximations.