Expected location of a non-homogeneous random walk 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]$$
 A: 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.
A: 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.
