Why is the expected average displacement of a random walk of N steps not $\sqrt N$?

Question

Let $D_N$ be the expected average of the displacement of a random walk on $\mathbb Z$ from the origin, where $N$ is the number of steps, each of which is either $-1$ or $1$.

We take the definition of the expected average of a variable $A$ to be $\sum_{i=1}^N a_ip_i$ where $A$ can take any value $a_1,a_2,\ldots,a_N$ with probability $p_1,p_2,\ldots,p_N$.

In one step, ${D_1}^2 = \frac121^2+\frac12(-1)^2=1$.

If we know $D_{N-1}$, then ${D_N}^2 = \frac12(D_{N-1}+1)^2 + \frac12(D_{N-1}-1)^2 = {D_{N-1}}^2 + 1$.

This means that ${D_N}^2 = N$ or $D_N = \sqrt N$.

However, if we look at the distribution of end paths after $N$ steps, we can represent the expected average $D_N = \frac{\binom{0}{N}d_1+\binom{1}{N}d_2 + \cdots + \binom{N}{N}d_N}{2^N}$ where $d_1,d_2,\ldots,d_{N}$ are the actual displacements from the origin.

ie:

$$D_1 = \frac{1}{2}\left[\binom011+\binom111\right] = 0.5 \\ D_2 = \frac{1}{4}\left[\binom022+\binom120+\binom222\right] = 1.0 \\ D_3 = \frac{1}{8}\left[\binom033+\binom131+\binom231+\binom333\right] = 1.5 \\ \vdots$$

All of which are different from $\sqrt N$.

I know that $\sqrt N$ is really only an approximation of $D_N$ and not an exact value, so where does the proof that $D_N$ is equal to $\sqrt N$ go wrong?

Answer 1

These are the recursions for the mean squared distances and, of course, square roots of mean squared distances are not mean distances since, in general $E(D^2)\ne E(D)^2$. The recursions for the mean distances $E(D)$ are more complicated.

Edit: Let us try to separate clearly the different notions involved, considering the (random) position $X_N$ after $N$ steps and the (random) distance) $D_N=|X_N|$ after $N$ steps (this may not be what you mean by $D_N$ in the question but, precisely, the confusion here might stem from the fact that what you mean by $D_N$ is not quite clear...).

Then, on the one hand, $X_{N+1}=X_N+Z_{N+1}$ where $Z_{N+1}=\pm1$ is centered and independent of $X_N$ hence $X_{N+1}^2=X_N^2+2X_nZ_{N+1}+1$ yields $E(X_{N+1}^2)=E(X_N^2)+1$, thus, $E(X_N^2)=N$ for every $N$, that is, the square root of the mean squared distance after $N$ steps is exactly $\sqrt{N}$.

On the other hand, to express $D_{N+1}=|X_N+Z_{N+1}|$ in terms of $D_N$ is more involved since, for every integer $x\gt0$, $E(D_{N+1}\mid D_N=x)=\frac12(x+1)+\frac12(x-1)=x$, while $E(D_{N+1}\mid D_N=0)=1$. Thus, $$E(D_{N+1})=E(D_N)+P(D_N=0)=E(D_N)+P(X_N=0),$$ which, together with $E(D_1)=1$, leads to $$E(D_{2N+2})=E(D_{2N+1})=1+\sum_{k=1}^NP(X_{2k}=0)=\sum_{k=0}^N\frac1{2^{2k}}{2k\choose k}.$$ Stirling's approximation then yields $$\frac1{2^{2k}}{2k\choose k}\sim\frac1{\sqrt{\pi k}},$$ hence $$E(D_N)\sim\sqrt{\frac2\pi}\cdot\sqrt{N}.$$

To sum up, $\sqrt{E(D_N^2)}$ and $E(D_N)$ both scale as $\sqrt{N}$ when $N\to\infty$ but for some different prefactors, and exactly for $\sqrt{E(D_N^2)}$ but only asymptotically for $E(D_N)$.

Finally, the value of the pre-factor for $E(D_N)$ can be understood if one notes that, by the most basic version of the central limit theorem, $D_N/\sqrt{N}$ converges in distribution to $|G|$ where $G$ is standard normal and that $E(|G|)$ is indeed... $\sqrt{2/\pi}$. More generally, for every nonnegative $k$, when $N\to\infty$, $$E(D_N^k)\sim E(|G|^k)\cdot N^{k/2}.$$

Answer 2

In an arbitrary dimension d:

