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[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/