Let $\sigma=(\sigma\_1,...,\sigma\_m)$ be i.i.d. uniform binary 0-1 valued variables.
I'm trying to figure out what is the order of $E[||\sigma||\_p]$ with respect to $m$.


Jensen's inequality gives an upper bound of $(m/2)^{1/p}$, but how do I get a lower bound? (I'm hoping for a lower bound of the same order.)



Expected p-norm of binary vector
$\newcommand\si\sigma$
For any real $p>0$,
$$m^{-1/p}\,E\|\si\|\_p=E\Big(\frac1m\sum\_{j=1}^m\si\_j\Big)^{1/p}.$$
By the law of large numbers, $\frac1m\sum\_{j=1}^m\si\_j\to2^{-1}$ in probability (as $m\to\infty$). So, by Fatou's lemma,
$$\liminf\_{m\to\infty}m^{-1/p}\,E\|\si\|\_p\ge2^{-1/p}$$
and hence
$$E\|\si\|\_p\ge(1-o(1))(m/2)^{1/p}.$$
Thus, the upper bound $(m/2)^{1/p}$ is asymptotically exact for large $m$.




---


Let us now get an asymptotically exact explicit lower bound on $E\|\si\|\_p$. Since you said "Jensen's inequality gives an upper bound of $(m/2)^{1/p}$" and "$p$-norm" is mentioned in the title of your post, one should conclude that $p\ge1$ and hence $1/p\in(0,1]$ (for $p>0$).


Note that
$$E\|\si\|\_p=\mu\_{1/p},$$
where $\mu\_q:=ES^q$ and $S:=\sum\_{j=1}^m\si\_j$, so that $S$ has the binomial distribution with parameters $m$ and $1/2$ and hence $\mu\_1=m/2$ and $\mu\_2=(m/2)^2+m/4$. Note also that $\mu\_q$ is log convex in $q>0$. So, for $t:=\frac{p-1}{2p-1}\in[0,1)$ we have $\mu\_1\le\mu\_{1/p}^{1-t}\mu\_2^t$, whence
$$\mu\_{1/p}\ge\mu\_1^{1/(1-t)}\mu\_2^{-t/(1-t)}
=\Big(\frac m2\Big)^{2-1/p}
\Big(\Big(\frac m2\Big)^2+\frac m4\Big)^{-1+1/p}
=\Big(\frac m2\Big)^{1/p}\Big(1+\frac1m\Big)^{-1+1/p}.$$
Thus,
$$E\|\si\|\_p\ge L\_{p,m}:=\Big(\frac m2\Big)^{1/p}\Big(1+\frac1m\Big)^{-1+1/p}.$$
Clearly, $L\_{p,m}\sim(m/2)^{1/p}$ (as $m\to\infty$). Thus, we have the explicit lower bound, $L\_{p,m}$, on $E\|\si\|\_p$ such that
$$E\|\si\|\_p\sim L\_{p,m}.$$


