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
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
inclusion-exclusion formula
0 references
0 references