A Drunkard's Walk: Proving Positive Average Displacement

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

 

[chroot]

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

 

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

 

[chroot]

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

 

[Gonzolo]

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

 

[chroot]

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

- Warren

 

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

 

[Gokul43201]

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}.

 

[chroot]

All this models is a "counter" which, every second adds to itself 0 or 1 with equal probability.

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

-Warren

 

[CRGreathouse]

All this models is a "counter" which, every second adds to itself 0 or 1 with equal probability.

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

 

[Gokul43201]

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

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

Sorry

 

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

 

[Gokul43201]

You sure that was Laplace and not Poisson ?

 

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

 

[Janitor]

You sure that was Laplace and not Poisson ?

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.

 

[Gokul43201]

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.

 

[Janitor]

I was thinking more of the Poisson distribution rather than the equation for the potential due to a charge distribution. Now I'm confused ...

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.

 

[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 can't 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.

 

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

 

[uart]

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.

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.

 

[shmoe]

Let f(n,k)=total number of walks of length n that have displacement k
Then f(n,0)=f(n-1,0)+f(n-1,1). If k>0 we also have f(n,k)=f(n-1,k-1)+f(n-1,k+1).

Let E(n)=average displacement after n steps, so we have

$$E(n)=(\sum\limits_{k=0}^{n}k*f(n,k))/2^n$$

We can relate this back to E(n-1) by the above,

$$E(n)=(\sum\limits_{k=1}^{n}k*(f(n-1,k-1)+f(n-1,k+1)))/2^n=(\sum\limits_{k=1}^{n}k*f(n-1,k-1))/2^n+(\sum\limits_{k=1}^{n}k*f(n-1,k+1))/2^n$$
$$=f(n-1,0)/2^n+(\sum\limits_{k=1}^{n-1}(k+1)*f(n-1,k))/2^n+\sum\limits_{k=2}^{n-1}(k-1)*f(n-1,k))/2^n$$

Since f(n-1,n)=f(n-1,n+1)=0. Combining sums, we get:

$$f(n-1,0)/2^n+2*f(n-1,1)/2^n+(\sum\limits_{k=2}^{n-1}2k*f(n-1,k))/2^n=f(n-1,0)/2^n+(\sum\limits_{k=1}^{n-1}k*f(n-1,k))/2^{n-1}$$

Since 0*f(n-1,0)=0, we get:

$$E(n)=f(n-1,0)/2^n+E(n-1)$$

To show E(n) goes to infinity as n does, it's therefore enough to show sum f(0,0)/2^1+f(1,0)/2^2+f(2,0)/2^3+... diverges.

Now we just need to work out f(n-1,0) and we're getting somewhere. I'm pretty confidant that $$f(n,0)=C^{n}_{floor(n/2)}$$, but so far I haven't been able to come up with a combinatorial proof of this. They match for the first 200 entries if my computations are correct.

