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
    It sounds like you also need some sort of constraints on $\mathbb{x}$.2012-09-14
  • 0
    @Sam: You mean something other that $\mathbf x \in [0,1]^k$?2012-09-14
  • 0
    If you talk about probabilities, you'll have to say something about what probability measure you use to pick $\mathbb{x}$.2012-09-14
  • 0
    You are right. I just edited the question and added the distribution of $\mathbf x$. Please let me know if it is not clear. Thanks.2012-09-14
  • 0
    Any comment, answer, hint, tip, ...? None? :)2012-09-15

0 Answers 0