How to bound the norm of sum of iid Bernoulli random variables? [closed]

$ x_1 , .., x_n$ are iid 0-1 random variables.

$\forall i \in [1,n]\;$ Pr$[x_i=1] = p$.

Given that $n \geq 2,\; p \leq 1/2\;$ and $\;pn \leq 1$.

$h:= x_1+ x_2 +..+ x_n$.

Show that there is an absolute constant $k$ such that E$[h^2] \leq k$.Pr$[h \neq 0]$.

This problem showed up in my research in Boolean Function Analysis.


We need to show that $E[h^2]/\Pr(h\neq 0)$ is bounded. Since $h$ is binomial, $E(h^2)=np [ 1+(n-1)p] \leq np(1+np)$ and $\Pr(h\neq 0)=1-(1-p)^n$. Let $x=np$, we have $$\frac{E[h^2]}{\Pr(h\neq 0)}\leq \frac{x(1+x)}{1-(1-x/n)^n}$$ Given the conditions, we just have to show that the right-hand side is bounded as a function on $[0,1]$. It is sufficient to study its behavior as $x\to 0$. Then $1-(1-x/n)^n\sim x$. The result follows.


I am merely making bdx77's proof more formal, in case it helps someone.

\begin{aligned} Pr[h \neq 0] &= 1 - (1-p)^n \\ &\geq 1-e^{-pn}\; \text{(Since} \; \forall x \in \mathbb{R}\; (1-x \leq e^{-x}\text{))}\\ &\geq \frac{pn}{2} \;\text{(Since} \; \forall x \in [0,1]\; (e^{-x} \leq 1-\frac{x}{2}\text{))} \end{aligned}

Now, \begin{aligned} E[h^2] &= np + n(n-1)p^2 \\ &\leq np(1+np)\\ &\leq 2np\\ &= 4(\frac{np}{2})\\ &\leq 4Pr[h \neq 0] \end{aligned} which is what we set out for.