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.

Suppose I have random binary variables $X_1, \dots, X_n$. I know they are negatively correlated in the sense that for any index set $I \subseteq \{1, \dots, n\}$ we have $E[ \prod_{i \in I} X_i ] \leq p^{|I|}$ for some $p \in (0,1)$

I have some non-decreasing function $f:\{0,1\}^n \rightarrow \{0,1\}$ and I want to estimate an upper bound on the probability that $P(f(X_1, \dots, X_n) = 1))$

For specific types of functions (for example, when $f$ is a large deviation event $\sum X_i \geq t$) one can give good bounds, but are there general types of bounds available in this case?


share|improve this question
in $\mathsf E[\prod_i X_i]\leq p^i$ what is $i$ in the rhs? –  Ilya May 24 '12 at 12:38
I imagine it's supposed to be $|I|$. –  Ben Millwood May 24 '12 at 14:09
Presumably the $p$ doesn't depend on $I$. –  Robert Israel May 24 '12 at 19:57
This is a very strange usage of the term "negatively correlated". The actual correlations of the $X_i$ could be arbitrarily close to $+1$. –  Robert Israel May 24 '12 at 20:00
What do you want the upper bound to be based on? For example, you could have $f(x_1,\ldots,x_n) = 1$ everywhere, and then the probability is $1$. –  Robert Israel May 24 '12 at 20:08

Your Answer


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

Browse other questions tagged or ask your own question.