COMPUTING SCIENCE

# Wagering with Zeno

# Walking with Zeno

The evolution of a Zeno wagering game corresponds to a special kind of random walk. A player's gains and losses are represented by the movement of a walker along the interval between 0 and 1. The walker starts at the position *x *=1/2. Each flip of the coin determines whether the next step is to the left (toward 0) or the right (toward 1). The length of the step is half the distance to whichever of these boundaries is nearer. In other words, the step length is 1/2 *min *( *x *, 1– *x *).

The illustration at left shows a few trajectories constructed according to these rules. One feature of note is an apparent tendency for paths to flee the middle of the interval and linger near the edges. It's not hard to understand this behavior, at least in a qualitative way. Whenever the walker is near the center, it is moving with higher velocity (that is, taking larger steps per unit time), and so it doesn't stay long in this neighborhood. Out at the periphery, the walker moves very slowly, and so it takes a long time to escape. It's as if the walker were moving over a landscape that's smoothly paved in the middle but becomes a sticky mire near the edges.

A plausible hypothesis suggests that a typical random walk will spend more and more time near the end points of the interval as the walk proceeds, coming arbitrarily close to 0 and 1. To test this idea you might follow a walk for many thousands of steps, but that process is computationally challenging. If you represent the walker's position by means of a floating-point number, the program will usually report that the walker has reached either 0.0 or 1.0 after just a few hundred steps. This outcome would surprise Zeno! The problem is that floating-point formats have only finite precision, and very small values are rounded to zero.

A remedy for the round-off problem is exact rational arithmetic, but this becomes cumbersome. Here is the unwieldy numerical value of a game score after 150 steps:

The numerator and denominator both have 45 digits, and they differ by less than one part in a trillion.

EMAIL TO A FRIEND :