We can look at the long term behavior of f(n-1,0)/2^n. If my formula for f(n,0) is correct, and ignoring the floor part (when n is very large, this won't matter much, and of course not at all when n is even), we get

$$f(n-1,0)/2^n=\frac{(n-1)!}{((n-1)/2)!^{2}2^n}\sim\frac{e^{-n}n^{n-1/2}(2\pi)^{1/2}}{e^{-n-1}((n+1)/2)^{n}(2\pi)2^n}$$, by Stirling. This is asymptotic to $$\frac{1}{(2\pi n)^{1/2}}$$ and is therefore a divergent series. So E(n) goes to infinity as n does, and itshould be asymptotic to $$(\frac{2n}{\pi})^{1/2}$$

 

[robert Ihnot]

Very nice work Shmoe. I think I can understand why it goes to infinity now. I had been totally mystified. You did say that you had no proof of $$f(n,0)=C^{n}_{floor(n/2)}$$.
I think I may be able to supply that, if I really got it straight.

Also, by your inequality: $$E(n)=f(n-1,0)/2^n+E(n-1)$$ we need only consider the infinite subset containg elements of even or odd order since we have: E(2n+1)>E(2n)>E(2n-1)>E(2n-2)>...This is a nice simplification.

Let us then consider a "truth table" series of Xs and 1s, that is an orderly array containing 2n elements, r of which are X and 2n-r of which are 1. These are then arranged in binominal series: 2nC0, 2nC1...2nC2n since of the 2n elements giving us 2n! arrangements, r are the same and 2n-r are the same giving us (2n!)/(r!(2n-r)!) ways of arranging this array.

In this case we have the rule that we never walk backward if we are at the wall, so that at that position adding another X leaves us where we are. But the 1s always accumulate and the steps can be "knocked back" by adding on a X. That is, k+X = k-1, unless k=0 and then 0+X = 0. Examples: XX11=2, X1X1=1.

The insight we need is that we check along the lines of the array to see if the 1s predominate along the line to the right from some certain point, say if we are dealing with 14C7, in the line: 11XX11XXX1XX11=2, when we read up to (XXX)1XX11 we see that now we are going to have more 1s than Xs remaining and so since the 1s accumulate, the Xs are unable to make the line equal 0. (The nice part about this is that we really don't care if the arrangement is ...1XX11=2, or ...1X1X1=1, we just know the sum is not zero.)

Thus as we look at the binominal series: 2nC0, 2nC1...2nCn...2nC2n, we see that no sums are going to add to a zero prior to the middle term: 2nCn because it is first time the Xs are as great as the 1s.

It might be said that in this particular case, 2nCn, for the 0s we are looking at a Catalan number which can be interpreted as a voting situation where one side is never behind in the count. Why? Because if the Xs predominate, even from the very first: X... then looking down the line past that first X, we see there will be more 1s coming up than Xs and so the sum will not be 0. I mention the reference: http://en.wikipedia.org/wiki/Catalan_number and refer you to the counting argument of D Andre.

Looking at the counting argument of D Andre in more detail: In the case of 6N3 where we have the line X1X1X1=1 looking past the first X, which means the sum will be 1 or more, we reverse the remaining elements producing: XX1X1X. This is an element from the set: 6N4. Now any element is the set 6N4 will always have an excess of Xs and past the first time it occurs, which is at the X, we reverse all the elements following and get the number X1X1X1=1. Thus every element from 6N4 can be "reversed" and transformed into an element in the set 6N3, which sums to 1 or more. Two examples from the set 6N4 are: XXXX11 and 11XXXX, these "reverse" and give X111XX=1, and 11XXX1=1.

Thus the counting argument says that the number of 0 sums in the array of $$\frac{2n!}{n!n!}$$ elements containing nXs and n1s is
$$[ \frac{2n!}{n!n!}-\frac{2n!}{(n+1)!(n-1)!}]$$

When we move along to the term 2nC(n+1), where the Xs predominate, to get at the 1s that will come out of the array, we have to go past the first two Xs that predominates and add one more of them giving three excess, the 1s will then predominate on the line, and the reasoning is the same as before giving the 0s as 2nC(n+1)-2nC(n+2). For example: XXXX11 is transformed into XXX1XX. Note too, that we do not care if instead of XXXX11=2, we had the case to handle of XXX11X=1, which transforms into XXXXX1, another member of the same set, namely: 2nC(n+2). Also, cases like 11XXXX =0, never present us with three excessive Xs, so they are not eligable to be transformed, which is correct since the value is 0. Going in reverse we look at the case of X1XXXX, transforming into X1XXX1=1. Or for that matter, we could have looked at XXXXX1, transforming into XXX11X=1.

When we reach 2nC(2n-1), we can continue the argument above or clearly see that only one 1 is present in each line of the array, and so only XXXXX...XX1=1. This is again the same form: 2nC(2n-1) - 2nC2n. At the final case 2nC2n, there is only Xs and so there is only one arrangement and in this case we have 2nC2n =1.

Stringing everything together we get [2nCn-2nC(n+1]+[2nC(n+1)-2nC(n+2)]+++[2nC(2n-1)-2nC2n] + 2nC2n =2nCn, which is exactly what Schmoe conjectured.