<p>I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and multiplicative approximation here.
Can I ask you about the problem in which you need this value to be computed? </p>

CC BY-SA 3.0
2015-06-29T11:46:30.913Z
2015-06-29T11:46:30.913Z
Marek Adamczyk
<p>A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, X_n) \in \mathbb{Z}(\mathcal{P})$, $(X_i \in \{0,1\})$:</p>

<ul>
  <li> $\mathbb{E}[X_i]=x_i$, for all $i \in [n]$.
</li>
  <li>For any $S \subseteq [n]$, $\mathbb{E}[\prod_{i\in S} X_i] \leq \prod_{i \in S} x_i$ and $\mathbb{E}[\prod_{i\in S} (1-X_i)] \leq \prod_{i \in S} (1-x_i)$ (negative correlation).</li>
</ul>

<p>An example is the dependent randomized rounding by Chekuri, Vondrak, and Zenklusen (<a href="http://arxiv.org/pdf/0909.4348v2.pdf" rel="nofollow">http://arxiv.org/pdf/0909.4348v2.pdf</a>). </p>

<p>We focus on <em>the dependent randomized rounding</em>. Given a point $x \in \mathcal{P}$, where $\mathcal{P}$ is a matroid polytope, let us assume that $X$ is the outcome of the random process (the dependent randomized rounding). Can we evaluate the value of $Pr\Big(\displaystyle \bigwedge_{i \in S} X_i=1 \Big)$  for some $S \subseteq [n]$? Shall we use sampling for this purpose?</p>

<p>That would be great if you can comment on this.</p>

CC BY-SA 3.0
2015-03-28T15:33:53.110Z
Are you assuming each $X_i\in [0,1]$?  Otherwise the conditions on the products seem strange...
Neal Young
CC BY-SA 3.0
2015-03-28T18:49:44.070Z
@NealYoung, Yes, I assume $x_i \in [0,1]$ and $X_i \in \{0,1\}$.
salmAn
CC BY-SA 3.0
2015-03-29T13:40:37.207Z
What exactly are you interested in bounding with a Chernoff-like bound?  E.g. are you interested in bounding $\Pr[\sum_i X_i \ge (1+\epsilon)\sum_i x_i]$?
Neal Young
CC BY-SA 3.0
2015-03-29T13:50:25.703Z
What about thm's 3.2 and 3.4 of http://epubs.siam.org/doi/pdf/10.1137/S0097539793250767 ?
Neal Young
CC BY-SA 3.0
2015-03-29T18:50:17.137Z
@NealYoung thank you very much for your comments. What I'm interested in is basically $Pr\Big(\displaystyle \bigwedge_{i \in S} X_i=1 \Big)$. I updated the question to make it clearer.
salmAn
CC BY-SA 3.0
2015-03-29T19:00:05.287Z
@NealYoung, To make it more concrete, I also limited the question to the _dependent randomized rounding_ by Chekuri et al.
salmAn
CC BY-SA 3.0
2015-03-29T20:35:09.753Z
Hmm.  Well, don't you have (for any $S$) that $$\Pr\left[\forall_{i\in S} X_i = 1\right] = \Pr\left[\prod_{i\in S} X_i = 1\right] = E\left[\prod_{i\in S} X_i\right] \le \prod_{i\in S} x_i$$ and $$\Pr\left[\forall_{i\in S} X_i = 0\right] = \Pr\left[\prod_{i\in S} (1-X_i) = 1\right] = E\left[\prod_{i\in S} (1-X_i)\right] \le \prod_{i\in S} 1-x_i?$$  These seem like about the best bounds you could hope for in general given your assumptions...
Neal Young
CC BY-SA 3.0
2015-03-31T01:58:09.590Z
@NealYoung, correct. We know (for any $S$) that $\mathbb{E}[\prod_{i\in S} X_i]$ is less than or equal to $\prod_{i \in S} x_i$, yet the question is, how much less? (in case they aren't equal). Can we calculate $\mathbb{E}[\prod_{i\in S} X_i]$ more precisely?
salmAn
<approximation-algorithms><randomized-algorithms><chernoff-bound><sample-complexity>
Evaluating the expected value of negatively correlated random variables
salmAn
# Evaluating the expected value of negatively correlated random variables

(Asked by: username_0 on 2015-03-27)

A polynomial random process satisfying the following properties converts a fractional point $(x\_1, x\_2, \ldots, x\_n) \in \mathcal{P}$, $(x\_i \in [0,1])$ to a random integer point $(X\_1, X\_2, \ldots, X\_n) \in \mathbb{Z}(\mathcal{P})$, $(X\_i \in \{0,1\})$:

* $\mathbb{E}[X\_i]=x\_i$, for all $i \in [n]$.
* For any $S \subseteq [n]$, $\mathbb{E}[\prod\_{i\in S} X\_i] \leq \prod\_{i \in S} x\_i$ and $\mathbb{E}[\prod\_{i\in S} (1-X\_i)] \leq \prod\_{i \in S} (1-x\_i)$ (negative correlation).

An example is the dependent randomized rounding by Chekuri, Vondrak, and Zenklusen (<http://arxiv.org/pdf/0909.4348v2.pdf>).

We focus on *the dependent randomized rounding*. Given a point $x \in \mathcal{P}$, where $\mathcal{P}$ is a matroid polytope, let us assume that $X$ is the outcome of the random process (the dependent randomized rounding). Can we evaluate the value of $Pr\Big(\displaystyle \bigwedge\_{i \in S} X\_i=1 \Big)$ for some $S \subseteq [n]$? Shall we use sampling for this purpose?

That would be great if you can comment on this.

**Tags:** approximation-algorithms, randomized-algorithms, chernoff-bound, sample-complexity

> **Comments:**
> **username_1**: Are you assuming each $X_i\in [0,1]$?  Otherwise the conditions on the products seem strange...  
> **username_0**: @NealYoung, Yes, I assume $x_i \in [0,1]$ and $X_i \in \{0,1\}$.  
> **username_1**: What exactly are you interested in bounding with a Chernoff-like bound?  E.g. are you interested in bounding $\Pr[\sum_i X_i \ge (1+\epsilon)\sum_i x_i]$?  
> **username_1**: What about thm's 3.2 and 3.4 of http://epubs.siam.org/doi/pdf/10.1137/S0097539793250767 ?  
> **username_0**: @NealYoung thank you very much for your comments. What I'm interested in is basically $Pr\Big(\displaystyle \bigwedge_{i \in S} X_i=1 \Big)$. I updated the question to make it clearer.  
> **username_0**: @NealYoung, To make it more concrete, I also limited the question to the _dependent randomized rounding_ by Chekuri et al.  
> **username_1**: Hmm.  Well, don't you have (for any $S$) that $$\Pr\left[\forall_{i\in S} X_i = 1\right] = \Pr\left[\prod_{i\in S} X_i = 1\right] = E\left[\prod_{i\in S} X_i\right] \le \prod_{i\in S} x_i$$ and $$\Pr\left[\forall_{i\in S} X_i = 0\right] = \Pr\left[\prod_{i\in S} (1-X_i) = 1\right] = E\left[\prod_{i\in S} (1-X_i)\right] \le \prod_{i\in S} 1-x_i?$$  These seem like about the best bounds you could hope for in general given your assumptions...  
> **username_0**: @NealYoung, correct. We know (for any $S$) that $\mathbb{E}[\prod_{i\in S} X_i]$ is less than or equal to $\prod_{i \in S} x_i$, yet the question is, how much less? (in case they aren't equal). Can we calculate $\mathbb{E}[\prod_{i\in S} X_i]$ more precisely?  

---

## 1 answers

### Answer by username_2 on 2015-06-29. Score: 1

I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and multiplicative approximation here.
Can I ask you about the problem in which you need this value to be computed?


---

