A Priori Error Estimates for the Method of Inclusion-Exclusion with Applications
Klaus D. Heidtmann · SIAM Journal on Applied Mathematics · 1984
The method of inclusion-exclusion can be used to obtain successive upper and lower bounds on the probability of the occurrence of complex events. Usually only the first upper and the first lower bound are considered. But as they can be crude, further bounds must not be excluded from methodical studies and practical computations. In this paper the errors of all inclusion-exclusion approximations are estimated. As a priori error estimates are independent of the actual computation of the bounds, they can precede. So the order of the approximation, being at least as close to the exact value as demanded, can be determined in advance. As a second point, the paper shows how to apply the method of inclusion-exclusion and the discussed a priori error bounds skillfully to approximate the reliability and the probability of connectivity for random graphs representing various structures.