# Drunken Walk

1. Oct 4, 2004

### Nexus[Free-DC]

There's an old problem concerning an old drunken person who is so sloshed he can't walk properly: he's got a 50/50 chance of stepping a metre forwards; otherwise he moves a metre backwards. It can be shown that he winds up where he started infinitely many times and that his average displacement from the origin is zero.

Let's say that his displacement from the origin is positive in the forward direction and negative in the backwards direction.

Now suppose we put a wall at the origin so that he can't move into the negative area. If he's at zero and tries to move backwards he just stays where he is. What then is his average displacement? I have a feeling it's a positive constant but have no idea how to go about showing that. Does anyone have any ideas?

2. Oct 4, 2004

### chroot

Staff Emeritus
I have a feeling the average displacement is unbounded and tends to infinity, but I'm not sure how to prove it. I'm looking into how I might conduct such a proof. A simple, non-proof sort of argument is this one:

In the normal 1D walk, the line is bounded on each end by $-\infty$ and $\infty$, which have the properties you'd like to give to your wall. An attempt to move past infinity leaves you at infinity, for example. (Does the fact that infinity is not number conflict with this use?)

The average displacement for a normal 1D walk is exactly halfway between its boundaries, negative and positive infinity: zero. (Is this a mathematically sensible statement?)

Your modified 1D walk has boundaries at 0 and positive infinity. Its average displacement is also halfway between its boundaries. Halfway between zero and positive infinity is actually infinity, too, so the average displacement is infinity. In other words, it has no average displacement.

I think I'm on the right track, but I'm sure someone with more mathematical skill can answer with more rigor.

- Warren

3. Oct 4, 2004

### Gonzolo

I am quite positive that the random walk problem leads directly to a gaussian distribution, so gaussian statistics might help. You might want to find the x-position where the area under the curve is the same on either side. It might not be what you're looking for, but it might be related.

4. Oct 4, 2004

### chroot

Staff Emeritus
Gonzolo,

This is not a 1D random walk, it's a modified 1D random walk -- so it no longer needs to lead directly to a gaussian distribution. I'm quite sure the average displacement is undefined (or infinite, if you'd prefer).

- Warren

5. Oct 4, 2004

### Gonzolo

Just adding input. Is the number of steps N finite or infinite?

6. Oct 4, 2004

### chroot

Staff Emeritus
I assumed by "average displacement" you meant the limit the average displacement tends to in an infinite random walk.

- Warren

7. Oct 4, 2004

### Gonzolo

It might be possible to show a relation between the average position and N, and then indeed prove where this position tends to when N tends toward infinity.

8. Oct 4, 2004

### Gokul43201

Staff Emeritus
The problem is not well defined. What is meant by "average displacement" ?

Edit: IGNORE THE FOLLOWING. I MISREAD THE ORIGINAL QUESTION. SORRY

All this models is a "counter" which, every second adds to itself 0 or 1 with equal probability. The value of the counter will approximate a linear funtion of time with slope 0.5 sec^{-1}.

Last edited: Oct 4, 2004
9. Oct 4, 2004

### chroot

Staff Emeritus
Does it? I don't see how that is possible.

-Warren

10. Oct 4, 2004

### CRGreathouse

This would be true only if the wall moved behind the person.

11. Oct 4, 2004

### Gokul43201

Staff Emeritus
That's what I thought I read. My bad...completely ignore my previous post.

Sorry

Last edited: Oct 4, 2004
12. Oct 4, 2004

### Janitor

This may not help, but I can remember reading in Scientific American decades ago about a connection between the drunkard's walk (or random walk--don't know if there is a distinction between the two) and Laplace's equation. Can't remember details.

13. Oct 5, 2004

### Gokul43201

Staff Emeritus
You sure that was Laplace and not Poisson ?

14. Oct 5, 2004

### Wong

In fact, "putting a barrier" at zero is equivalent to asserting that the probability of going to the right equals one when the person is at the origin and 1/2 otherwise. With a little bit of work one is able to show that the probaility that the person is at k after n steps is $$2*C_{\frac{n-k}{2}}^{n}(\frac{1}{2})^{n}$$. With this one may obtain the mean displacement at the nth step.

In fact the answer is the same as E[|N|] where "E" denotes expectation and N is the random variable denoting the displacement at the nth step and "|...|" is absolute value, and the expectation is taken with respect to the probability measure of the usual random walk.

Last edited: Oct 5, 2004
15. Oct 5, 2004

### Janitor

I'm not at all sure. Too many brain cells have died since I read the article. Of course, Laplace's equation is a special case (homogeneous) of the Poisson equation.

16. Oct 5, 2004

### Gokul43201

Staff Emeritus
I was thinking more of the Poisson distribution rather than the equation for the potential due to a charge distribution. Now I'm confused ?? Never mind...I believe Wong has the right way to go about it.

17. Oct 5, 2004

### Janitor

I was not thinking of the Poisson distribution, but of the partial differential equation. This weekend I'll take a shovel to a pile of old magazines I have and see if I happened to buy that particular issue.

18. Oct 6, 2004

### uart

I haven't come across the modified drunken walk with the wall as in this problem before. For the basic drunken (random) walk without the wall however it's pretty easy to show that the mean squared displacement after n steps is equal to n.

While I cant figure out how to tackle the modified problem I can show that the mean squared displacement is greater than that of the basic random walk.

For the basic random walk the mean displacement is zero by symmetry and the mean squared displacement is E(x^2), where x_n = Sum (k=1..n, u_k) and u_k is a random vector in which each element has a 50% probability of being +1 and a 50% probability of being -1.

So E(x^2) = E( Sum( k=1..n, u_k)^2 ), but since E(u_j u_k)=0 for any j<>k then E(x^2) is simply,

E( Sum(k=1..n, u_k )^2 ) = Sum(k=1..n, E( (u_k)^2 ) = n

For the case of the modified random walk then the step probabilty of the kth step, u_k, will be asymmetrical, with somewhat high probabilty of going forward than backwards, and the mean of the u_j times u_k terms will not cancel as above. I think this leads to E(u_j u_k) > 0 and consequently a mean sqaure displacement that is greater than that of the unmodified case.

Last edited: Oct 6, 2004
19. Oct 6, 2004

### Wong

The modified drunken walk with a wall at the origin is in fact equivalent to the "absolute" random walk, {|N|}, where N is the random displacement at the nth step.

20. Oct 6, 2004

### uart

So this would be like a "full wave rectified" drunken walk so to speak. :) Interesting, when I first read this problem I was wondering if that might be the case.

So E(|x|^2) = E(x^2) and the mean sqaured value of the modified drunken walk should actually be the same as that of the unmodified drunken walk, is that correct Wong? I'd kind of convinced myself that the mean square value of the modified walk would be greater but maybe I was mistaken.