A tail bound for read‐ k  families of functions | Zendy

Gavinsky Dmitry | Zendy; Lovett Shachar | Zendy; Saks Michael | Zendy; Srinivasan Srikanth | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research