A tail bound for read‐k families of functions
Copyright policy )A tail bound for read‐k families of functions
AbstractWe prove a Chernoff‐like large deviation bound on the sum of non‐independent random variables that have the following dependence structure. The variables are arbitrary [0,1]‐valued functions of independent random variables , modulo a restriction that every Xi influences at most k of the variables . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 99–108, 2015
- Rutgers University New Brunswick United States
- Indian Institute of Technology Bombay India
- University of California, San Francisco United States
- Indian Institue of Technology, Bombay India
- Czech Academy of Sciences Czech Republic
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Entropy, Information Theory, Shearer's lemma, Computation Theory & Mathematics, tail bound, Concentration Inequalities, FOS: Mathematics, deviation bound, Shearer'S Lemma, information theory, limited independence, Statistics, Probability (math.PR), Computation Theory and Mathematics, Chernoff bounds, Pure Mathematics, Chernoff Bounds, Chernoff-like large deviation bound, Brain Disorders, Limited Independence, random variables, Large deviations, Mathematics - Probability, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Entropy, Information Theory, Shearer's lemma, Computation Theory & Mathematics, tail bound, Concentration Inequalities, FOS: Mathematics, deviation bound, Shearer'S Lemma, information theory, limited independence, Statistics, Probability (math.PR), Computation Theory and Mathematics, Chernoff bounds, Pure Mathematics, Chernoff Bounds, Chernoff-like large deviation bound, Brain Disorders, Limited Independence, random variables, Large deviations, Mathematics - Probability, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).25 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!