Approximate inclusion-exclusion (Q1174115)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Approximate inclusion-exclusion
scientific article

    Statements

    Approximate inclusion-exclusion (English)
    0 references
    0 references
    0 references
    0 references
    25 June 1992
    0 references
    The inclusion-exclusion formula \[ | A_ 1\cup A_ 2\cup\dots\cup A_ n|=\sum_ i| A_ i| -\sum_{i<j}| A_ i\cap A_ j|+\sum_{i<j<k}| A_ i\cap A_ j\cap A_ k|-\dots+(- 1)^ n| A_ 1\cap\dots\cap A_ n|, \] may be used to find the size of the union with the fact that it has an exponential number of terms and that all terms are necessary. Moreover if the size of intersection of any sub-collection is missing then the size of union cannot be computed. In this paper the approximate size of the union when intersection sizes are known for only some of them, or when these quantities are given to within some error or both, have been estimated under certain conditions with several applications to Boolean functions.
    0 references
    0 references
    inclusion-exclusion formula
    0 references
    0 references