Expected Number of Plays to End the GameDate: 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 last? 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 write: 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 http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/