COMPUTING SCIENCE

# Wagering with Zeno

Vacationing in Italy, you wander into the coastal village of Velia, a few hours south of Naples. On the edge of town you notice an archaeological dig. When you go to have a look at the ruins, you learn that the place now called Velia was once the Greek settlement of Elea, home to the philosopher Parmenides and his disciple Zeno. You stroll through the excavated baths and trace the city walls, then climb a steep, cobbled roadway to an arch called the Porta Rosa. Perhaps Zeno formulated his famous paradoxes while pacing these same stones 900,000 days ago. Was there something special about the terrain that led him to imagine arrows frozen in flight and runners who go halfway, then half the remaining half, but never get to the finish line?

That night, Zeno visits you in a dream. He brings along a sack of ancient coins, which come in denominations of 1, 1/2, 1/4, 1/8, 1/16, and so on. Evidently the Eleatic currency had no smallest unit: For every coin of value 1/2 ^{n }, there is another of value 1/2 ^{n+ 1 }. Zeno's bag holds exactly one coin of each denomination.

He teaches you a gambling game. First the coin of value 1 is set aside; it belongs to neither of you but will be flipped to decide the outcome of each round of play. Now the remaining coins are divided in such a way that each of you has a total initial stake of exactly 1/2. The distinctively Eleatic part of the game is the rule for setting the amount of the wager. Before each coin toss, you and Zeno each count your current holdings, and the bet is one-half of the lesser of these two amounts. Thus the first wager is 1/4. Suppose you win that toss. After the bet is paid, you have 3/4, and Zeno's fortune is reduced to 1/4; the amount of the next bet is therefore 1/8. Say Zeno wins this time; then the score stands at 5/8 for you and 3/8 for him, and the next amount at stake is 3/16. If Zeno wins again, he takes the lead, 9/16 to 7/16.

In the morning you wake up wondering about this curious game. What is the likely outcome if you continue playing indefinitely? Is one player sure to win eventually, or could the lead be traded back and forth forever?

EMAIL TO A FRIEND :