Let $(X_n)_{n\geq 1}$ be a sequence of iid random variables such that $P(X_1=1)=P(X_1=-1)=1/2.$ Show that $\lim\limits_{n\rightarrow \infty} P(S_n=k^2$ for some $k\in \mathbb{N})=0$ where $S_n=X_1+...X_n.$

My idea to approach this problem is as follows:

Since $P(S_n=l)=\binom{n}{(n-l)/2}2^{-n}$ if $n,l$ are both even, or both odd; $P(S_n=l)=0$ otherwise. Therefore, for each $n\in\mathbb{N}$, we have $$ P(S_n=k^2\ \ \mbox{for some}\ \ k\in \mathbb{N})\leq \sum\limits_{k=0}^{[\sqrt{n}]} \binom{n}{\frac{n-k^2}{2}}2^{-n}=\sum\limits_{k=0}^{[\sqrt{n}]}\frac{n!}{(\frac{n-k^2}{2})!(\frac{n+k^2}{2})!2^n}. $$

However, I don't find a appropriate upper bound of right hand side of the inequality. Can anyone give me some idea how to do it? Thanks.


1 Answer 1


The basic idea is to use Stirling's approximation to prove a local central limit theorem for $P(S_n=k)$. We must be careful to cut off the sum at the appropriate point since the local central limit theorem provides a poor estimate for $k$ of order $n$, but luckily this does not turn out to be a problem.

Assume $j=O(\sqrt{n})$. Stirling's approximation tells us that

$$P(S_{2n}=2j)=2^{-2n}\frac{(2n)!}{(n+j)!(n-j)!}\sim2^{-2n}\frac{\sqrt{4\pi n}(2n/e)^{2n}}{\sqrt{4\pi^2(n^2-j^2)}((n+j)/e)^{n+j}((n-j)/e)^{n-j}}=\frac1{\sqrt{n\pi}}\left(1-\frac{j^2}{n^2}\right)^{-1/2}\left(1-\frac{2j}{n+j}\right)^j\left(1-\frac{j^2}{n^2}\right)^{-n}.$$

Now $(1-\frac{j^2}{n^2})^{-1/2}\to1$ and $(1-\frac{2j}{n+j})^{j}\le1$. Using the expansion $\log(1+x)=x+O(x^2)$, we have


since $j=O(\sqrt{n})$. We can then compute a similar estimate for $P(S_{2n+1}=2j+1)$ using $P(S_{2n+1}=2j+1)=\frac12P(S_{2n}=2j)+\frac12P(S_{2n}=2(j+1))$. Putting this all together, we deduce that for every $L>0$, there exists $C=C(L)$ such that


for all $n$ and all $j\le L\sqrt{n}$. (There are more precise estimates but we will not need them.) Now fix $\varepsilon>0$ and let $M>0$ be large enough that $P(S_n>\sqrt{nM})<\varepsilon$ for all $n$; such an $M$ exists since $S_n/\sqrt{n}$ converges in distribution to a Gaussian by the central limit theorem. We have

$$P(S_n=k^2\text{ for some }k)\le\sum_{k\le(nM)^{1/4}}P(S_n=k^2)+P(S_n>\sqrt{nM})\\ \le(nM)^{1/4}\frac{C(\sqrt{M})}{\sqrt{n}}+\varepsilon$$

and in particular,

$$\limsup_{n\to\infty}P(S_n=k^2\text{ for some }k)\le\varepsilon.$$

Letting $\varepsilon\to0$ concludes the proof.

  • $\begingroup$ Thanks! Your proof is very clear. $\endgroup$ Mar 31, 2017 at 4:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .