College Mathematics Journal, The: Coin ToGa: A coin-tossing game

Inspiration

For six decades, the Mathematical Association of America has sponsored the annual Putnam exam, challenging American and Canadian undergraduates to find novel solutions to imaginative mathematical questions. There are cash incentives for the highest-scoring individuals and teams, and it is perhaps with such mercenary motives in mind that the 1997 Putnam proposed this question:

Players 1, 2, 3, . . . , n are seated around a table and each has a single penny. Player 1 passes a penny to Player 2, who then passes two pennies to Player 3. Player 3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an infinite set of numbers for which some player ends up with all n pennies. [2]

We examine a similar problem with a probabilistic spin. Let n be a positive integer. Suppose that n people are randomly assigned seats at a round table. One of them is chosen (again at random) and called Player 1. Then the remaining participants are numbered clockwise 2, 3, . . . , n. Player 1 tosses a coin, not necessarily fair. If the coin comes up heads, then that player is out of the game. If it comes up tails, she stays in the game. Then Player 2 tosses the same coin, etc. After Player n's turn, the coin is passed clockwise to the next (remaining) player and the process continues. When n - 1 players have been eliminated, then only the winner remains and the game terminates.

Let p denote the probability that the coin comes up heads, and put q = 1 - p. If p = 0, then the game almost surely does not terminate. On the other hand, if p = 1, then the game almost surely terminates in n - 1 steps, with Player n declared the winner. Therefore, we will take 0

If p = 1/6, the probabilist might call this game "Russian roulette, with reloading." More generally, the game serves as a model for any simple process of successive elimination, from certain incarnations of the children's game of dodgeball to voting systems. We will analyze this game to determine the advantage of each seat position.

For brevity we will call this game Coin ToGa, for Coin Tossing Game. We begin by looking at games that are not well-populated (n = 2, 3). Then we discern some regular patterns by analyzing these special cases. Finally we derive a useful recursion for the general game with n players and will use it to prove various theorems.

As a referee suggested to us, Coin ToGa could be used in courses or in-service workshops dealing with experimental probability, or even at mathematical parties!

The 2- and 3-person games

In the following, X^sub j^ denotes the event that Player j wins. For n > or = 1, define the random variable A^sub n^ by A^sub n^ = j if Player j wins, j = 1, 2, . . . , n, and put P^sub n^(X^sub j^) = Pr(A^sub n^ = j), the probability that the winner of an n-person game is the jth player. The possibilities for a two-person game are shown in Figure 1.

The initial node (1 2) reflects the fact that both players are still in the game and that Player 1's turn is next, whereas the node label (2 1) shows that Player 2's turn is next at that step. Player 2 can win in 1 step (probability p), in 3 steps (probability q^sup 2^p), in 5 steps (probability q^sup 4^p), and so on. That is because terminal node (2) is reached by first traversing the graph's single loop (or cycle) some nonnegative integer number of times, then moving to the left. Therefore, the probability that Player 2 wins is P^sub 2^(X^sub 2^) = [summation operator]^sup [infinity]^^sub m=0^q^sup 2m^ p = p/(1 - q^sup 2^) = 1/(1 + q). It follows that P^sub 2^(X^sub 1^) = 1 - 1/(1 + q) = q/(1 + q)

Figure 2 depicts the three-person game. As before, each node shows the survivors at a particular moment. This tree contains cycles of length 2 and 3. Observe that the subtrees emanating from nodes (1 2), (2 3), and (3 1) are isomorphic.

Each node of the tree lists players in order by whose turn is next, second from next, etc. This has the advantage that each nonterminal node is uniquely determined by its labelling when n = 3, and it is always clear whose turn is next. As in the previous section, we will use the cycling properties of the tree to avoid needing an infinite sheet of paper.

We take care to identify two nodes based not only on the set of remaining players, e.g., {1, 2}, but also on whose turn is next. That is, we use ordered sets: node (12) [not =] node (21).

