Let
$$S_n = \sum_{k=1}^n \frac{X_k}{\sqrt{k}}$$ where $X_1, X_2, \ldots$ are iid symmetric Bernoullis with parameter $\frac{1}{2}$:
$$X_k =
\begin{cases}
1 &p=\frac{1}{2}\\
-1 &p=\frac{1}{2}
\end{cases}
$$
I found that the characteristic function for $S_n$ is
$$\varphi_n(t)=\prod_{k=1}^n \cos\left(\frac{t}{\sqrt{k}}\right)$$
and have proved the following inequality
$$|\mathbb{E}[\exp\{it(S_{n+m}-S_n)\}-1]| \leq |t|\cdot \mathbb{1}_{|\Delta S| < 1 } + 2\mathbb{P}(|S_{n+m}-S_n| \geq 1)\cdot \mathbb{1}_{|\Delta S| \geq 1 }, \ \forall \ t \in \mathbb{R}, \ n,m > 0$$
where $\Delta S = S_{n+m}-S_{n}$. Now I am looking to use this inequality to prove that there exists a subsequence $n_1, n_2,\ldots$ such that
$$\mathbb{P}(|S_{n_{k+1}}-S_{n_{k}}| \geq 1) \geq \frac{1}{4}$$
I started with
\begin{split}
\mathbb{P}(|\Delta S_n| \geq 1) &\geq\frac{1}{2} \left( |\mathbb{E}[e^{it\Delta S_n} – 1]|\right)\\
&=\frac{1}{2} \left( |\mathbb{E}[\cos(t\Delta S_n) + i\sin(t\Delta S_n) – 1]|\right)\\
&=\frac{1}{2} \left( \left|\mathbb{E}\left[\frac{e^{it\Delta S_n} + e^{-it\Delta S_n}}{2} + i \frac{e^{it\Delta S_n} – e^{-it\Delta S_n}}{2i}- 1\right]\right|\right)\\
& =\frac{1}{2} \left( \left|\mathbb{E}\left[\frac{e^{it\Delta S_n} + e^{-it\Delta S_n} + e^{it\Delta S_n} – e^{-it\Delta S_n} – 2}{2}\right]\right|\right)\\
& = \frac{1}{2}\left( \left|\mathbb{E}\left[\frac{2e^{it\Delta S_n} – 2}{2}\right]\right|\right)
\end{split}
where $\Delta S_n = S_{n_{k+1}}-S_{n_{k}}$. I think my intuition is right to deduce a lower bound for $\mathbb{P}(|\Delta S_n| \geq 1)$ with trig identities, but I'm stuck. Any help is welcome, thanks!
Weighted summation of symmetric Bernoulli RV. Characteristic function inequality
characteristic-functionscomplex numbersexpected valueprobability theoryrandom walk
Best Answer
I think you more or less got it, one just needs to take $|t|$ sufficiently small.