How to prove inequality between probabilities of negative-binomial random variable and geometric variable?

Question

The problem is: Let $X$ be a negative binomial random variable of parameters $r,p$, then $X=Y_1 + Y_2+\ldots+Y_r$, where $Y_j$ ,$j=1,\ldots,r$ are geometric random.variables of parameter $p$. Show that: $\mathbb{P}(X>k)\leq r \mathbb{P}(Y_1>k/r)$ Can anybody help me please? I've tried a lot :c

Answer 1

The proposed inequality is true in general (continuous as well as discrete, bounded support or unbounded), not just for the nice and well-known examples of NegativeBinomial (sum of Geometric), Binomial (sum of Bernoulli), or Gamma (sum of exponential) etc.

Rewrite the left hand side as

$$\mathbb{P}\Bigl\{X > k \Bigr\} = 1 - \mathbb{P}\Bigl\{X \leq k \Bigr\} = 1 - \mathbb{P}\Biggl\{ \Bigl(\sum_{i = 1}^r Y_i \Bigr)\leq k \Bigg\}~.$$

Then, note that the event $\left(\sum_{i = 1}^r Y_i\right) \leq k$ behaves as if it is a union that contains the intersection of the individual events $\bigcap_{i = 1}^r \left( Y_i \leq \frac{k}r \right)$. To be convinced of this fact, please consider the events $Y_1 + Y_2 \leq 2$ versus $Y_1 \leq 1 \bigcap Y_2 \leq 1$.

Geometrically, one can view this as the simplex solid being larger than the cube. For example, with all $Y_i$ being non-negative, the simplex solid $Y_1+Y_2+Y_3 \leq 3$ clearly contains the entirety of the unit cube $Y_1 \leq 1 \bigcap Y_2 \leq 1 \bigcap Y_3 \leq 1$.

Therefore

\begin{align} \mathbb{P}\Bigl\{X > k \Bigr\} = 1 - \overbrace{ \mathbb{P}\Bigl\{ \left(\textstyle\sum_{i = 1}^r Y_i \right) \leq k \Bigr\} }^{\text{larger event}} &\leq 1 - \overbrace{ \mathbb{P}\Bigl\{ \textstyle\bigcap_{i = 1}^r \left( Y_i \leq \frac{k}r \right) \Bigr\} }^{\text{smaller event}} \\ &= \mathbb{P}\biggl\{ \Bigl[ \textstyle\bigcap_{i = 1}^r \left( Y_i \leq \frac{k}r \right) \Bigr]^c \biggr\}\\ &= \mathbb{P}\Bigl\{ \textstyle\bigcup_{i = 1}^r \left( Y_i > \frac{k}r \right) \Bigr\} ~. \end{align}

Now, the probability of the union is smaller than the sum of the probabilities, by Boole's inequality, also known as Bonferroni inequality: $$\mathbb{P}\Bigl\{ \textstyle\bigcup_{i = 1}^r ( Y_i > \frac{k}r ) \displaystyle \Bigr\} \leq \sum_{i = 1}^r \mathbb{P}\Bigl\{Y_i > \frac{k}r \Bigr\} = r \cdot \mathbb{P}\Bigl\{Y_1 > \frac{k}r \Bigr\} $$ which is the right hand side.

Both "simplex versus hypercube" and Bonferroni inequality are very loose, so the overall inequality is very loose.