Skip to main content
A tail bound for read‐k families of functions
Published Web Location
https://arxiv.org/pdf/1205.1478v1.pdfNo data is associated with this publication.
Abstract
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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.