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<W_i ) = 0. $$ In other words, $M_{i}$ indicates whether bin $i$ contains more black balls than white balls (breaking ties u.a.r.).

In Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds 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...


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.

  • $\begingroup$ 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! :) $\endgroup$ – Immanuel Weihnachten Jul 22 '15 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.