Tight lower bound on the probability of a binomial exceeding its expectation

Spencer Greenberg; Mehryar Mohri

doi:10.1016/j.spl.2013.12.009

Tight lower bound on the probability of a binomial exceeding its expectation

Spencer Greenberg, Mehryar Mohri

Computer Science

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

Abstract

We give the proof of a tight lower bound on the probability that a binomial random variable exceeds its expected value. The inequality plays an important role in a variety of contexts, including the analysis of relative deviation bounds in learning theory and generalization bounds for unbounded loss functions.

Original language	English (US)
Pages (from-to)	91-98
Number of pages	8
Journal	Statistics and Probability Letters
Volume	86
Issue number	1
DOIs	https://doi.org/10.1016/j.spl.2013.12.009
State	Published - Mar 2014

Keywords

Binomial distribution
Expected value
Lower bound
Machine learning
Relative deviation

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty

Access to Document

10.1016/j.spl.2013.12.009

Cite this

@article{cdcc7d1f912d493aa3a50c33de539d32,

title = "Tight lower bound on the probability of a binomial exceeding its expectation",

abstract = "We give the proof of a tight lower bound on the probability that a binomial random variable exceeds its expected value. The inequality plays an important role in a variety of contexts, including the analysis of relative deviation bounds in learning theory and generalization bounds for unbounded loss functions.",

keywords = "Binomial distribution, Expected value, Lower bound, Machine learning, Relative deviation",

author = "Spencer Greenberg and Mehryar Mohri",

year = "2014",

month = mar,

doi = "10.1016/j.spl.2013.12.009",

language = "English (US)",

volume = "86",

pages = "91--98",

journal = "Statistics and Probability Letters",

issn = "0167-7152",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Tight lower bound on the probability of a binomial exceeding its expectation

AU - Greenberg, Spencer

AU - Mohri, Mehryar

PY - 2014/3

Y1 - 2014/3

N2 - We give the proof of a tight lower bound on the probability that a binomial random variable exceeds its expected value. The inequality plays an important role in a variety of contexts, including the analysis of relative deviation bounds in learning theory and generalization bounds for unbounded loss functions.

AB - We give the proof of a tight lower bound on the probability that a binomial random variable exceeds its expected value. The inequality plays an important role in a variety of contexts, including the analysis of relative deviation bounds in learning theory and generalization bounds for unbounded loss functions.

KW - Binomial distribution

KW - Expected value

KW - Lower bound

KW - Machine learning

KW - Relative deviation

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

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

U2 - 10.1016/j.spl.2013.12.009

DO - 10.1016/j.spl.2013.12.009

M3 - Article

AN - SCOPUS:84893083297

SN - 0167-7152

VL - 86

SP - 91

EP - 98

JO - Statistics and Probability Letters

JF - Statistics and Probability Letters

IS - 1

ER -

Tight lower bound on the probability of a binomial exceeding its expectation

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this