Consider Player 1. There are two terminal nodes (1) in Figure 2. The first is reached directly by tossing THH; the second, by tossing TTHTH. The accompanying probabilities are p^sup 2^q and p^sup 2^q^sup 3^. However, these account only for direct routes with no cycles. Player 1 can also win as a result of several 3-cycles followed by 2-cycles. Thus,

Compare the trees for n = 2, 3. It appears that the nth tree has exactly n! terminal nodes, with each player appearing an equal number of times among them. This can be proved inductively, but it will be clear anyway as a consequence of the proof of our recursion.

Some observations

By summarizing what we know so far, we will be able to see some patterns immediately. Proofs are deferred until later.

The 1-person game is straightforward, and we mention only for reference that P^sub 1^(X^sub 1^) = 1. The probabilities for the 2-person game are best viewed in unreduced form:

Based on these calculations, we make several observations.

Theorem 1. For n > or = 2, q P^sub n^(X^sub n^) = P^sub n^(X^sub 1^).

This is surprising; although Coin ToGa is a circular game and Players n and 1 are adjacent players, their probabilities of winning are quite closely related. The theorem implies that Player n is in a much better position to win than Player 1. That can be extended into a generalized order relation which constitutes the next theorem. As further motivation, Theorem 1 will be useful in the proof of Theorem 2.

Theorem 2. For fixed n > or = 1, P^sub n^(X^sub j^) is strictly monotone in j:

P^sub n^(X^sub n^) > P^sub n^(X^sub n-1^) > [middot][middot][middot] > P^sub n^(X^sub 1^).

That is, your chances of winning are better if your first turn comes later in the game. This corresponds to the intuition that the more players who are in front of you, the greater your chance of being the sole survivor. This should hold true even as the game enters the second round, third round, and so on. If we assign the players a ranking, Player 1 comes in last; hence the biblical quote that began this article.

It also appears that for fixed j > or = 1, P^sub n^(X^sub j^) is strictly monotone in n:

P^sub j^ (X^sub j^) > P^sub j+1^(X^sub j^) > P^sub j+2^ (X^sub j^) > [middot][middot][middot],

and so Player j's chances worsen each time the number of players increases. If true in general, this would be a useful lemma; it implies that lim^sub n[arrow right][infinity]^ P^sub n^(X^sub j^) exists. Fortunately, we will be able to prove an even stronger limit result (lim^sub n[arrow right][infinity]^ P^sub n^(X^sub j^) = 0) by other methods.

Excursion into number theory

It is interesting to observe that our next theorem relates a probability question to some well-known and deep objects in number theory-the modular forms and the cyclotomic polynomials.

Theorem 3.

(a) For n > or = 2,

where l = 1 if 1 3, R^sub n,j^(-1) = 0.

(b) R^sub n,j^(1/q) = q^sup -k^R^sub n,n-j+1^(q), where k = deg R^sub n,j^ is described explicitly below.

This looks remarkably like the two-function transformation law in the theory of modular forms! [See, for example, [3, p. 145, eq. (12)].] However, as R^sub n,j^ is neither periodic nor transcendental, it holds no obvious allure for the practical number theorist.

(d) The polynomial [function of]^sub s^ is always divisible by the cyclotomic polynomial [phi]^sub s^(q) = [Pi]^sub r^(q - [zeta]^sub r^), where this product runs through all primitive sth roots of unity [zeta]^sub r^; and in fact [function of]^sub s^ = [phi]^sub s^ whenever s is prime. For any positive integer s, a standard result states that [function of]^sub s^ factors into irreducibles, each of which is cyclotomic. Thus, we may write

We omit the tedious details of the proof of Theorem 3; we merely note that it can be proved directly using the recursion on R^sub n,j^ imposed by the one on P^sub n^(X^sub j^). We use R^sub n,j^ in the closing section to provide a simple proof of a probabilistic limit theorem.

