ICAR Research Data Repository for Knowledge Management
A tail bound for read-k families of functions
DSpace at IIT Bombay
View Archive Info| Field | Value | |
| Title |
A tail bound for read-k families of functions
|
|
| Creator |
GAVINSKY, D
LOVETT, S SAKS, M SRINIVASAN, S |
|
| Subject |
CONCENTRATION INEQUALITIES
ENTROPY limited independence Chernoff bounds Shearer's lemma information theory |
|
| Description |
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 X-i influences at most k of the variables Y1,...,Yr. (c) 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 99-108, 2015
|
|
| Publisher |
WILEY-BLACKWELL
|
|
| Date |
2016-01-14T10:48:17Z
2016-01-14T10:48:17Z 2015 |
|
| Type |
Article
|
|
| Identifier |
RANDOM STRUCTURES & ALGORITHMS, 47(1)99-108
1042-9832 1098-2418 http://dx.doi.org/10.1002/rsa.20532 http://dspace.library.iitb.ac.in/jspui/handle/100/17398 |
|
| Language |
en
|
|