Abstract
The analysis of many randomized algorithms, for example in dynamic load
balancing, probabilistic divide-and-conquer paradigm and distributed
edge-coloring, requires ascertaining the precise nature of the correlation
between the random variables arising in the following prototypical
``balls-and-bins'' experiment.
Suppose a certain number of balls are thrown uniformly and
independently at random into $n$ bins. Let $X_i$ be the random
variable denoting the number of balls in the $i$th bin, $i \in
[n]$. These variables are clearly not independent and are intuitively
negatively related.
We make this mathematically precise by proving the following type of
correlation inequalities:
\begin{itemize}
\item For index sets $I,J \subseteq [n]$ such that $I \cap J =
\emptyset$ or $I \cup J = [n]$, and any non--negative
integers $t_I,t_J$,
\[ \prob[\sum_{i \in I} X_i \geq t_I \mid \sum_{j \in J} X_j \geq t_J]
\]
\\[-5mm]
\[\leq
\prob[\sum_{i \in I} X_i \geq t_I] .\]
\item For any disjoint index sets $I,J \subseteq [n]$, any $I' \subseteq I,
J' \subseteq J$ and any non--negative integers $t_i, i \in I$ and $t_j, j \in J$,
\[ \prob[\bigwedge_{i \in I}X_i \geq t_i \mid \bigwedge_{j \in J} X_j
\geq t_j]\]\\[-5mm]\[ \leq
\prob[\bigwedge_{i \in I'}X_i \geq t_i \mid \bigwedge_{j \in J'} X_j \geq t_j] . \]
\end{itemize}
Although these inequalities are intuitively appealing, establishing
them is non--trivial; in particular, direct counting arguments become
intractable very fast. We prove the inequalities of the first type by
an application of the celebrated FKG Correlation Inequality. The proof
for the second uses only elementary methods and hinges on some
{\em monotonicity} properties.
More importantly, we then introduce a
general methodology that may be applicable whenever the random variables
involved are negatively related. Precisely, we invoke a general notion
of {\em negative assocation\/} of random variables and show that:
\begin{itemize}
\item The variables $X_i$ are negatively associated. This yields most
of the previous results in a uniform way.
\item For a set of negatively associated variables, one can apply the
Chernoff-Hoeffding bounds to the sum of these variables. This provides
a tool that facilitates analysis of many randomized algorithms, for
example, the ones mentioned above.
