<p>A good reference is Concentration of Measure for the Analysis of Randomized Algorithms, by Dubhashi and Panconesi.  This is not a standalone proof but shows how you could use the results therein to prove your desired inequality.</p>

<p>We say a set of random variables $X_i, i \in [n]$ are negatively associated if for all disjoint subsets $I,J \subset [n]$, and all nondecreasing functions $f$ and $g$,
$$
\mathbb{E}[f(X_i, i \in I)g(X_j, j \in J)] \leq \mathbb{E}[f(X_i, i \in I)]\mathbb{E}[g(X_j, j \in J)].
$$</p>

<p>By the proof of proposition 3.1 of D&amp;P, the variables $\{B_1, \dots, B_n\}$ and $\{W_1, \dots, W_n\}$ are negatively associated.  By the disjoint monotone aggregation property of negatively associated variables, (p.35 of D&amp;P), $-W_1, \dots, -W_n$ are also negatively associated, and the random variables $B_i-W_j$, over all choices of $i,j$ are as well.  In particular, the set of variables $B_i - W_i$, for any subset $I \subset [n]$ are negatively associated.</p>

<p>Then, per exercise 3.1, or just by applying the above inequality recursively with $f=g=1$,
$$
\mathbb{E}[ \prod_{i \in I}M_i ] \leq \prod_{i\in I}\mathbb{E}[ M_i],
$$
from which your inequality follows.</p>

CC BY-SA 3.0
2015-07-22T22:36:43.687Z
I did almost the same considerations, except for the key observation that $-W_1, ..., -W_n$ are negatively associated, thus $B_i-W_i(=B_i+(-W_i))$ is nondecreasing in both arguments. Thanks for the missing brick! :)
Immanuel Weihnachten
CC BY-SA 3.0
2015-07-22T17:57:33.603Z
2015-07-22T17:57:33.603Z
user41530
<p>Suppose we throw $m_b$ black balls and $m_w$ white balls independently and 
uniformly at random in $n$ bins. 
Let 
$\left\{ B_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$,
$\left\{ W_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$
be the number of black and white balls that end up in bin $i$, respectively.</p>

<p>Let 
$\left\{ M_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$
be the binary random variables such that<br>
$$
    \Pr(M_{i} = 1 \,|\, B_i&gt;W_i ) = 1,\\  
    \Pr(M_{i} = 1 \,|\, B_i=W_i ) = 1/2,\\  
    \Pr(M_{i} = 1 \,|\, B_i&lt;W_i ) = 0.  
$$
In other words, $M_{i}$ indicates whether bin $i$ contains more
black balls than white balls (breaking ties u.a.r.).</p>

<p>In 
<a href="http://epubs.siam.org/doi/abs/10.1137/S0097539793250767">Randomized Distributed Edge Coloring via an Extension of the
Chernoff--Hoeffding Bounds</a> by<br>
Alessandro Panconesi and Aravind Srinivasan, it is shown that the
Chernoff bound holds for dependent binary random variables such that 
for each $I \subseteq \left\{ 1, \cdots, n \right\}$
$$
    \Pr \left( \bigwedge_{i \in I} X_{i} = 1 \right) 
    \leq \prod_{i \in I} \Pr \left( X_{i} = 1 \right)
$$
They call the latter property negative 1-correlation. </p>

<p>My question is: are the r.v. $M_{i}$ negatively one correlated? </p>

<p>This is very intuitive, but I couldn't figure out any proof. All my attempts end up dealing with the explicit joint probability distribution of the $B_i$ and $W_i$, at which point I'm stuck...</p>

<pr.probability>
Are bins with more black than white balls negatively 1-correlated?
Immanuel Weihnachten
# Are bins with more black than white balls negatively 1-correlated?

(Asked by: username_0 on 2015-07-17)

Suppose we throw $m\_b$ black balls and $m\_w$ white balls independently and
uniformly at random in $n$ bins.
Let
$\left\{ B\_i \right\}\_{i \in \left\{ 1,\ldots,n \right\}}$,
$\left\{ W\_i \right\}\_{i \in \left\{ 1,\ldots,n \right\}}$
be the number of black and white balls that end up in bin $i$, respectively.

Let
$\left\{ M\_i \right\}\_{i \in \left\{ 1,\ldots,n \right\}}$
be the binary random variables such that  
$$
\Pr(M\_{i} = 1 \,|\, B\_i>W\_i ) = 1,\\
\Pr(M\_{i} = 1 \,|\, B\_i=W\_i ) = 1/2,\\
\Pr(M\_{i} = 1 \,|\, B\_i

In
[Randomized Distributed Edge Coloring via an Extension of the
Chernoff--Hoeffding Bounds](http://epubs.siam.org/doi/abs/10.1137/S0097539793250767) by  
Alessandro Panconesi and Aravind Srinivasan, it is shown that the
Chernoff bound holds for dependent binary random variables such that
for each $I \subseteq \left\{ 1, \cdots, n \right\}$
$$
\Pr \left( \bigwedge\_{i \in I} X\_{i} = 1 \right)
\leq \prod\_{i \in I} \Pr \left( X\_{i} = 1 \right)
$$
They call the latter property negative 1-correlation.

My question is: are the r.v. $M\_{i}$ negatively one correlated?

This is very intuitive, but I couldn't figure out any proof. All my attempts end up dealing with the explicit joint probability distribution of the $B\_i$ and $W\_i$, at which point I'm stuck...

**Tags:** pr.probability

---

## 1 answers

### Answer by username_1 on 2015-07-22. Score: 3 | Accepted answer

A good reference is Concentration of Measure for the Analysis of Randomized Algorithms, by Dubhashi and Panconesi. This is not a standalone proof but shows how you could use the results therein to prove your desired inequality.

We say a set of random variables $X\_i, i \in [n]$ are negatively associated if for all disjoint subsets $I,J \subset [n]$, and all nondecreasing functions $f$ and $g$,
$$
\mathbb{E}[f(X\_i, i \in I)g(X\_j, j \in J)] \leq \mathbb{E}[f(X\_i, i \in I)]\mathbb{E}[g(X\_j, j \in J)].
$$

By the proof of proposition 3.1 of D&P, the variables $\{B\_1, \dots, B\_n\}$ and $\{W\_1, \dots, W\_n\}$ are negatively associated. By the disjoint monotone aggregation property of negatively associated variables, (p.35 of D&P), $-W\_1, \dots, -W\_n$ are also negatively associated, and the random variables $B\_i-W\_j$, over all choices of $i,j$ are as well. In particular, the set of variables $B\_i - W\_i$, for any subset $I \subset [n]$ are negatively associated.

Then, per exercise 3.1, or just by applying the above inequality recursively with $f=g=1$,
$$
\mathbb{E}[ \prod\_{i \in I}M\_i ] \leq \prod\_{i\in I}\mathbb{E}[ M\_i],
$$
from which your inequality follows.

> **Comments:**
> **username_0**: I did almost the same considerations, except for the key observation that $-W_1, ..., -W_n$ are negatively associated, thus $B_i-W_i(=B_i+(-W_i))$ is nondecreasing in both arguments. Thanks for the missing brick! :)  

---

