Walking Randomly - How Far?

If $x\ne 0$ at for some $n,$ then $a_{n+1}=a_{n}$ because with equal probabilities $x$ changes to either $x+1$ or $x-1.$ If $x=0,$ then necessarily $|x|$ grows by $1.$

If $n$ is odd, the probability of $x=0$ is $0.$ If $n=2k$, there are $\displaystyle {2k\choose k}$ equiprobable ways to have the same number of tails as of heads. Thus, the probability of $x=0$ for $n$ even is $\displaystyle {n\choose n/2}\bigg/2^n.$ This leads to the following recurrence

$\displaystyle a_{n+1}=\begin{cases} a_n,& \text{if }n\text{ is odd}\\ \displaystyle a_n+{n\choose n/2}\big/2^n,& \text{if }n\text{ is even}. \end{cases}$

Solving that we obtain $\displaystyle a_{2n+2}=a_{2n+1}=\sum_{k=0}^n{2k\choose k}\bigg/2^{2k}.$ It follows that

$\displaystyle \lim_{n\to\infty}a_n=\sum_{k=0}^{\infty}{2k\choose k}\bigg/2^{2k}.$

It's not hard to roughly estimate the central binomial coefficient $\displaystyle {2k\choose k}.$ It's the largest among $2k+1$ coefficients in the sum $\displaystyle \sum_{s=0}^{2k}{2k\choose s}=2^{2k},$ so that $\displaystyle {2k\choose k}(2k+1)\gt 2^{2k}.$ In other words, $\displaystyle {2k\choose k}\bigg/2^{2k}\gt\frac{1}{2k+1}.$ We conclude that $a_n\to\infty,$ for

$\displaystyle \sum_{k=0}^{\infty}{2k\choose k}\bigg/2^{2k}\gt\sum_{k=0}^{\infty}\frac{1}{2k+1}$

and the latter series is known to converge to infinity.

Let $y$ be that random variable that represents the incremental change in $x$ because of a coin toss. Thus, $y$ takes the following two values: $-1$ and $1$, has a mean of $\mu=0$, and a variance of $\sigma^2=1$. Central limit theorem implies that after a large number, $n$, of coin tosses, $x$ has a normal distribution with mean $\tilde{\mu}=n\mu=0$ and variance $\tilde{\sigma}^2=n\sigma^2$. Thus, $z=|x|$ has a half normal distribution with expected value

$\displaystyle a_n = \frac{\tilde{\sigma}\sqrt{2}}{\sqrt{\pi}} =\frac{\sigma\sqrt{2n}}{\sqrt{\pi}} =\sqrt{\frac{2n}{\pi}}.$

As $n\rightarrow\infty$, $a_n\rightarrow\infty$.

First Approach

Let $x$ be $S_n$ the summed variables; $X$ follow a binomial with PDF $\displaystyle \phi_n(x)=2^{-n} {n\choose n-x}$.

We have

$\displaystyle \mathbb{E}(|X|)=\sum _{x=0}^n \left| x-\frac{n}{2}\right| \phi_n(x).$

Assume $n$ is sufficiently large that:

$\displaystyle \begin{align}\left\lceil \frac{n}{2}\right\rceil \approx \frac{n}{2}&=2 \sum _{x=\frac{n}{2}}^n \left(x-\frac{n}{2}\right) \phi_n(x)\\ &=\frac{\Gamma \left(\frac{n}{2}+\frac{1}{2}\right)}{\sqrt{\pi } \Gamma \left(\frac{n}{2}\right)} \end{align}$

We have

$\displaystyle \underset{n\to \infty }{\text{lim}}\frac{1}{\sqrt{n}}\frac{\Gamma \left(\frac{n}{2}+\frac{1}{2}\right)}{ \Gamma \left(\frac{n}{2}\right)}=\frac{1}{\sqrt{2}}$

In other words

$\displaystyle \lim_{n\to\infty}\mathbb{E}(|X|)=\sqrt{\frac{n}{2 \pi}}$

Second Approach

The binomial PDF

$\phi_n(x)=2^{-n} {n\choose x}$

Adjusting for $2 |x-\frac{n}{2}|$ to adapt it to an absolute sum, we have the characteristic function $\Psi$:

$ \displaystyle \begin{align}\Psi_X(t)&=\sum _{x=\frac{n}{2}}^n 2^{-n} {n\choose x} \left(\exp \left(i 2 t \left(x-\frac{n}{2}\right)\right)\right)\\ &=\frac{\Gamma \left(\frac{n}{2}+\frac{1}{2}\right) \, _2F_1\left(1,-\frac{n}{2};\frac{n+2}{2};-e^{2 i t}\right)}{\sqrt{\pi } \Gamma \left(\frac{n}{2}+1\right)} \end{align}$

and the mean

$\displaystyle - i \Psi'_X(t)|_{t=0}=\frac{n \Gamma \left(\frac{n}{2}+\frac{1}{2}\right)}{2 \sqrt{\pi } \Gamma \left(\frac{n}{2}+1\right)}$

as before.

Third Approach}

The characteristic function of a Benoulli that delivers $\{-1,1\}$, $\displaystyle \Psi_X(t)= \frac{1}{2}(e^{i t}+ e^{-i t}) = \cos(t).$ Hence the moments or order p of the sum

$\displaystyle m_p=i^p \frac{\partial ^p\cos ^n(t)}{\partial t^p}|_{t=0},$$ with $m_1=0$, $m_2=n$, $m_3=0$,$m_4=n (3 n-2)$.

Using Kurtosis as a benchmark of the speed of convergence to Gaussian, $\displaystyle \kappa=\frac{m_4}{m_2^2}$, we have $\displaystyle \kappa=3-\frac{2}{n}$.

For $n$ large enough, the distribution is effectively Gaussian. Let $\varphi(x)$ be the normal distribution with mean 0 and standard deviation $\sqrt{n}$. We have $\displaystyle \int_{-\infty}^{\infty} |x| \varphi(x) \;dx=\sqrt{\frac{2}{\pi }} \sqrt{n}$ as the converging expectation.

This is problem 115 from A Mathematical Orchard by M. I. Krusemeyer, G. T. Gilbert, L. C. Larson (MAA, 2012). Solution 2 is by Amit Itagi. The same approach was taken by Hélvio Vairinhos and Keith Dawid; Solution 3,4,5 are by N. N. Taleb.

The problem is an instance of what is generally referred to as a random walk.