MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n$ be a growing integer parameter, and suppose that $X_1,\dotsc,X_n$ are independent Bernoulli random variables with the probabilities of success $p_i:={\mathsf P}(X_i=1)$. If $X=X_1+\dotsb+X_n$ then, trivially, ${\mathsf E}(\sqrt X)\le\sqrt{np}$, where $p=(p_1+\dotsb+p_n)/n$. When can one expect ${\mathsf E}(\sqrt X)=o(\sqrt{np})$ to hold, and what estimates can be proven in this direction? (I actually would like to have an explicit and reasonable improvement as compared to the trivial $\sqrt{np}$ bound.) I suspect normal and Poisson approximations might be useful -- are they?

share|cite|improve this question
Did you try to bound from below the probability that $X$ is less than $\lambda np$ for a given $\lambda$ (for example thanks to Hoeffding inequality) ? For example if this probability is smaller than $1/2$ then we have $E(\sqrt{X}) \ge \sqrt{\lambda np}/2$ This would give a (quite strong) necessary condition on $n$ and $p$ for what you look for. – camomille Jun 15 '11 at 20:58
Chebyshev should suffice here. I believe that $E(\sqrt{X})=o(\sqrt{np})$ only when $np=o(1)$ but it's late, I'm tired and have a plane to catch, so who knows? – Ori Gurel-Gurevich Jun 16 '11 at 5:08
@camomille and Ori. You are right: Chebyshev shows that ${\mathsf E}(\sqrt X)\gg\sqrt{np}$ if, say, $np>2$, and Hoeffding seems to lead to the same conclusion under the stronger (!) assumption $np^2>1$ (or so). However, I am equally interested in the regime where $np$ is small. – Seva Jun 16 '11 at 8:22
Do you implicitly assume $p_1 = p_2 = \dots = p_n$? I'm asking because otherwise $p_1 = 1$ and $p_2 = \dots = p_n = 0$ (or just all $p_i$ close to these values) causes problems. – Someone Jun 16 '11 at 9:26
@Someone: no, $p_1=...=p_n$ is not assumed. If one of the $p_i$'s is equal to $1$ and the rest are equal to $0$, then ${\mathsf E}(\sqrt X)=\sqrt{np}=1$ -- which only shows that what I am interested in (namely, ${\mathsf E}(\sqrt X)$ is small as compared to $\sqrt{np}$) does not occur in this particular case. – Seva Jun 16 '11 at 10:17
up vote 0 down vote accepted

Having carefully checked the things, I am not really interested in the case where $pn\to 0$; and, when $pn\gg 1$, the observations of camomille and Ori resolve the problem, leading to ${\mathsf E}(\sqrt X)\gg\sqrt{np}$. Thanks to all those who have replied!

share|cite|improve this answer
Seva, I think you're using the notation $\gg$ in a non standard way here. – Ori Gurel-Gurevich Jun 16 '11 at 17:03
I think there is no problem with the notation. For $f$ and $g$ positive, $f\ll g$ is (I believe) standardly used as an equivalent of $f=O(g)$; that is, $f\le Cg$ with an absolute constant $C$. Thus, for instance, $f\ll 1$ means that $f$ is bounded from above by an absolute constant, and $f\gg 1$ means that $f$ is bounded away from $0$. – Seva Jun 16 '11 at 18:20
I use $f \ll g$ as an equivalent to $f=o(g)$ (not $f=O(g)$) and I have never seen it used in a different way. – camomille Jun 17 '11 at 9:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.