I am doing some probability work with "bounds". An example is given for something called the second moment method. The example proceeds as follows:
$$X = I_1 + \dots + I_n,$$
where the $I_j$ are uncorrelated indicator r.v.s. Let $p_j = E(I_j)$. Then
$$\text{Var}(X) = \sum_{j = 1}^n \text{Var}(I_j) = \sum_{j = 1}^n (p_j – p_j^2) = \sum_{j = 1}^n p_j – \sum_{j = 1}^n p_j^2 = \mu – c,$$
where $\mu = E(X), c = \sum_{j = 1}^n p_j^2$. Also, $E(X^2) = \text{Var}(X) + (EX)^2 = \mu^2 + \mu – c$. So
$$P(X = 0) \le \dfrac{\text{Var}(X)}{E(X^2)} = \dfrac{\mu – c}{\mu^2 + \mu – c} \le \dfrac{1}{\mu + 1},$$
where the last inequality is easily checked by cross-multiplying.
I don't understand why $\dfrac{\mu – c}{\mu^2 + \mu – c} \le \dfrac{1}{\mu + 1}$ is true. I began by seeing if I could simplify $\dfrac{\mu – c}{\mu^2 + \mu – c}$ by factoring out the numerator $\mu – c$ from the denominator $\mu^2 + \mu – c$. Using polynomial division, I got that $\mu^2 + \mu – c = (\mu – c)(\mu(1 + c)) + c^2$, so that didn't work out. Would anyone please explain to me why $\dfrac{\mu – c}{\mu^2 + \mu – c} \le \dfrac{1}{\mu + 1}$ is true? Thank you.
Best Answer
As what you have quoted, "the last inequality is easily checked by cross-multiplying"
Note that since $p_j \in (0, 1)$, $\displaystyle \mu = \sum_{j=1}^n p_j > 0 $ and thus $1 + \mu > 0$.
Also we have $p_j > p_j^2$, therefore $\displaystyle \mu - c = \sum_{j=1}^n p_j - \sum_{j=1}^n p_j^2 \geq 0$ and thus $\mu^2 + \mu - c > 0$
With both denominator checked as positive, we can cross-multiply the inequality without changing the inequality sign:
$$ \begin{align} \frac {\mu - c} {\mu^2 + \mu - c} & \leq \frac {1} {\mu + 1} \\ \iff (\mu - c)(\mu + 1) & \leq \mu^2 + \mu - c \\ \iff \mu^2 - \mu c + \mu - c & \leq \mu^2 + \mu - c \\ \iff -\mu c & \leq 0 \end{align} $$
So the inequality is always true as $\mu > 0, c > 0$