1

I was just introduced to the concept of a random walk while reading the Feynman lectures on physics, Volume 1. There was something in the explanation there that confused me, so I tried looking online for other explanations, and encountered the same difficulty.

I'm trying to understand how on earth the expected distance traveled could ever be the square root of the number of steps.

Here's my thinking process. I'm curious where I'm going wrong.

Suppose you start at 0, and at each step, either go forward (+1), or backward (-1), with equal probability. Suppose that you do 100 steps. Let us call X the number where you end up.

I can see how if you were to repeat this experiment many many times, the mean value of X would be 0.

But this is not interesting. What is interesting is the total distance moved, not the final displacement.

Well, it's as obvious as pie that that total distance moved is simply 100!

This is because the distance moved with each step is the absolute value of the incremental displacement at each step, which, in our example, is 1. So the total distance moved is 1 multipled by the number of steps, which is 100.

Now all the guides I've read say that using the absolute value is computationally tricky/impossible/inefficient, so it's better to first square the individual displacements, and then square root them at the end. But the problem with this is that you end up with something completely different. In our example, you'd end up with a value of 10, which is clearly incorrect if what you are interested in is the total distance traveled.

So, if we define the root mean squared distance as "the square root of the expected total distance traveled", that is fine and consistent. But to say that the root mean squared value is the expected total distance traveled seems nonsensical to me.

Yet we have statements that appear to say just that.

For example:

Since sqrt(d2) is something like the average positive distance away from 0 after N steps (technically, it's called the "root-mean-squared" distance), we expect that after N steps, the black dot will be roughly sqrt(N) steps away from where it started. So for 25 steps, we expect the black dot to have moved roughly 5 total spaces from 0 in either direction. Of course sometimes it will move more and sometimes fewer total spaces, but 5 is roughly what we might expect.

taken from http://www.mit.edu/~kardar/teaching/projects/chemotaxis(AndreaSchmidt)/random.htm

The second thing that confuses me is that this is portrayed as some sort of probabilistic function. According to my thinking descibed above (which may be woefully misguided!) both the total distance and the square root of the total distance will be exactly N and square root of N, each and every time, in the case where the magnitude of each incremental displacement is always the same (i.e. "1" in this example). So why even frame this as an expected value. How on earth could the total distance traveled be anything but N x |stepsize|?

spacediver
  • 73
  • 1
  • 8
  • Your argument should make it obvious that the "distance" in "expected distance" must refer to the *net* distance: that is, the distance between the position at time $N$ and the initial position, regardless of what path was taken to arrive there. – whuber Dec 29 '15 at 18:43
  • Unless I'm missing something, net distance is total displacement, which, in my example, has an expected value of 0, not root N. – spacediver Dec 29 '15 at 19:36
  • It's going to be extremely difficult for a nonnegative random variable to have zero expectation! – whuber Dec 29 '15 at 21:45
  • But net displacement can be either positive or negative. Why would it be non negative? – spacediver Dec 29 '15 at 21:47
  • The strongest reason perhaps is that when you do not adopt the interpretation I am suggesting, then none of the results makes sense, whereas when you interpret the net distance as an actual *distance* (which axiomatically is nonnegative) then all the stated results are true. – whuber Dec 29 '15 at 21:51
  • but isn't actual distance traveled simply N mutliplied by magnitude of step size, which would be 100 x 1 = 100, in my example? I'm not trying to be daft or difficult! – spacediver Dec 29 '15 at 22:10
  • If I travel from New York to London, the distance between my origin and destination is still 5700 km regardless of whether I went directly or stopped at Hong Kong and Santiago along the way. That's the entire (and rather trivial) point: we are talking about *distance between the start and the stop* (which is what is of physical interest), not about the distance along the path (which is the same for all paths after $N$ steps and therefore is uninteresting). – whuber Dec 29 '15 at 23:04
  • How is the distance between the start and stop different than the final net displacement? This is the key idea that I'm not grasping (and I do appreciate your patience here). – spacediver Dec 30 '15 at 02:27
  • I definitely know there's something wrong with my thinking, since when I simulate the random walk, the expected value of the absolute value of the net displacement is certainly not 0. Interestingly, neither is it root N. For example, when N is 25, the expected value seems to be around 3.87. Here's the Matlab code : [link](http://pastie.org/10659835) Now that I have a sandbox to work with, I'll see if I can resolve this paradox that exists inside my addled brain. – spacediver Dec 30 '15 at 04:24
  • Think I've figured it out. Also, Matlab code was faulty as it was taking modulus, rather than square. – spacediver Dec 30 '15 at 04:45
  • See discussions [here](http://stats.stackexchange.com/questions/159650/why-does-the-variance-of-the-random-walk-increase) and also [this post](http://stats.stackexchange.com/a/136879/805) – Glen_b Dec 30 '15 at 07:52

2 Answers2

1

The average "distance" is sqrt(n) in the topological sense, independent of direction. You drive a distance of 10 miles no matter what direction you drive (North, South, East or West). You correctly point out that given 100 steps the average distance from the origin will be 10 (above OR below the point of orgin) Rest assured that the average displacement (which may be either positive OR negative) is zero.

Gregg B
  • 11
  • 1
  • Thanks @Gregg B, yes, it's been a while since I tackled this issue, but I think that I was confusing the concept of distance and displacement in my discussion with Whuber. – spacediver Aug 20 '17 at 23:53
0

I think I've figured it out.

The key thing that was bugging me was this:

In the example I gave, consider tossing a fair coin to decide which direction to step for each of the 100 steps. The expected value of the number of heads would be 50.

But if there are 50 heads and 50 tails, that means that the net distance traveled would be 0.

However, it is a thinking error to assume that each of the experiments (a single experiment being a 100 coin toss random walk) will yield 50 heads. Rather, there will be a distribution, with 50 heads at the center of this distribution.

While the expected value of this distribution is 50, it is highly unlikely that all samples are going to be exactly 50. Rather, many of them will be merely in the vicinity of 50. The average deviation from 50, for any given sample, is determined by the spread of this distribution.

As we are squaring the the value of each experiment, these deviations do not cancel out.

spacediver
  • 73
  • 1
  • 8