# The random walk problem

1. Jan 23, 2014

### CAF123

1. The problem statement, all variables and given/known data
A drunk lurches from one lamp post to the next on his way home. At each lamp post he pauses and is equally likely move towards or away from home. Suppose the posts are separated by a distance $a$ and find the mean and standard deviation of his displacement $d$ from the starting point, after $N$ steps.

2. Relevant equations
Binomial distribution may be incorporated

3. The attempt at a solution
I assume that each step the drunk makes is of length $a$. He starts at some origin and then takes a total of N steps to reach a displacement d. Let $r$ be the number of steps to the right and let $\ell$ be the number of steps to the left. Then $r + \ell = N$. At a given post, the probability that the drunk moves right is 1/2 = probability that the drunk moves left. The probability of getting $r$ right steps is then binomially distributed;$$P(\text{r right steps}) = {N \choose r} p^r (1-p)^{N-r},$$ and since $p = 1/2$, this is the same as $${N \choose r} \frac{1}{2^N}$$ Similarly, $$P(\text{l left steps}) = {N \choose N-r} \frac{1}{2^N}$$ which is the same distribution.
I do not know how to proceed from here. I was also thinking that the expected value of displacement is given by the sum of all possible displacements multiplied by their corresponding probabilities, however, I am not sure how to obtain this in practice.

Many thanks.

2. Jan 23, 2014

### Dick

Your 'right steps' and 'left steps' distributions are counting the same thing. Just use one of them. If you take r steps right (and N-r left) where do you wind up?

3. Jan 23, 2014

### CAF123

Hi Dick,
This depends on the combination of right and left steps. The displacement is given by $ka$ where $k$ is an integer. If there are no left steps, then $k = r = N$.

4. Jan 23, 2014

### Ray Vickson

You seem to be missing the point: given N and r, what is the displacement X? You need to figure this out because you are being asked to find the mean and standard deviation of X.

5. Jan 23, 2014

### CAF123

I see, so then $X = ra - \ell a = ra - (N-r)a$. To obtain the mean it is a case of solving the equation $X_{avg} = 2r_{avg} a - Na$. I can see where this method is going and in fact I have already solved it this way. I was wondering if there was a way of solving this explicitly with the distributions I have derived or via conditional probabilities.

6. Jan 23, 2014

### Staff: Mentor

To find the mean, you can simply use the symmetry of the problem. The standard deviation is more interesting.
You can find ravg with the distributions. I don't see where conditional probabilities would occur, as all steps are independent.

7. Jan 23, 2014

### CAF123

Since the drunk is equally likely to go backwards or forwards at each post, the mean should be zero.
$r_{avg}$ is the expected number of right steps. This is just an expectation of a binomial distribution (regard each step as a trial and moving to the right an event - at each post the probability of the event is 1/2).

E[right steps] = r(1/2) + (N-r)(1/2) = N/2. How would I show this using my distributions?

I also want to try to use the explicit expression for the expectation that is $E[X] = \sum_i i P_i$, where $i$ is a possible displacement and $P_i$ is the probability of that displacement. The summation would be over the entire sample space which is all possible displacements. Is it possible to find such a form?
I did see a method in my examples class, but the page was full with conditional probabilities that I preferred to focus on my own method. I think he was conditioning on the fact that we start at, say, $x_o = 0$ and then considered for example P(X=xo+a|xo=0).

8. Jan 23, 2014

### Staff: Mentor

Right.

That is the easy way, indeed. You can calculate the probability of every r from 0 to N and then calculate the expectation value based on the distribution. I don't see a reason for that, but you can do it.

See above, that is nearly the same (just split it in odd and even i to make it easier).

Ah well... that is more complicated than necessary.