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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered May 31, 2022 at 13:31
-
$\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 non-zero; 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$– lchenCommented Jun 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$ Commented 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$– lchenCommented Jun 2, 2022 at 3:29
-