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?
$\begingroup$
$\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$– camomilleJun 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$– Ori Gurel-GurevichJun 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$– SevaJun 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$– SomeoneJun 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$– SevaJun 16, 2011 at 10:17
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
3
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!
-
$\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$– SevaJun 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$ Jun 17, 2011 at 9:37