# Evaluating the expected value of negatively correlated random variables

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.

• Are you assuming each $X_i\in [0,1]$? Otherwise the conditions on the products seem strange... – Neal Young Mar 28 '15 at 15:33
• @NealYoung, Yes, I assume $x_i \in [0,1]$ and $X_i \in \{0,1\}$. – salmAn Mar 28 '15 at 18:49
• 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 Mar 29 '15 at 13:40
• What about thm's 3.2 and 3.4 of epubs.siam.org/doi/pdf/10.1137/S0097539793250767 ? – Neal Young Mar 29 '15 at 13:50
• @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 Mar 29 '15 at 18:50