English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Some correlation inequalities for probabilistic analysis of algorithms

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.

Item is

Files

show Files
hide Files
:
MPI-I-94-143.pdf (Any fulltext), 14MB
Name:
MPI-I-94-143.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Dubhashi, Devdatt P.1, Author
Ranjan, Desh2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 1994
 Publication Status: Issued
 Pages: 16 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/94-143
Report Nr.: MPI-I-94-143
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -