Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 7 (2002) > Paper 9 open journal systems 


Inclusion-Exclusion Redux

David Kessler, Bar-Ilan University
Jeremy Schiff, Bar-Ilan University


Abstract
We present a reordered version of the inclusion-exclusion principle, which is useful when computing the probability of a union of events which are close to independent. The advantages of this formulation are demonstrated in the context of 3 classic problems in combinatorics.


Full text: PDF

Pages: 85-96

Published on: March 11, 2002
Bibliography
  1. G.Boole, An Investigation of The Laws of Thought on which are Founded the Mathematical Theories of Logic and Probabilities , Macmillan (1854), reprinted Dover (1958), MR 19,1d
  2. N.Linial and N.Nisan, Approximate Inclusion-Exclusion, Combinatorica 10 (1990) 349-365, MR 92d:05167
  3. J.Kahn, N.Linial and A.Samorodnitsky, Inclusion-Exclusion: Exact and Approximate, Combinatorica 16 (1996) 465-477, MR 98b:05008
  4. A.Samorodnitsky, Approximate Inclusion-Exclusion and Orthogonal Polynomials, preprint.
  5. S.Janson, Poisson Approximation for Large Deviations, Random Structures and Algorithms 1 (1990) 221-229, MR 93a:60041
  6. P.Erdös and L.Lovász, Problems and Results on 3-chromatic Hypergraphs and Some Related Questions, in "Infinite and Finite Sets", ed. A.Hajnal et al., North Holland (1975), MR 52 #2938
  7. N.Alon and J.Spencer, The Probablistic Method, Wiley (1992), MR 95c:05113
  8. D.Q.Naiman and H.P.Wynn, Inclusion-Exclusion-Bonferroni Identities and Inequalities for Discrete Tube-Like Problems via Euler Characteristics, Ann.Stat. 20 (1992) 43-76, MR 93b:60035
  9. D.Q.Naiman and H.P.Wynn, Abstract Tubes, Improved Inclusion-Exclusion Identities and Inequalities and Importance Sampling, Ann.Stat. 25 (1997) 1954-1983, MR 99h:60034
  10. D.Q.Naiman and H.P.Wynn, Improved Inclusion-Exclusion Inequalities for Simplex and Orthant Arrangements, JIPAM J.Inequal.Pure Appl. Math 2 (2001) article 18, MR 1 873 858
  11. J.Riordan, An Introduction to Combinatorial Analysis, Wiley (1958), MR 20 #3077
  12. F.F.Knudsen and and I. Skar, On the Asymptotic Solution of a Card-Matching Problem, Math. Mag. 69 (1996) 190-197, MR 97f:15013
  13. W.Feller, An Introduction to Probability Theory and its Applications, third edition, Wiley (1968), MR 37 #3604
  14. E.P.Miles, Jr., Generalized Fibonacci Numbers and Associated Matrices, Amer. Math. Monthly 67 (1960) 745-752, MR 23 #A846
  15. R. Savit and M.L.Green, Time Series and Dependent Variables, Physica D 50 (1991) 95-116 (correction: Physica D 55 (1992) 234); M.L.Green and R.Savit, Dependent Variables in Broad Band Continuous Time Series, Physica D 50 (1991) 521-544, MR 92i:58172
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X