Weighted summation of symmetric Bernoulli RV. Characteristic function inequality

Question

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!

Answer 1

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.$$

Answer 2

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}$.