5
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – camomille
    Jun 15, 2011 at 20:58
  • $\begingroup$ 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? $\endgroup$ Jun 16, 2011 at 5:08
  • $\begingroup$ @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. $\endgroup$
    – Seva
    Jun 16, 2011 at 8:22
  • $\begingroup$ 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. $\endgroup$
    – Someone
    Jun 16, 2011 at 9:26
  • $\begingroup$ @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. $\endgroup$
    – Seva
    Jun 16, 2011 at 10:17

1 Answer 1

0
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Seva, I think you're using the notation $\gg$ in a non standard way here. $\endgroup$ Jun 16, 2011 at 17:03
  • $\begingroup$ 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$. $\endgroup$
    – Seva
    Jun 16, 2011 at 18:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – camomille
    Jun 17, 2011 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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