Chernoff–Hoeffding Bounds in Dependent Settings
In this chapter, we consider the sum
where is an index set and the variables Xα, α , may not be independent. In some dependent situations, the Chernoff–Hoeffding bound can be salvaged to be applicable (as is, or with slight modifications) to X.
3.1 Negative Dependence
We consider the ...