# Show that $\lim\limits_{n\rightarrow \infty} P(S_n=k^2$ for some $k\in \mathbb{N})=0$

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.

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

$$\left(1-\frac{j^2}{n^2}\right)^{-n}=e^{j^2/n+O(j^4/n^3)}=O(1)$$

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

$$P(S_n=j)\le\frac{C(L)}{\sqrt{n}}$$

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.

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