# Randomized Solution to a System of Inequalities

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

-
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$? –  Helium 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. –  Helium Sep 14 '12 at 7:42
Any comment, answer, hint, tip, ...? None? :) –  Helium Sep 15 '12 at 0:16