We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables Y1,...,Yr are arbitrary [0,1]-valued functions of independent random variables X1,...,Xm, modulo a restriction that every Xi influences at most k of the variables Y1,...,Yr.
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
- Chernoff bounds
- Information theory
- Limited independence
- Shearer's lemma