# Stirling Formula and random walk

Let $p \in (0,1)$, $N \in \mathbb{N}$ and $X_{1}, ..., X_{N}$ a family of independent random variables with $\mathbb{P}(X_{k}=1)=p, \mathbb{P}(X_{k}=-1)=(1-p)$ for all $k \in \{1, ..., N\}$. It is $S_{n}=\sum_{k=1}^{n}X_{k}$ for all $n \in \{0, ..., N\}$. We know that $\mathbb{P}(S_{2n}=0)$ is asymptotically the same as $\frac{1}{\sqrt{\pi n}}$. Using the Stirling Formula, show that there exists $c \in (0,1)$ and $M \ge 0$ if $p \neq \frac{1}{2}$, so that: $\mathbb{P}(S_{2n}=0)\le M \cdot c^{n}$.

Unluckily, I have no idea how to show that. Is there anyone who could give me a hint on how to start?

Thanks a lot!

Best, Jolle

Guide:

$P(S_{2n}=0)=\frac{(2n)!}{n!n!}p^n(1-p)^n$

Now use Stirling approximation to find a suitable expression $E(n)$ such that $\frac{(2n)!}{n!n!}\leq E(n)$ for every positive integer $n$.

Then $P(S_{2n}=0)\leq E(n)p^n(1-p)^n$ and search for $M\geq0$ and $c\in(0,1)$ such that $E(n)p^n(1-p)^n\leq Mc^n$.

• Thanks a lot! I now have $P(S_{2n}=0) = \frac{(2n)!}{n!n!}p^{n}(1-p)^{n}=\frac{1}{\sqrt{\pi n}}2^{2n}p^{n}(1-p)^{n}$. Is this less equal than $\frac{1}{\sqrt{n}}2^{2n}p^{n}(1-p)^{n}$ for example? – Jolle Jun 3 '18 at 14:49
• Is it possible to choose $M=4^n$ and $c^n=(p-p^2)^n$? – Jolle Jun 3 '18 at 17:10
• No to your last comment, because $M$ should be a constant, so should not depend on $n$. I haven't checked (and will not go into the details), but if $4^n(p-p^2)^n$ indeed works as bound then you better take $M=1$ and $c=4(p-p^2)$. – drhab Jun 3 '18 at 17:27
• Note that $c:=4p(1-p)\in(0,1)$ if $p\notin\{0,0.5,1\}$ – drhab Jun 3 '18 at 17:33
• You are right - seems like this is not going to work. Do you have any idea how to estimate $P(S_{2n}=0)$? I found that $n!$ can be estimated by $e^{1/(12n)}$. Is that a possible way? I simply don‘t find an answer. – Jolle Jun 4 '18 at 9:30