Are bins with more black than white balls negatively 1-correlated?

Question

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...

Answer 1

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.