Best lower bound on the probability of a binomial exceeding its expectation. (English) Zbl 1483.60035
Let \(X\sim Bin\, (n,p)\), and \(c = \ln(4/3)\). In this article, the author proves that \[\mbox{ if} \quad \frac{c}{n}\leq p < 1, \quad \mbox{ then } \quad P\left(X > E[X]\right) \geq \frac{1}{4}. \] The value of \(c\) is optimal. This result is a slight improvement of a result of S. Greenberg and M. Mohri [Stat. Probab. Lett. 86, 91–98 (2014; Zbl 1293.60024)].
“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.”
“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.”
Reviewer: Italo Simonelli (Durham)
Citations:
Zbl 1293.60024References:
| [1] | Alon, N.; Hanneke, S.; Holzman, R.; Moran, S., A theory of PAC learnability of partial concept classes (2021), arXiv:2107.08444, arXiv:2107.08444 (cs.LG) |
| [2] | Anderson, T. W.; Samuels, S. M., Some inequalities among binomial and Poisson probabilities, (Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Statistics, vol. 1 (1967), University of California Press: University of California Press Berkeley, Calif.), 1-12, URL: https://projecteuclid.org/euclid.bsmsp/1200512976 · Zbl 0232.60008 |
| [3] | Andonova Jaeger, S., Generalization bounds and complexities based on sparsity and clustering for convex combinations of functions from random classes, J. Mach. Learn. Res., 6, 307-340 (2005) · Zbl 1222.62072 |
| [4] | Anthony, M.; Shawe-Taylor, J., A result of Vapnik with applications, Discrete Appl. Math., 47, 207-217 (1993) · Zbl 0801.68147 |
| [5] | Greenberg, S.; Mohri, M., Tight lower bound on the probability of a binomial exceeding its expectation, Statist. Probab. Lett., 86, 91-98 (2014), URL: http://dx.doi.org/10.1016/j.spl.2013.12.009 · Zbl 1293.60024 |
| [6] | Haussler, D., Decision theoretic generalizations of the PAC model for neural net and other learning applications, Inform. and Comput., 100, 78-150 (1992), URL: http://dx.doi.org/10.1016/0890-5401(92)90010-D · Zbl 0762.68050 |
| [7] | Hoeffding, W., On the distribution of the number of successes in independent trials, Ann. Math. Statist., 27, 713-721 (1956), URL: http://dx.doi.org/10.1214/aoms/1177728178 · Zbl 0073.13902 |
| [8] | Kontorovich, A.; Pinelis, I., Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model, Ann. Statist, 47, 2822-2854 (2019) · Zbl 1447.62070 |
| [9] | Korolev, V.; Shevtsova, I., An improvement of the Berry-Esseen inequality with applications to Poisson and mixed Poisson random sums, Scand. Actuar. J., 8, 1-105 (2012) · Zbl 1277.60042 |
| [10] | Pinelis, I., Monotonicity properties of the Poisson approximation to the binomial distribution, Statist. Probab. Lett., 167, Article 108901 pp. (2020), 7 · Zbl 1453.60062 |
| [11] | Rigollet, P.; Tong, X., Neyman-Pearson classification, convexity and stochastic constraints, J. Mach. Learn. Res., 12, 2831-2855 (2011) · Zbl 1280.62080 |
| [12] | Valiant, L. G., A theory of the learnable, Commun. ACM, 27, 1134-1142 (1984) · Zbl 0587.68077 |
| [13] | Vapnik, V. N., Statistical learning theory, (Adaptive and Learning Systems for Signal Processing, Communications and Control (1998), John Wiley & Sons, Inc., A Wiley-Interscience Publication: John Wiley & Sons, Inc., A Wiley-Interscience Publication New York) · Zbl 0935.62007 |
| [14] | Vapnik, V., Estimation of dependences based on empirical data, (Information Science and Statistics (2006), Springer: Springer New York), Reprinted from: 1982 edition, Afterword of 2006: Empirical Inference Science · Zbl 1118.62002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
