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


1 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$.


\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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .