Asymptotic expression for discrete random walk

Question

I am trying to approximate the evolution of probability distribution of discrete random walk on the integers, starting from zero at the time step $n=0$. The probability of being at integer $k$ at time step $n$ is given by $$P_k(n)={1\over 2^n} {n\choose {n+k\over 2}},$$ where $k$’s are such that at time step $n$, ${n+k\over 2}$ is an integer.

Now I apply the Stirling’s formula to get $$P_k(n)\sim\sqrt{2\over \pi n}\Bigl(1-{k\over n}\Bigr)^{-(1+n-k)/2}\Bigl(1+{k\over n}\Bigr)^{-(1+n+k)/2}.\tag{1}\label{eq1}$$

But from Fourier transforms applied to the diffusion equation (continuous case), I know the solution (probability density) to be $${e^{-x^2/{4Dt}}\over \sqrt{4\pi Dt}},\tag{2}\label{eq2}$$ where $D$ is the diffusion coefficient.

And this makes me guess that for the discrete case, $P_k(n)$ should be asymptotic to $$\sqrt{2\over \pi n}e^{-k^2/2n}.\tag{3}\label{eq3}$$ And on Desmos, I’ve checked that this fits very well.

However, I’m not being able to show how this follows from equation $\eqref{eq1}$. Please help me show that (with some rigor).

---

Also, there is an issue of a mysterious factor of $2$, since to get $\eqref{eq3}$, I had to multiply the formulae suggested by equation $\eqref{eq2}$ by $2$. Any thoughts on that?

Answer 1

It is well known that $\lim\limits_{x \to \infty}\left( 1+\frac{c}{x}\right)^x = \exp(c)$

so here for sensible $n$ and $k$ you have

• $\Bigl(1-{k\over n}\Bigr)^{-(n-k)/2} \approx \exp\left(+ \frac{(n-k)k}{2n}\right)$ and
• $\Bigl(1+{k\over n}\Bigr)^{-(n+k)/2} \approx \exp\left(- \frac{(n+k)k}{2n}\right)$

and their product is therefore about $\exp\left(- \frac{k^2}{2n}\right)$.

In the random walk, all the possible positions are even after an even number of steps and odd after an odd number of steps. This may account for your mysterious factor of $2$

Answer 2

Considering $$P_k(n)={1\over 2^n} {n\choose {n+k\over 2}}$$ transform to factorials, take logarithms and use Stirling approximation for large values of $n$ and continue with Taylor expansions to get $$\log\left(P_k(n) \right)=\frac{1}{2} \log \left(\frac{2}{\pi n}\right)-\frac{2 k^2+1}{4 n}+\frac{k^2}{2 n^2}+O\left(\frac{1}{n^3}\right)$$ which gives as asymptotics $$P_k(n)=\sqrt{\frac{2}{\pi n}}\exp \left(-\frac{2 k^2+1}{4 n} \right)$$