Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search