3.6 - Proving Average Squared Difference (Optional)

What is the value of the average square displacement of a random walker after N steps? Here we show two ways to calculate this average square displacement.

### First Method: Average Square Displacement from Pascal's Triangle

Look at Pascal's Triangle, Figure 3.7.

Pick out the row of circles representing displacements after two steps. A total of 4 paths are available for entering this row (the denominator of the average in the equation below). Two paths lead to zero displacement, one path leads to a displacement +2, and one path leads to a displacement -2. Each of these paths is equally likely. In taking the average of the squares (numerator of the equation below), there is one entry for (-2)2 = 4, two entries for (0)2 = 0, and one entry for (+2)2. Therefore the average of the square for two steps is:
 1(-2)2+2(0)2+1(+2)2 4 = 8 4 = 2.
Now calculate the average of the squares of the displacements after three steps. A total of 8 paths are available for entering this row. Three paths lead to +1 final displacement. Three paths lead to -1 final displacement. One path leads to +3 and one path to -3 displacement. Follow the same steps as above to calculate the average of the squares of the displacements after three steps:
 1(-3)2+3(-1)2+3(+1)2+1(+3)2 8 = 24 8 = 3.
Show that for the row representing displacement after four steps the average of the squares of the displacements is 4. What is the average of the squares of the displacements after five steps?

Do you see a pattern? The average of the squares of the final displacements is equal to the number of steps. A graph of the ideal mean square displacement vs. the number of steps is simply a straight line.

### Second method: Calculating the Average Square Displacement using Algebra

Notation: Scientists often use the symbol x to represent displacement along a line, x2 to represent the square of this displacement, a subscript N to represent "after N steps,'' and a bracket á ñ to represent average value. Then our argument from Pascal's triangle is that:
 (average of the squared displacements after N steps) = number of steps N,
which is written (xN)2 = N.
We already obtained this result using Pascal's Triangle. Next we calculate the same answer using algebra.

Suppose the walker has taken n steps and is now at position xn. What do we expect the value of (xn)2 to be? Start by asking where the walker will be at the next step n+1. If we know where the walker is now (i.e., xn) then after the next step the walker can be a step to the right or a step to the left; either at
 xn+1 = xn + 1      (step right)
(1)
or at
 xn+1 = xn - 1      (step left).
(2)
Which of these will it be? We cannot say for sure. In a random walk both are equally likely. So we take an average: Square both sides of Eqs. (1) and (2) and take the average of the two. Again, use the  bracket to mean average value. Then (xn+1)2 = (xn+1)2+(xn-1)2 2 = xn2+2xn+1+xn2-2xn+1 2 ,
or (xn+1)2 = 2 (xn)2 +2 2 ,
or (xn+1)2 = (xn)2 +1.
(3)
What does this equation mean? Start with n = 0, the zeroth step (or no step at all). Then (x0)2 = 0. For the first step, Eq. 3 tells us that (x1)2 = (x0)2 +1 = 0+1 = 1, which we knew already without doing this calculation. From this, it follows that (x2)2 = (x1)2 +1 = 1+1 = 2 and (x3)2 = 3 and, in general (xN)2 = N. The result? The average squared displacement after N steps is simply N: (xN)2 = N.
This is the same result we obtained from studying Pascal's Triangle.

What we stated above is an ideal average, i.e., an average we would also obtain over an infinite number of trials. For a finite number of trials, for example the average of 250 walkers, this is our "best guess'' of the final squared displacement after N random steps along a line. In general, observed values approach the "best guess'' for a very large number of trials.

Next: 3.7 - The Wandering Ant on a Square Grid