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 moreblack balls than white balls (breaking ties u.a.r.).In Randomized Distributed Edge Coloring via an Extension of theChernoff--Hoeffding Bounds byAlessandro Panconesi and Aravind Srinivasan, it is shown that theChernoff 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...
Are bins with more black than white balls negatively 1-correlated?
pr.probability
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.