Random Walk Coin SimulationDate: 10/27/2005 at 11:56:04 From: Ravi Subject: Probability "Random walk" I start at x = 0 and flip a coin, then carry out one of the following actions: If coin lands with tails: x = x - 1 If coin lands with heads: x = x + 1 I continue to flip the coin until I reach x = +n or x = -n. Is there a way to calculate how many times I will have to toss the coin? If yes, please suggest the way. I tried applying probability and can prove that since p(head) = p(tail) = 0.5 the probability of reaching +n/-n is also = 0.5. I know that the answer to this question is n squared, but I have not been able to reason out the solution. Regards, Ravi Date: 10/28/2005 at 04:45:51 From: Doctor Jacques Subject: Re: Probability Hi Ravi, Here is the outline of a way to find the solution; I will let you fill in the missing steps. I assume that you want to know the average number of steps required-- there is no maximum number of steps; indeed, if you are out of luck, you could get alternately heads and tails infinitely often and the game would never end. We let y[k] be the average number of steps required to end the game when x = k (we are interested in values of k between -n and +n). As we start with x = 0, we must find y[0]. Note first that, because of the symmetry of the problem, we have: y[k] = y[-k] [1] If x = n or x = -n, the game is over, and we have therefore: y[n] = y[-n] = 0 [2] Assume now that -n < x < n; we have to toss the coin at least once more. If we get a head, x will become x + 1, and there will be, on the average, y[k+1] moves remaining after this move (this is the definition of y[k]). If you take into account the next move, this means that, if you get a head, the total number of moves left is: y[k;head] = 1 + y[k+1] [3] In the same way, if you get a tail, you have: y[k;tail] = 1 + y[k-1] [4] Each of these two cases can happen with probability 1/2; this means that y[k] is the average of the above two values: y[k] = 1/2(1 + y[k+1]) + 1/2(1 + y[k-1]) and this can be written as: 2*y[k] - y[k+1] - y[k-1] = 2 [5] You could write all the equations [5] for k between -n+1 and n-1, together with the two equations [2]. This would give you a system of (2n+1) linear equations in the (2n+1) unknowns y[-n] ... y[n]. You could solve that system to find y[0]. Although this does work, there is a nice shortcut available. We define: d[k] = y[k-1] - y[k] [6] so that d[k] is the difference between consecutive values of y. Note that, because of [1], we have: d[1] = y[0] - y[1] = 1 [7] We can also rewrite [5] as: (y[k] - y[k+1]) - (y[k-1] - y[k]) = 2 d[k+1] = d[k] + 2 [8] Because of the symmetry, we only need to consider the equation [7] and equations [8] for k > 0. These equations show that the d's are just the odd integers: d[1] = 1 d[2] = 1 + 2 = 3 d[3] = 3 + 2 = 5 .... d[k] = 2k-1 [9] It is easy to prove by induction that: 1 + 3 + ... + 2k-1 = k^2 [10] and, therefore: d[1] + ... + d[k] = k^2 [11] On the other hand, if you add together the equations [6], the intermediate y[k] terms cancel out, and you have: d[1] + ... + d[k] = y[0] - y[k] which means, because of [11], that: y[k] = y[0] - k^2 [12] Because of [2], if we let k = n, we see that we must have y[0] = n^2, which is the result we are looking for. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - 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- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/