Given $r$ r.v.s $x_k$: $x_k=1$ with probability $p_k$ and $0$ otherwise. Let $s_i=\sum_{j=1}^r c_{ij}p_j$ where $c_{ij}\in[0,1]$, $1\le i\le n$. Let $E_i$ denote the event $\sum_{j=1}^r c_{ij}x_j>(1+\delta)s_i$. I want to compute an upperbound of $\Pr(\bigcup_{i=1}^n E_i)$. A loose bound is $\sum_{i=1}^n E_i$. Another bound is $1\Pi_{i} [1\Pr(E_i)]$. However, since $E_i$ are mutually dependent, how to derive a tighter bound?
1 Answer
In general, really nothing can be said here. Very much will depend on how close the rows of the matrix $(c_{ij})$ are to one another.
Even in the very special case when $p_k=1/2$ for all $k$, this is a very difficult problem, considered in detail in Chapter 5 "Bernoulli Processes" of Talagrand's book Upper and Lower Bounds for Stochastic Processes.
Arguably the main idea there is that of generic chaining, going back to Kolmogorov. If you have enough information on how close the rows of the matrix $(c_{ij})$ are to one another, you can try a custom adaptation of the generic chaining method.

$\begingroup$ Thank you Losif for your comment and pointing out the reference. I now see that the problem is intuitively understandable but hard to solve. My original thought is: suppose two events $E_i$ and $E_j$ "overlap" on only a single $x_k$ where $c_{ik}$ and $c_{jk}$ are nonzero; I was expecting results like $\Pr(E_i\cup E_j)\le a\cdot[\Pr(E_i)+ \Pr(E_j)]$ with some $a<1$. $\endgroup$– lchenJun 1, 2022 at 13:11

$\begingroup$ '"overlap" on only a single $x_k$": What do you mean by that? It is generally not a good idea to denote a random variable and its values by the same symbol  this creates confusion. $\endgroup$ Jun 1, 2022 at 13:39

$\begingroup$ My comment was not clear. What I meant is that if $(c_{ij})$ is sparse (having many zero elements), $E_i$ and $E_j$ can be correlated, and we may hope to have some result. But I now see that it is still highly intractable. $\endgroup$– lchenJun 2, 2022 at 3:29
