1
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Dec 29, 2015 at 18:43
  • $\begingroup$ Unless I'm missing something, net distance is total displacement, which, in my example, has an expected value of 0, not root N. $\endgroup$
    – spacediver
    Dec 29, 2015 at 19:36
  • $\begingroup$ It's going to be extremely difficult for a nonnegative random variable to have zero expectation! $\endgroup$
    – whuber
    Dec 29, 2015 at 21:45
  • $\begingroup$ But net displacement can be either positive or negative. Why would it be non negative? $\endgroup$
    – spacediver
    Dec 29, 2015 at 21:47
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Dec 29, 2015 at 21:51

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – spacediver
    Aug 20, 2017 at 23:53
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.