Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space. Let $\{E_i\}_{i = 1}^N,$ with $E_i \in\mathcal{F}$ be a set of events and let $i(X)$ be a R.V. assuming values in $\{1,...,N\}$

Is there a way to bound the following quantity?

$$\mathbb{P}\left[\bigcup_{i\in[N]: i \neq i(X)} E_i\right].$$

I am looking in an upper-bound that resemble the union bound: in fact, if the union would not depend on the R.V. $X$ we may use the union bound in the following way

$$\mathbb{P}\left[\bigcup_{i\in[N]} E_i\right] \leq \sum_{i\in[N]}\mathbb{P}\left[ E_i\right].$$


1 Answer 1


Let $n:=N$ and $J:=i(X)$. Then the probability to bound is \begin{aligned} P\Big(\bigcup_{i\in[n]\setminus\{J\}}E_i\Big) &=\sum_{j\in[n]}P\Big(\{J=j\}\cap \bigcup_{i\in[n]\setminus\{j\}}E_i\Big) \\ &=\sum_{j\in[n]}P\Big(\bigcup_{i\in[n]\setminus\{j\}}\big(\{J=j\}\cap E_i\big)\Big) \\ &\le\sum_{j\in[n]}\sum_{i\in[n]\setminus\{j\}}P(\{J=j\}\cap E_i) \\ &=\sum_{j\in[n]}\sum_{i\in[n]\setminus\{j\}}P(J=j)P(E_i|J=j) \\ &=\sum_{j\in[n]}P(J=j)\sum_{i\in[n]\setminus\{j\}}P(E_i|J=j). \end{aligned} If each event $E_i$ does not depend on $J$, then we further have \begin{aligned} P\Big(\bigcup_{i\in[n]\setminus\{J\}}E_i\Big) &\le\sum_{j\in[n]}P(J=j)\sum_{i\in[n]\setminus\{j\}}P(E_i) \\ &=\sum_{i\in[n]}P(E_i)\sum_{j\in[n]\setminus\{i\}}P(J=j) \\ &=\sum_{i\in[n]}P(E_i)P(J\ne i). \end{aligned}

  • $\begingroup$ could you please explain the second to last line? It is not completely clear to me. Thanks $\endgroup$
    – Apprentice
    Commented Jan 25, 2021 at 14:40
  • 1
    $\begingroup$ @Apprentice : The equality in the second to last line is just the interchange of the order of summation, with the factors not depending on the inner summation index put before the inner summation sign. $\endgroup$ Commented Jan 25, 2021 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.