Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]$.

share|improve this question
    
It sounds like you also need some sort of constraints on $\mathbb{x}$. –  Alex R. Sep 14 '12 at 4:55
    
@Sam: You mean something other that $\mathbf x \in [0,1]^k$? –  Mohsen Sep 14 '12 at 5:19
    
If you talk about probabilities, you'll have to say something about what probability measure you use to pick $\mathbb{x}$. –  Raskolnikov Sep 14 '12 at 6:05
    
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. –  Mohsen Sep 14 '12 at 7:42
    
Any comment, answer, hint, tip, ...? None? :) –  Mohsen Sep 15 '12 at 0:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.