Expected location of a non-homogeneous random walk

Question

Let $p_1,\dots,p_T$ be a sequence of real numbers in $[0,1]$ and let $B_1,\dots,B_T$ be a sequence of independent random variables such that $\Pr[B_t=1]=p_t$ and $\Pr[B_t=-1]=1-p_t$. Is there any good lower bound of $$\mathbb{E}\left[\left|\sum_{t=1}^T B_t\right|\right]$$

Answer 1

I don't know how tight this bound has to be or what you intend to use it for, but an easy one would be $$\mathbb E \left(\left|\sum_{t=1}^T B_t\right|\right)\ge=T\left(\prod_{t=1}^T p_t+\prod_{t=1}^Tq_t\right),$$ where $q_t=1-p_t$.

To see that this is true, note that $$\mathbb P(B_1+\ldots+B_T=T)=p_1\cdots p_T$$ (that is, every $B_t$ takes the value $1$), and $$P(B_1+\ldots+B_T=-T)=q_1\cdots q_T$$ (all them are $-1$). Then, $$P(|B_1+\ldots+B_T|=T)=p_1\cdots p_T+q_1\cdots q_T.$$

And so, one term of the expectacion is $T(p_1\cdots p_T+q_1\cdots q_T)$, and this is a lower bound, since all the other terms when calculating the expectation are also positive.

Answer 2

Expanding on my comment: From Jensen's inequality we get $$ E\left[\left|\sum_{t=1}^T B_t\right|\right] \geq \left|E\left[\sum_{t=1}^T B_t\right]\right| = \left|\sum_{t=1}^T(2p_t-1)\right|$$

---

For tightness we observe $$\sum_{t=1}^T B_t = \sum_{t=1}^T(2p_t-1) + \sum_{t=1}^T (B_t-E[B_t])$$ So $$\left|\sum_{t=1}^T B_t\right| \leq \left|\sum_{t=1}^T(2p_t-1)\right| + \left|\sum_{t=1}^T (B_t-E[B_t])\right|$$ So \begin{align} \left|\sum_{t=1}^T (2p_t-1)\right| &\leq E\left[\left|\sum_{t=1}^TB_t\right|\right] \\ &\leq \left| \sum_{t=1}^T (2p_t-1)\right| + E\left[\left|\sum_{t=1}^T(B_t-E[B_t])\right|\right] \end{align} However $$ E\left[\left|\frac{1}{T}\sum_{t=1}^T(B_t-E[B_t])\right|\right] \leq \sqrt{\frac{1}{T^2}\sum_{t=1}^T Var(B_t)}\rightarrow 0$$

---

Edit: By similar reasoning we can get a stronger form of tightness of the above bound: If one of the two “drift” conditions hold: $$\liminf_{T\rightarrow \infty}\frac{1}{T}\sum_{t=1}^{T}(2p_t-1)>0$$ or $$\limsup_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}(2p_t-1)<0$$ then $$\lim_{T\rightarrow\infty}\left[E\left[\left|\sum_{t=1}^{T}B_t\right|\right]-\left|\sum_{t=1}^{T}(2p_t-1)\right|\right]=0$$ So the bound is very tight. This objectively qualifies as a “good” lower bound.