Premium
A tail bound for read‐ k families of functions
Author(s) -
Gavinsky Dmitry,
Lovett Shachar,
Saks Michael,
Srinivasan Srikanth
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20532
Subject(s) - struct , random variable , modulo , chernoff bound , mathematics , sum of normally distributed random variables , combinatorics , variables , upper and lower bounds , discrete mathematics , statistics , convergence of random variables , computer science , mathematical analysis , programming language
We prove a Chernoff‐like large deviation bound on the sum of non‐independent random variables that have the following dependence structure. The variablesY 1 , … , Y rare arbitrary [0,1]‐valued functions of independent random variablesX 1 , … , X m , modulo a restriction that every X i influences at most k of the variablesY 1 , … , Y r . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 99–108, 2015