Random Walk Coin Simulation
Date: 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. Note first that, because of the symmetry of the problem, we have: y[k] = y[-k]  If x = n or x = -n, the game is over, and we have therefore: y[n] = y[-n] = 0  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]  In the same way, if you get a tail, you have: y[k;tail] = 1 + y[k-1]  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  You could write all the equations  for k between -n+1 and n-1, together with the two equations . 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. Although this does work, there is a nice shortcut available. We define: d[k] = y[k-1] - y[k]  so that d[k] is the difference between consecutive values of y. Note that, because of , we have: d = y - y = 1  We can also rewrite  as: (y[k] - y[k+1]) - (y[k-1] - y[k]) = 2 d[k+1] = d[k] + 2  Because of the symmetry, we only need to consider the equation  and equations  for k > 0. These equations show that the d's are just the odd integers: d = 1 d = 1 + 2 = 3 d = 3 + 2 = 5 .... d[k] = 2k-1  It is easy to prove by induction that: 1 + 3 + ... + 2k-1 = k^2  and, therefore: d + ... + d[k] = k^2  On the other hand, if you add together the equations , the intermediate y[k] terms cancel out, and you have: d + ... + d[k] = y - y[k] which means, because of , that: y[k] = y - k^2  Because of , if we let k = n, we see that we must have y = 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:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.