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 upper-bound 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?



Tight upper-bound on dependent events
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*](https://link.springer.com/book/10.1007/978-3-642-54075-2).


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.


