# Union bound probability of random union

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

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}

• could you please explain the second to last line? It is not completely clear to me. Thanks Jan 25, 2021 at 14:40
• @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. Jan 25, 2021 at 18:14