2
$\begingroup$

Given a set of $\mathbf v_i \in \{0,1\}^k$ for $i=1,\dots,n$ and a vector $\mathbf x \in [0,1]^k$, we want to decide if the following inequality holds or not:

$ \mathbf x \le \sum_{i=1}^n \alpha_i \mathbf v_i \text{ for some $\alpha_i$ such that $\sum_{i=1}^n \alpha_i=1$} \tag{I} $ where the comparison is taken componentwise. Assume, we randomly take $m$ out of $n$ vectors $\mathbf v_i$ and call them $\mathbf u_j$ for $j=1,\dots,m$ and solve the following inequality instead:

$ \mathbf x \le \sum_{j=1}^m \beta_j \mathbf u_j \text{ for some $\beta_j$ such that $\sum_{j=1}^n \beta_j=1$}\tag{II} $

Obviousely, if the answer to (II) is yes, the answer to (I) is yes as well (because it doesn't harm if we set some of $\alpha_i$ to zero). It is also obvious that if the answer to (I) is no, the answer of (II) is no as well.

Now, my question is that what is the probability that the answer to (II) is no but the answer to (I) is yes?

We can assume $\mathbf v_i$ are distinct. Additionally, let $\mathbf v_i = \langle v_i^1,\dots,v_i^k \rangle$. For each $\mathbf v_i$, $v_i^j$ is 1 with probability $p_j$ and zero with probability $1-p_j$. Also, assume $\mathbf x$ is uniformly distributed over $[0,1]^k$, i.e., each entry of $\mathbf x$ is picked uniformly from $[0,1]$.

  • 0
    Any comment, answer, hint, tip, ...? None? :)2012-09-15

0 Answers 0