Let $X_1,..., X_n$ be i.i.d discrete random variables which take their value in $\mathbb{Z}$ with a non trivial and finite support. Let $S_n = X_1+...+ X_n$
Prove the existence of $ 0 < C_1 < C_2 < \infty$ such that for all $ n \geq 1$ :
$$ C_1/\sqrt{n} \leq \sup_{k \in \mathbb{Z}} \mathbb{P}(S_n = k) \leq C_2/\sqrt{n}$$
I know that this can be proved using the central limit theorem yet we didn’t see this theorem in class so this exercise can be solved without using CLT.
So far here are my thoughts :
The fact that it’s $\sqrt{n}$ comes from the fact that the standard deviation of $S_n$ is $\theta \sqrt{n}$. Hence one possible strategy is to study the random variable : $\frac{S_n- \mu}{\theta/\sqrt{n}}$. Yet from now on I dind’t manage finding an upper bound on the probability.
For example using Markov inequality I get that :
$$\mathbb{P}( \mid \frac{S_n}{n} -\mu \mid \geq \theta/\sqrt{n}) \leq \frac{1}{n}$$
The problem is that it doesn’t help since I can’t say anything when $\mid S_n/n -\mu \mid \leq \theta/\sqrt{n}$.
Thank you !
I can prove the lower bound as follows:
$P(|S_n-n\mu| \geq cn^a\theta) \leq \frac{1}{c^2n^{2a-1}}$.
Thus the largest $P(S_n=k)$ is roughly greater than $(1-c^{-2}n^{1-2a})(2cn^a\theta+1)^{-1}$. (Because this quantity is not greater than $P(|S_n-n\mu| \leq cn^a\theta)|[n\mu-cn^a\theta,n\mu+cn^a\theta] \cap \mathbb{Z}|^{-1}$).
Take $a=1/2, c=2$, this quantity is greater than $\frac{3/4}{4\theta\sqrt{n}+1}$, which proves the lower bound.
Edit: this was done without looking at Michael’s comment.