On a Problem of Ross by P.J. Fitzsimmons

January 6, 2010

S. M. Ross studies the following game in [1]: “Consider a gambler’s ruin problem involving r players, with player i initially having n_{i} units, n_{i} > 0, i = 1, …, r. At each stage, two of the players are chosen to play a game, with the winner of the game receiving 1 unit from the loser. Any player whose fortune drops to 0 is eliminated, and this continues until a single player has all n ≡ ∑_{i=1}^{r} n_{i} units, with that player designated as victor. Assuming that the results of successive games are independent and that each game is equally likely to be won by either of its two players, among other results we find

(a) the probability that player i is the victor;

(b) the expected number of stages until one of the players has all the money;

(c) the expected number of games played between two specified players. Moreover, we show that none of the preceding quanties depend on the rule for choosing the players in each stage.”

In this note we provide an alternative approach to that taken by Ross, using certain martingales associated with the game in a way that naturally extends a familiar approach in the two-player case.

For i = 1, …, r, let F_{i}(t) be the fortune of player i after game t is played, and let I_{i}(t) be the indicator of the event that player i participates in game t. Let F = {F_{t}; t = 0, 1, 2, …} be the filtration determined by

F_{t} := σ{F_{i}(s), I_{i}(s) : i = 1, 2, …, r, s = 1, 2, … t},

and define

p_{i}(t) := E[I_{i}(t + 1)|F_{t}], p_{ij}(t) := E[I_{i}(t + 1)I_{j}(t + 1)|F_{t}].

It is then a simple matter to check that each of the processes

(1)  F_{i}(t),  t = 0, 1, 2, …,

(2)  F_{i}(t)F_{j}(t) + ∑_{s=0}^{t−1} p_{ij}(s),  t = 0, 1, 2, …, i ≠ j,

and

(3)  F_{i}(t)^{2} − ∑_{s=0}^{t−1} p_{i}(s),  t = 0, 1, 2, …,

is a martingale. Let us now apply the optional stopping theorem at the stopping time T, defined to be the first time one player has all the money. The martingales in (1) are bounded, so we obtain immediately

(4)  n_{i} = E[F_{i}(0)] = E[F_{i}(T)] = nP[V_{i}],  i = 1, 2, …, r,

where V_{i} is the event that player i is the victor. Thus,

(5)  P[V_{i}] = \frac{n_{i}}{n} ,  i = 1, 2, … r.

Applying optional stopping to the martingales in (2) at the bounded stopping times T ∧ k (for integer k) we obtain (for i ≠ j)

(6)  E[F_{i}(T ∧ k)F_{j}(T ∧ k)] + E [ ∑_{s=0}^{T ∧k−1} p_{ij}(s)] = n_{i}n_{j}.

Now send k off to +∞ in (6), using dominated convergence on the first term on the left side and monotone convergence on the second, to obtain

(7)  E[F_{i}(T)F_{j}(T)] + E [∑_{s=0}^{T −1} p_{ij}(s)] = n_{i}n_{j}.

Clearly F_{i}(T)F_{j}(T) = 0, while

E [∑_{s=0}^{T −1} p_{ij}(s)] = E [∑_{s=0}^{T −1} I_{i}(s + 1)I_{j}(s + 1)] = E[N_{ij}],

where N_{ij} is the number of games in which players i and j compete against each other. Thus,

(8)  E[N_{ij}] = n_{i}n_{j},  i ≠ j.

The same truncation of T leads to

(9)  E[F_{i}(T)^{2}] = E [∑_{s=0}^{T −1} p_{i}(s)] + n_{i}^{2},

which in combination with (5) yields

(10)  \frac{n_{i}}{n} n^{2} = E[N_{i}] + n_{i}^{2},

with N_{i} the number of games in which player i participates. Thus

(11)  E[N_{i}] = n_{i}(n − n_{i}),  i = 1, 2, …, r.

Summing on i in (11) we obtain

(12)  2E[T] = n^{2} − ∑_{i=1}^{r} n_{i}^{2}.

Reference

[1] Ross, S.M.: A simple solution to a multiple player gambler’s ruin problem. Amer. Math. Monthly 116 (2009) 77–81.