Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse





Some correlation inequalities for probabilistic analysis of algorithms


Ranjan,  Desh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)

(Any fulltext), 14MB

Supplementary Material (public)
There is no public supplementary material available

Dubhashi, D. P., & Ranjan, D.(1994). Some correlation inequalities for probabilistic analysis of algorithms (MPI-I-94-143). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as:
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.