Abstract
In this note we prove a large deviation bound on the sum of random variables with the following dependency structure: there is a dependency graph G with a bounded chromatic number, in which each vertex represents a random variable. Variables that are represented by neighboring vertices may be arbitrarily dependent, but collections of variables that form an independent set in G are t-wise independent.
Original language | English (US) |
---|---|
Pages (from-to) | 208-212 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 106 |
Issue number | 5 |
DOIs | |
State | Published - May 31 2008 |
Funding
* Corresponding author. E-mail addresses: [email protected] (R. Gradwohl), [email protected] (A. Yehudayoff). 1 Research supported by US–Israel Binational Science Foundation Grant 2006060. 2 Research supported by a grant from the Israel Ministry of Science (IMOS)—Eshkol Fellowship.
Keywords
- Combinatorial problems
- Large deviation bounds
- Limited independence
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications