A tail bound for read-k families of functions

Dmitry Gavinsky; Shachar Lovett; Michael Saks; Srikanth Srinivasan

doi:10.1002/rsa.20532

A tail bound for read-k families of functions

Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

24 Scopus citations

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 Y₁,...,Y_r are arbitrary [0,1]-valued functions of independent random variables X₁,...,X_m, modulo a restriction that every X_i influences at most k of the variables Y₁,...,Y_r.

Original language	English (US)
Pages (from-to)	99-108
Number of pages	10
Journal	Random Structures and Algorithms
Volume	47
Issue number	1
DOIs	https://doi.org/10.1002/rsa.20532
State	Published - Aug 1 2015

All Science Journal Classification (ASJC) codes

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Keywords

Chernoff bounds
Information theory
Limited independence
Shearer's lemma

Access to Document

10.1002/rsa.20532

Cite this

@article{bccc6b3441bf499a8019d162645beff9,

title = "A tail bound for read-k families of functions",

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.",

keywords = "Chernoff bounds, Information theory, Limited independence, Shearer's lemma",

author = "Dmitry Gavinsky and Shachar Lovett and Michael Saks and Srikanth Srinivasan",

note = "Publisher Copyright: {\textcopyright} 2014 Wiley Periodicals, Inc.",

year = "2015",

month = aug,

day = "1",

doi = "10.1002/rsa.20532",

language = "English (US)",

volume = "47",

pages = "99--108",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "1",

}

TY - JOUR

T1 - A tail bound for read-k families of functions

AU - Gavinsky, Dmitry

AU - Lovett, Shachar

AU - Saks, Michael

AU - Srinivasan, Srikanth

PY - 2015/8/1

Y1 - 2015/8/1

N2 - 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.

AB - 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.

KW - Chernoff bounds

KW - Information theory

KW - Limited independence

KW - Shearer's lemma

UR - http://www.scopus.com/inward/record.url?scp=84932199657&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84932199657&partnerID=8YFLogxK

U2 - 10.1002/rsa.20532

DO - 10.1002/rsa.20532

M3 - Article

AN - SCOPUS:84932199657

SN - 1042-9832

VL - 47

SP - 99

EP - 108

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

A tail bound for read-k families of functions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this