Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  129.31402
Autor:  Erdös, Pál; Neveu, J.; Rényi, Alfréd
Title:  An elementary inequality between the probabilities of events (In English)
Source:  Math. Scand. 13, 90-104 (1963).
Review:  The reviewer (Zbl 064.13005) has proved that for any n events A1,A2,...,An such that Pr(Ai) = \omega1 for i = 1,2,...,n and Pr(Ai \cap Aj) = \omega2 for i \ne j we have the inequality

\omega2 \geq \omega12-{\omega1(1-\omega1) \over n-1}+{(n\omega1-[n\omega1]) (1-n\omega1+[n \omega1]) \over n(n-1)}    (1)

with [n\omega1] denoting the integral part of n\omega1, and that this inequality is an equality for some collection of events A1, A2,...,An whatever \omega1 and n.
Here the authors consider the closely related more general problem of the determination, for any natural n and a in (0,1), of the constant \epsilonn (\alpha) defined as the least real number \epsilon such that for any collection of events A1,A2,...,An subject to the only condition (2) Pr(Ai \cap Aj) \leq \alpha2 for i \ne j we have the inequality sum Pr(Ai) \leq n\alpha+\epsilon. With \nu denoting the largest integer such that \nu(\nu-1) \leq n(n-1)\alpha2 the constant sought for is found to be given by

\epsilonn(\alpha) = 1/2 (1-\alpha)+(n \alpha-\nu) ((n-1)\alpha-\nu)/2 \nu.

The second term in this formula vanishes if n\alpha or (n-1)\alpha is an integer; otherwise for n ––> oo it is of the order of 1/n. An explicit extremal collection of events A1,A2,...,An is constructed in the case of \alpha = 1/2 and n \equiv 3 (mod 4) by the use of the method of quadratic residues.
Reviewer:  S.Zubrzycki
Classif.:  * 60C05 Combinatorial probability
                   60E05 General theory of probability distributions
Index Words:  probability theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page