×

An elementary analysis of the probability that a binomial random variable exceeds its expectation. (English) Zbl 1392.60022

Summary: We give an elementary proof of the fact that a binomial random variable \(X\) with parameters \(n\) and \(0.29 / n \leq p < 1\) with probability at least \(1 / 4\) strictly exceeds its expectation. We also show that for \(1 / n \leq p < 1 - 1 / n\), \(X\) exceeds its expectation by more than one with probability at least 0.0370. Both probabilities approach \(1 / 2\) when \(n p\) and \(n(1 - p)\) tend to infinity.

MSC:

60E15 Inequalities; stochastic orderings
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Becchetti, Luca; Clementi, Andrea E. F.; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca, Simple dynamics for plurality consensus, Distrib. Comput., 30, 293-306, (2017) · Zbl 1419.68027
[2] Doerr, Benjamin; Gießen, Christian; Witt, Carsten; Yang, Jing, The (1+\(\lambda\)) evolutionary algorithm with self-adjusting mutation rate, (Genetic and Evolutionary Computation Conference, GECCO 2017, (2017), ACM), 1351-1358, Full version available at http://arxiv.org/abs/1704.02191
[3] Feller, William, An introduction to probability theory and its applications, vol. II, (1971), Wiley · Zbl 0219.60003
[4] Greenberg, Spencer; Mohri, Mehryar, Tight lower bound on the probability of a binomial exceeding its expectation, Statist. Probab. Lett., 86, 91-98, (2014) · Zbl 1293.60024
[5] Kaas, R.; Buhrman, J. M., Mean, Median and mode in binomial distributions, Stat. Neerl., 34, 13-18, (1980) · Zbl 0444.62021
[6] Karppa, Matti; Kaski, Petteri; Kohonen, Jukka, A faster subquadratic algorithm for finding outlier correlations, (Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, (2016), SIAM), 1288-1305 · Zbl 1397.68218
[7] Mitzenmacher, Michael, Morgan, Tom, Reconciling graphs and sets of sets. CoRR, abs/1707.05867; Mitzenmacher, Michael, Morgan, Tom, Reconciling graphs and sets of sets. CoRR, abs/1707.05867
[8] Neumann, P., Über den Median der binomial- and poissonverteilung, Wiss. Z. Tech. Univ. Dresden, 19, 29-33, (1966) · Zbl 0288.60011
[9] Pelekis, Christos, A lower bound on binomial tails: an approach via tail conditional expectations. ArXiv e-prints, 1609.06651, 2016.; Pelekis, Christos, A lower bound on binomial tails: an approach via tail conditional expectations. ArXiv e-prints, 1609.06651, 2016.
[10] Pelekis, Christos; Ramon, Jan, A lower bound on the probability that a binomial random variable is exceeding its mean, Statist. Probab. Lett., 119, 305-309, (2016) · Zbl 1397.60055
[11] Rigollet, Philippe; Tong, Xin, Neyman-Pearson classification, convexity and stochastic constraints, J. Mach. Learn. Res., 12, 2831-2855, (2011) · Zbl 1280.62080
[12] Robbins, Herbert, A remark on stirling’s formula, Amer. Math. Monthly, 62, 26-29, (1955) · Zbl 0068.05404
[13] Slud, Eric V., Distribution inequalities for the binomial law, Ann. Probab., 5, 404-412, (1977) · Zbl 0358.60015
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.