The following is a probability qualifying exam problem that I'm struggling with.

Suppose that $X_1,..,X_n$ are i.i.d Rademacher random variables, i.e. $\mathbb{P}(X_i = \pm 1) = \dfrac{1}{2}$. Show that, $$ \lim\limits_{n\rightarrow\infty}\sum\limits_{k=1}^\infty\mathbb{P}(S_n = k^2) = 0, \;\;\; where \;\;\; S_n = \displaystyle\sum\limits_{i=1}^nX_i $$

Intuitively I can sort of see why for each term in the sum, $\lim\limits_{n\rightarrow\infty}\mathbb{P}(S_n = k^2) = 0$. This is because when $n$ is large, $\dfrac{1}{\sqrt{n}}S_n \sim N(0,1)$. However, I'm not sure how to make this argument rigorous. There's the $\sqrt{n}$ in the CLT that might cause trouble as well.

Should I start by considering a small interval around $k^2$, i.e. $(k^2-\epsilon, k^2+\epsilon)$? Then, perhaps I can try to argue that,

$$\mathbb{P}\left(\dfrac{1}{\sqrt{n}}(k^2-\epsilon) \leq S_n \leq \dfrac{1}{\sqrt{n}}(k^2+\epsilon)\right) \approx \int\limits_{\dfrac{1}{\sqrt{n}}(k^2-\epsilon)}^{\dfrac{1}{\sqrt{n}}(k^2+\epsilon)}\exp\left(-\frac{x^2}{2}\right)dx $$

Then take limits as $\epsilon \rightarrow 0$?


1 Answer 1


I'm not sure the central limit theorem is of any help here because the question regard $S_n$ and not a scaled version of it. Let me try a different approach.

If $n$ is odd, then $S_n$ cannot be a square number so $P(S_n=k^2)=0$. If $k>n$, then it is clear that $P(S_n=k)=0$ as well.

So let's assume that $n$ is even and $k$ such that $|k|\le n$. Then, $S_n=k$ if the number of $+1$ (say $A$) minus the number of $-1$ (say $B$) must be equal to equal to $k$. So, we have $A-B=k$ and $A+B=n$, which gives $A=\frac{n+k}{2},B=\frac{n-k}{2}$. Now, the question becomes combinatoric: in how many way we can choose $\frac{n+k}{2}$ '$+1$' and $\frac{n-k}{2}$ '$-1$'? This is ${ n \choose \frac{n+k}{2} }$, which gives \begin{align} P(S_n=k) = \frac{ { n \choose \frac{n+k}{2} } }{ 2^n } \end{align} Now, \begin{align} \sum_{k\ge 1} P(S_n=k^2) & = \sum_{k= 2}^{\lfloor\sqrt{n}\rfloor} \frac{1}{2^n} { n \choose \frac{n+k^2}{2} } \le \frac{ \sqrt{n}}{2^n} { n \choose \frac{n+4}{2} } = O(n^{-1/2})\to 0 \end{align} where the $O(n^{-1/2})$ follows by using Stirling approximation.


You must log in to answer this question.