The recursion

We will obtain the probabilities for the (N + 1)-person game in terms of the N-person game.

In Figure 3, the first subtree, which begins with node (2 3 4 [middot] [middot][middot] N + 1), is isomorphic to the tree for N players. That is, it is identical to the N-tree, except that we have to subtract 1 from each node entry. Thus, in this subtree, (j) occurs as a terminal node with probability pP^sub N^(X^sub j-1^)/(1 - q^sup N+1^), j > or = 2. The factor p occurs because we are conditioning on the event that the first coin toss (before getting to the subtree) is heads; the factor 1/(1 - q^sup N+1^) is necessary to account for the (N + 1)-length loops that are now possible.

The second subtree is similar. It begins with node (3 4 [middot][middot][middot] N + 1 1). To map this to the N-tree, which begins with node (1 2 3 [middot][middot][middot] N), we can subtract 2 from each node entry and then identify those entries mod (N + 1). If we make this identification, then (j) occurs as a terminal node in this subtree with probability qpP^sub N^(X^sub j-2^)/(1 - q^sup N+1^), j [not =] 2.

Now consider the third subtree. For j [not =] 3, (j) occurs as a terminal node in this subtree with probability q^sup 2^pP^sub N^(X^sub j-3^)/(1 - q^sup N+1^). For instance, (2) occurs in this subtree with probability q^sup 2^pP^sub N^(X^sub j-3^)/(1 - q^sup N+1^) = q^sup 2^pP^sub N^(X^sub N^)/(1 - q^sup N+1^), since again we interpret players mod(N + 1).

In the last, or (N + 1)st, subtree, Player j wins with probability q^sup N^pP^sub N^(X^sub j-N-1^), for any j [not =] N + 1. Sans the denominator 1 - q^sup N+1^, these terms are organized in Table 1.

We can calculate P^sub N+1^(X^sub 1^) by summing the probabilities of (1) appearing as a terminal node in all of the aforementioned N-subtrees:

for 1

If P^sub n^(X^sub i^)/P^sub n^(X^sub j^) is close to 1, then Players i and j have a nearly equal chance of winning; thus, Theorem 6 is concerned with the fairness of the game. If n players want to make the game more fair, they will choose a coin that is biased more heavily towards tails. As long as q > 1/2, a more biased coin actually results in a fairer game! However, there is a trade-off involved: the increased bias of the coin will lengthen the game, so that the perfectly fair game almost surely never terminates.

1 Note added in proof: it has recently come to the authors' attention that this game was studied by Blom et al., as "General Russian Roulette," Mathematics Magazine 69 (1996) #4.

References

1. Good News Bible, American Bible Society, New York, 1992.

2. Problem A-2, The Fifty-Eighth William Lowell Putnam Exam Mathematical Competition, 1997. Some solutions to this exercise can be found in Mathematics Magazine 71 (1998) 154-155, and American Mathematical Monthly 105 (1998) 74-79.

3. E. Hecke, Neuere Fortschritte in der Theorie der elliptischen Modulfunktionen, Comptes rendus du congres international des mathematiciens Oslo (1936) 140-156.

Osvaldo Marrero (Osvaldo.Marrero@villanova.edu) studied mathematics at the University of Miami, and biometry and statistics at Yale University. After holding various appointments in academia and in industry, he is now a Professor at Villanova University. He has published papers in epidemiology, mathematics, medicine, and statistics. Other interests include listening to music, physical exercises, and travel. He is fluent in English, French, and Spanish, and he continues to improve his knowledge of Dutch and German.

Paul C. Pasles (Paul.Pasles@villanova.edu) is Assistant Professor of Mathematical Sciences at Villanova University. He traces his ancestry to Chios, birthplace of Hippocrates (the Pythagorean, not the physician). Paul's first book, with new revelations on Dr. Franklin and his squares, is in progress.