Confusion about the average distance traveled on a $1$D random walk The average absolute distance on a one dimensional random walk is supposed to be $\sqrt{n}$. Where $n$ steps are taken from the origin or $n$ is the time. I don't have an intuitive understanding or proof of why this is. My approach to the problem would have been to find the mean of all the possible outcomes after n intervals. In order to do that, one would have to sum up the product of the binomial terms and the corresponding distances and divide by the total number of outcomes. 
For example, let's say we were working out the average distance after 3 steps. taking $(x+\frac{1}{x})^3$, all we have to do is multiply the absolute value of the exponent of $x$ and it's coefficiant. That's $1\cdot{3} + 3\cdot{1} + 3\cdot{1} + 1\cdot{3} = 12$. $12$ divided by $2^3$ is $\frac{3}{2}$. This is not $\sqrt3$.
Is this a correct approach? If not, why not? If so, how come it is not similar to $\sqrt{n}$ - does it approach it as $n$ goes to infinity or something?
Also, how do you evaluate that sum for any $n$?
 A: Not sure if I can answer satisfactory, but I'll try.

This is not $\sqrt 3$.

The claim is that the average walking distance for n steps approaches $\sqrt n$ for $n \rightarrow \infty$, not exact equality.
I visualize this by thinking of the random walk as the sum of $n$ Bernoulli experiments with the outcomes ${-1,+1}$, meaning go left or right. Therefore, we know that the walking distance will have a Binomial distribution, because that's just its definition. Now, the fact that the Binomial distribution approaches the Normal distribution for large $n$ is a fact that I can't explain (because I don't understand it fully), but it's the easiest way to see that the distance (i.e. the standard deviation) indeed approaches $\sqrt n$.
https://en.wikipedia.org/wiki/Binomial_distribution#Normal_approximation
A: 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\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)}$.
