Weighted summation of symmetric Bernoulli RV. Characteristic function inequality 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!
 A: I think you more or less got it, one just needs to take $|t|$ sufficiently small.

*

*Let $$\varphi_{n,m}(t):=\mathbb E\!\left[\mathrm e^{\mathrm it(S_{n+m}-S_n)}\right]=\prod_{k=n+1}^{n+m}\cos\!\left(\frac t{\sqrt k}\right)\!.$$

*Let $p,q>1$ be Lebesgue exponents, i.e., such that $\frac1p+\frac1q=1$. Then
\begin{align*}
1-\varphi_{n,m}(t)
&\le
\mathbb E\!\left[\left\lvert\mathrm e^{\mathrm it(S_{n+m}-S_n)}-1\right\rvert\mathbf1_{\{|S_{n+m}-S_n|\ge1\}}\right]
+\mathbb E\!\left[\left\lvert\mathrm e^{\mathrm it(S_{n+m}-S_n)}-1\right\rvert\mathbf1_{\{|S_{n+m}-S_n|<1\}}\right]\\[.4em]
&\le\mathbb E\!\left[\left\lvert\mathrm e^{\mathrm it(S_{n+m}-S_n)}-1\right\rvert^p\right]^{\frac1p}\:
\mathbb P\left(|S_{n+m}-S_n|\ge1|\right)^{\frac1q}
+|t|\\[.4em]
&\le2\,\mathbb P\Bigl(|S_{n+m}-S_n|\ge1\Bigr)^{\frac1q}+|t|,
\end{align*}
where we applied Hölder's inequality and the bound $|\mathrm e^{ix}-1|\le2\wedge|x|$ for any $x\in\mathbb R$. Letting $q\downarrow1$ shows that (as you already observed)
$$2\,\mathbb P\Bigl(|S_{n+m}-S_n|\ge1\Bigr)\ge1-\varphi_{n,m}(t)-t\tag{1}$$
for every $t\ge0$, $m\ge1$ and $n\ge0$.

*Now we find a lower bound on $1-\varphi_{n,m}(t)$. Note that
$$0\le\cos(x)-1+\frac{x^2}2\le\frac{x^4}{24}$$
for any $x\in\mathbb R$, so
$$\varphi_{n,m}(t)=\prod_{k=n+1}^{n+m}\left(1-\frac{t^2}{2k}+\varepsilon_k(t)\right)\!,$$
where $\varepsilon_k(t):=\cos(\frac t{\sqrt k})-1+\frac{t^2}{2k}$
is such that $0\le\varepsilon_k(t)\le\frac{t^4}{24k^2}$.
Then, for all $t\ge0$, $m\ge1$ and $n\ge\frac{t^2}2$, each of the above factors lies in $(0,1)$, so
\begin{align*}
\log\varphi_{n,m}(t)&=\sum_{k=n+1}^{n+m}\log\!\left(1-\frac{t^2}{2k}+\varepsilon_k(t)\right)\\[.4em]
&\le-\frac{t^2}2\sum_{k=n+1}^{n+m}\frac1k+\frac{t^4}{24}\sum_{k=n+1}^\infty\frac1{k^2},
\end{align*}
because $\log(1-u)\le-u$ for any $u\in(0,1)$.
Using $\frac1k\ge\ln(\frac{k+1}k)$ and $\frac1{k^2}\le\frac1{k-1}-\frac1k$, we obtain
$$1-\varphi_{n,m}(t)\ge1-\exp\left(-\frac{t^2}2\log\!\left(1+\frac{m+1}{n+1}\right)
+\frac{t^4}{24n}\right)\tag{2}$$
for every $t\ge0$, $m\ge1$ and $n\ge\frac{t^2}2$.

*Let $0<\varepsilon<1$ and pick $0<t<\frac\varepsilon2$ so small that $\exp(\frac{t^4}{24})\le1+\varepsilon$. We construct an increasing sequence $(n_k)_{k\ge0}$ (depending on $\varepsilon$) such that $\mathbb P(|S_{n_{k+1}}-S_{n_k}|\ge1)>\frac{1-\varepsilon}2$ for every $k\ge0$.
We can take $n_0:=0$ and $n_1:=1$ (because $|S_1-S_0|=|X_1|=1$ almost surely). Let $k\ge1$ and assume $n_k$ has been constructed. Choose $m:=m_k\ge1$ so large that $$\exp\!\left(-\frac{t^2}2\log\!\left(1+\frac{m+1}{n_k+1}\right)\right)\le\frac\varepsilon{2(1+\varepsilon)}.$$
Then, by $(2)$,
$$1-\varphi_{n_k,m}(t)\ge1-\frac\varepsilon{2(1+\varepsilon)}\cdot(1+\varepsilon)^{\frac1{n_k}}\ge1-\frac\varepsilon2.$$
Setting $n_{k+1}:=n_k+m_k$ and reporting in $(1)$ gives
$$2\,\mathbb P\Bigl(|S_{n_{k+1}}-S_{n_k}|\ge1\Bigr)\ge1-\frac\varepsilon2-t>1-\varepsilon,$$
that is $$\mathbb P\Bigl(|S_{n_{k+1}}-S_{n_k}|\ge1\Bigr)>\frac{1-\varepsilon}2.$$
A: We can also suppose that, for a chosen $N$
$$\mathbb{P}(|S_{N+m} - S_N) \geq 1) <\frac{1}{4}$$
hence we have that
$$\limsup_{m \rightarrow \infty}|\mathbb{E}[\exp\{it(S_{n+m}-S_n)\}-1]| \leq |t| +\frac{1}{2}$$
but
$$\limsup_{m \rightarrow \infty}|\mathbb{E}[\exp\{it(S_{n+m}-S_n)\}]|=0, \ |t| >0$$
but these are contradictory for $0 < |t| < \frac{1}{2}$.
