Pigeonhole for threshold on sum of non-negative random variables

98 Views Asked by At

Let $X = X_1 + X_2 + \cdots + X_n$ , where $X_i$ ($1 \le i \le n$) are non negative random variables ($X_i$ are not independent). Then using pigeonhole principle would it be correct to state the following two

$$ \Pr[X \ge t] \le \Pr\bigg[ \bigcup_{i=1}^n\big(X_i \ge \frac{t}{n}\big) \bigg] $$

$$ \Pr[X \le t] \le \Pr\bigg[ \bigcup_{i=1}^n\big(X_i \le \frac{t}{n}\big) \bigg] $$

where $t \ge 0$.

If $X \ge t$, then by pigeonhole principle there will be an $i$ s.t. $X_i \ge \frac{t}{n}$. But the implication is not true in the other direction.
Similarly for when $X \le t$, there would be an $i$ s.t. $X_i \le \frac{t}{n}$.

If the claim above are correct then I can write

$$ \Pr[X = t] \le \Pr\bigg[ \bigcup_{i=1}^n\big(X_i \ge \frac{t}{n}\big) \bigg] $$

$$ \Pr[X = t] \le \Pr\bigg[ \bigcup_{i=1}^n\big(X_i \le \frac{t}{n}\big) \bigg] $$ Which seems fine to me, but bit weird that I can break $\Pr[X=t]$ into two forms one where $X_i \ge \frac{t}{n}$ are involved and another where $X_i \le \frac{t}{n}$.

1

There are 1 best solutions below

0
On BEST ANSWER

Claim and the given argument is correct; a reason why this should still be conceptually OK is because those bounds, in general, are going to be quite loose (especially the final step of going from $P(X \geq t) \geq P(X = t)$ is extremely loose for $X$ continuous, say).