The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Expected Number of Plays to End the Game

Date: 06/19/2009 at 09:29:30
From: Ryan
Subject: What is the Expected Number of Flips This Game Would Take

Bob and Kyle each have $18.  They flip a fair coin repeatedly.  If the
coin comes up tails, Bob pays Kyle $1.  If the coin comes up heads,
Kyle pays Bob $1.  The game is finished when either one of them has no
money left.  What is the expected number of coin flips this game will

Date: 06/20/2009 at 04:30:04
From: Doctor Jacques
Subject: Re: What is the Expected Number of Flips This Game Would Take

Hi Ryan,

To make the problem more symmetrical, we may consider the gains and
losses with respect to the initial situation.  This means that we
assume that the players start with nothing, and the game lasts until
one of the players (say Bob) has "won" either 18 or -18.  To be a
little more general, we assume that the game ends when Bob has won
either -S or +S dollars (in this case, S = 18).

Bob's gain can be any integer between -S and +S.  At any given
instant, the state of the game is completely determined by Bob's gain,
because we assume that the coin flips are independent events.  (This 
is called a Marlov process).

We can therefore define (2S+1) variables x[n], with -S <= n <= +S.
x[n] represents the expected duration of the game when Bob has won n
dollars.  We are trying to compute x[0].

If Bob has n dollars, and n is not -S or +S, after the next flip, Bob
will have either n-1 or n+1 dollars, with equal probability.  This
means that one flip has occurred, and the remaining number of flips is
either x[n-1] or x[n+1], each with probability 1/2.  We may therefore

  x[n] = 1 + (x[n-1]+x[n+1])/2      [1]

and there is one such equation for each value of n between -S+1 and
+S-1, for a total of 2S-1.

Because the game ends when Bob has either -18 or +18, we have:

  x[-S] = x[S] = 0                   [2]

This gives two additional equations, for a total of 2S+1.  As we have
2S+1 unknowns, we could try to solve the corresponding linear system
of equations.  However, there is a shorter way to solve this.

Note that, by symmetry, we have:

  x[n] = x[-n]                       [3]

(You can check that these equations are compatible with [1] and [2])

We may write [1] as:

  -x[n-1] + 2x[n] -x[n+1] = 2
  (x[n+1] - x[n]) - (x[n] - x[n-1]) = -2
  d[n+1] - d[n] = -2                  [4]

where the d[n] are the first order differences:

  d[n] = x[n] - x[n-1]                [5]

[4] shows that the first differences are constant.  If you are
familiar with finite differences, you will recognize that this means
that x[n] is a quadratic function of n, and be able to find the
coefficients by using [2] and [3].  Otherwise, let us look at a step
by step derivation.

[4] shows that the d[n] constitute an arithmetic progression with
common difference -2, and we have therefore:

  d[n] = a - 2n                        [6]

for some constant a.  We have:

  x[n] = x[0] + d[1] + ... + d[n]
       = x[0] + SUM{k = 1..n}(d[k])    [7]

and, by using [6],

  x[n] = x[0] + SUM{k=1..n}(a-2n)
       = x[0] + na - n(n+1)             [8]

where we have used the formula for triangular numbers:

  SUM{k=1..n}(k) = 1 + 2 + .. + n = n(n+1)/2

Now, we may rewrite [8] as:

  x[n] = x[0] + (a-1)n - n^2            [9]

Because of [6], the coefficient of n (i.e., a-1) must be 0, and we can
use [2] to show that x[0] = S^2, which is the answer we are seeking.
Note that the general formula for x[n] becomes:

  x[n] = S^2 - n^2                     [10]

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum 
Associated Topics:
College Probability

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.