# 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!

• Connected : math.stackexchange.com/q/3470424 Commented Nov 17, 2021 at 23:34
• I have taken the liberty to add "Weighted summation of symmetric Bernoulli RV. " in front of your title. It can help to attract more people to your question... I just added as well "random walk" to the tags. Commented Nov 17, 2021 at 23:40

## 2 Answers

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

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

• +1. It is clear once we understand that $\varphi_{n,m}(t)\to0$ as $m\to\infty$ (a kind of obvious fact which I may have over-detailed in my answer). Commented Nov 22, 2021 at 20:16