7

I'm trying to teach myself probability theory, and an exercise has me stumped. This exercise comes from Alon & Spencer 4.8, in the chapter on the second moment method.

Let $X$ be a random variable taking values in $\mathbb{Z}_{\geq 0}$. Let $E[X^2]$ denote the expectation of its square. Prove that

$\displaystyle Pr[X=0] \leq \frac{Var[X]}{E[X^2]}$

In particular, they prove in the chapter that this is true by replacing $E[X^2]$ with $E[X]^2$ by using a simple application of Chebyshev's inequality (they set $\lambda$ in the theorem to $E[X]/Var[X]$). However, this bound is easily seen to be tighter, and so it seems I need to come up with a shrewder application of the inequality by redefining the random variable or choosing an appropriate constant.

Any hints?

JeremyKun
  • 3,580

2 Answers2

4

Hint:

$$P(X=0)=1-P(X \ge 1)$$ $$\frac{\operatorname{Var}(X)}{E(X^2)}=1-\frac{E(X)^2}{E(X^2)}$$ Take conditional expectation and using $E(X \mid X \ge 1)^2 \le E(X^2 \mid X \ge 1)$, calculate both sides and get the result.

Nate Eldredge
  • 97,710
Koushik
  • 4,472
  • calculations are fairly straightforward do the expansions into infinite sum – Koushik Dec 21 '12 at 02:36
  • 2
    You can use $\LaTeX$ on this site. I edited your answer to use it. You could double-check that I didn't mess it up. – Nate Eldredge Dec 21 '12 at 02:51
  • @Koushik - could you elaborate? does this hold for non integer random variables or is there a counter example for that case? – Daniel Oct 13 '21 at 10:13
2

see https://en.wikipedia.org/wiki/Second_moment_method for a proof. The basic idea is you define Y as an indicator function. $Y=1[X>0]$ and then using Cauchy–Schwarz $$E[X]=E[XY]<=\sqrt{E[X^2]E[Y^2]}=\sqrt{E[X^2]E[Y]}=\sqrt{E[X^2]Pr(X>0)}$$ $$Pr(X>0)>=E^2[X]/E[X^2]$$ $$Pr(X=0)=1-Pr(X>0)<=\frac{E[X^2]-E^2[X]}{E[X^2]}=\frac{Var(X)}{E[X^2]}$$

Daniel
  • 75
  • 7