Need an upper bound for a simple expectation involving Rademacher random variables.

Question

I need an upper bound on the following expectation:
$$E_{x_1,dots,x_n} left| sum_{i=1}^n a_i x_i right| quad,quad mbox{s.t.} sum_{i=1}^n a_i^2=1.$$
Here $x_i$'s are iid Rademacher random variables ($x_i=+1$ or $x_i=-1$, each with probability $1/2$) and |.| is the absolute value. The real vector $(a_1,...a_n)$, as shown, is on the unit sphere.
What is the best upper bound you know for this expectation? Getting a bound using Holder's inequality is straightforward,
begin{equation}
E_{x_1,dots,x_n} left| sum_{i=1}^n a_i x_i right| leq E_{x_1,dots,x_n} |boldsymbol{a}|_1 |boldsymbol{x}|_{infty} = |boldsymbol{a}|_1
end{equation}
However, I am hoping for a tighter bound.
Thanks!

user8675309 · Answer

using $Ebig[Xbig]^2 leq Ebig[X^2big]$ (Jensen) allows you to (i) linearize the absolute value and (ii) use explicitly use  $sum_{i=1}^n a_i^2=1$.
$Big(E_{mathbf x} big[ vertsum_{i=1}^n a_i X_i vertbig]Big)^2$
$leq E_{mathbf x} big[ (sum_{i=1}^n a_i X_i big)^2big]$
$=E_{mathbf x} big[ sum_{i=1}^n a_i^2 X_i^2  big] + E_{mathbf x} big[ sum_{i=1}^nsum_{jneq i} a_ia_j X_iX_j  big]$
$= sum_{i=1}^n a_i^2 E_{mathbf x} big[X_i^2  big] +  sum_{i=1}^nsum_{jneq i} a_ia_j E_{mathbf x} big[X_ibig]E_{mathbf x} big[X_j  big]$
$= sum_{i=1}^n a_i^2 +0$
$=1$
taking square roots
$E_{mathbf x} big[ vertsum_{i=1}^n a_i X_i vertbig]leq 1$
recall
$bigVert mathbf abigVert_2 leq bigVert mathbf abigVert_1$
by triangle inequality so this is a sharper bound.

Need an upper bound for a simple expectation involving Rademacher random variables.

One Answer

Add your own answers!

Ask a Question