Let $\vec{R}$ be the end-to-end distance vector of a random walk of fixed step length $|\vec{r}_i| = l$. $\vec{R}$ can then be expressed as $\displaystyle \vec{R} = \sum_{i=1}^N \vec{r}_i$, where $\vec{r}_i$ is the vector of the $i$-th step. The Root-Mean-Square End-to-End Distance is given by $\textrm{RMS}=\sqrt { \langle R^2 \rangle }$. Since the steps are mutually independent, the covariance of two steps $\vec{r}_i$ and $\vec{r}_j$ is zero if $i\neq j$ and $\textrm{Cov}(\vec{r}_i, \ \vec{r}_j)= \textrm{Var}(\vec{r}_i)$ if $i=j$. The variance of $ \vec{r}_i$ can be expressed as $ \textrm{Var}(\vec{r}_i)= \langle \vec{r}_i \cdot \vec{r}_i \rangle - \langle \vec{r}_i \rangle^2$. Due to symmetry $\langle \vec{r}_i \rangle=\vec{0}$ and therefore the variance of of $ \vec{r}_i$ is simply $ \textrm{Var}(\vec{r}_i)= \langle \vec{r}_i \cdot \vec{r}_i \rangle = |\vec{r}_i|^2 = l^2$. Altogether, the covariance of $\vec{r}_i$ and $\vec{r}_j$ equals $\textrm{Cov}(\vec{r}_i, \ \vec{r}_j)=\delta_{ij}l^2$. The covariance of $\vec{r}_i$ and $\vec{r}_j$ can also be expressed as $\textrm{Cov}(\vec{r}_i, \ \vec{r}_j) = \langle \vec{r}_i \cdot \vec{r}_j \rangle - \langle \vec{r}_i \rangle \cdot \langle \vec{r}_j \rangle$. Combining the two different expressions for the covariance and using that $\langle \vec{r}_i \rangle=0$, results in $\langle \vec{r}_i \cdot \vec{r}_j \rangle =\delta_{ij}l^2$. This result can be used to determine the RMS:

$$\textrm{RMS}=\sqrt { \langle R^2 \rangle } = \sqrt { \langle \vec{R} \cdot \vec{R} \rangle } =\sqrt { \big\langle \sum_{i=1}^N \vec{r}_i \cdot \sum_{j=1}^N \vec{r}_j \big\rangle } =\sqrt { \sum_{i=1}^N \sum_{j=1}^N \langle \vec{r}_i \cdot \vec{r}_j \rangle }= $$ $$=\sqrt { \sum_{i=1}^N \sum_{j=1}^N l^2 \delta_{ij} + 0^2}=\sqrt { \sum_{i=1}^N l^2}=\sqrt { N l^2}=l\sqrt { N }$$

Let $Z_i$ denote the $i$-th coordinate of the end-to-end distance vector $\vec{R}$ after $N$ steps, and let $X_i$ and $Y_i$ denote the number of steps taken in the $i$-th dimension in the positive and negative direction respectively. Then the set of random variables $\{X_i, Y_i\}_{i=1}^d$ follows a multinomial distribution with parameters $N$ and $\displaystyle p_i=\frac{N}{2d}$. For sufficiently large values of $N$, $\{X_i, Y_i\}_{i=1}^d$ are approximately iid (independent and identically distributed) Poisson random variables with parameters $\displaystyle \lambda_i = \frac{N}{2d}$. For $\lambda > 20$, i.e. $N>40d$, $\textrm{Po}(\lambda) \sim \textrm{N}(\lambda, \lambda)$. $ Z_i = l(X_i - Y_i)$ and therefore $\displaystyle Z_i \sim \textrm{N}(l(\lambda - \lambda), l^2(\lambda+\lambda))=\textrm{N}(0, 2l^2\lambda)=\textrm{N}\left(0, \frac{l^2N}{d}\right)$.

$\displaystyle \langle R \rangle = \langle \sqrt{R^2} \rangle = \left\langle \sqrt{ \sum_{i=1}^d Z_i^2} \right\rangle$. The square root of a sum of $k$ independent $\textrm{N}(0, 1)$-distributed random variables is distributed according to the chi distribution, $\chi_k$. Therefore $\displaystyle \sqrt{ \sum_{i=1}^d \frac{dZ_i^2}{l^2N}}$ is approximately $\chi_d$-distributed for large values of $N$. The expected value of a $\chi_k$-distributed random variable is $\displaystyle \sqrt{2} \frac{ \Gamma \left(\frac{k+1}{2}\right) }{\Gamma \left( \frac{k}{2}\right)}$.

Hence $\displaystyle \langle R \rangle =\left\langle\sqrt{ \sum_{i=1}^d Z_i^2}\right\rangle =\left\langle l \sqrt{\frac{N}{d}} \sqrt{ \sum_{i=1}^d \frac{dZ_i^2}{l^2N} }\right\rangle = l \sqrt{\frac{2N}{d} }\frac{ \Gamma \left(\frac{d+1}{2}\right) }{\Gamma \left( \frac{d}{2}\right)}$.