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




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$.

  • $\begingroup$ 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? $\endgroup$ – Jolle Jun 3 '18 at 14:49
  • $\begingroup$ Is it possible to choose $M=4^n$ and $c^n=(p-p^2)^n$? $\endgroup$ – Jolle Jun 3 '18 at 17:10
  • $\begingroup$ 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)$. $\endgroup$ – drhab Jun 3 '18 at 17:27
  • $\begingroup$ Note that $c:=4p(1-p)\in(0,1)$ if $p\notin\{0,0.5,1\}$ $\endgroup$ – drhab Jun 3 '18 at 17:33
  • $\begingroup$ 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. $\endgroup$ – Jolle Jun 4 '18 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.