MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Some correlation inequalities for probabilistic analysis of algorithms

Dubhashi, Devdatt P. and Ranjan, Desh

August 1994, 16 pages.

Status: available - back from printing

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.

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Dubhashi, Devdatt P. and Ranjan, Desh},
  TITLE = {Some correlation inequalities for probabilistic analysis of algorithms},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-143},
  MONTH = {August},
  YEAR = {1994},
  ISSN = {0946-011X},