Welcome to MathOverflow

Question

4

1

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?

flag	asked Jun 15 2011 at 19:40 Seva 4,983●1●8●26

	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 2011 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 2011 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 2011 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 2011 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 2011 at 10:17

show 1 more comment

Seva · Accepted Answer · 2011-06-16 12:49:05Z UTC

0

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!

edited Jun 16 2011 at 12:49

answered Jun 16 2011 at 12:40

Seva
4,983●1●8●26

Seva, I think you're using the notation $\gg$ in a non standard way here. – Ori Gurel-Gurevich Jun 16 2011 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 2011 at 18:20

2

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 2011 at 9:37

The expectation of $\sqrt{B(n,p)}$

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.