Fréchet inequalities

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

In probabilistic logic, the Fréchet inequalities, also known as the Boole–Fréchet inequalities, are rules implicit in the work of George Boole[1][2] and explicitly derived by Maurice Fréchet[3][4] that govern the combination of probabilities about logical propositions or events logically linked together in conjunctions (AND operations) or disjunctions (OR operations) as in Boolean expressions or fault or event trees common in risk assessments, engineering design and artificial intelligence. These inequalities can be considered rules about how to bound calculations involving probabilities without assuming independence or, indeed, without making any dependence assumptions whatsoever. The Fréchet inequalities are closely related to the Boole–Bonferroni–Fréchet inequalities, and to Fréchet bounds.

If Ai are logical propositions or events, the Fréchet inequalities are

Probability of a logical conjunction (&)
max(0, P(A1) + P(A2) + ... + P(An) − (n − 1)) ≤ P(A1 & A2 & ... & An) ≤ min(P(A1), P(A2), ..., P(An)),
Probability of a logical disjunction (∨)
max(P(A1), P(A2), ..., P(An)) ≤ P(A1 ∨ A2 ∨ ... ∨ An) ≤ min(1, P(A1) + P(A2) + ... + P(An)),

where P( ) denotes the probability of an event or proposition. In the case where there are only two events, say A and B, the inequalities reduce to

Probability of a logical conjunction (&)
max(0, P(A) + P(B) − 1) ≤ P(A & B) ≤ min(P(A), P(B)),
Probability of a logical disjunction (∨)
max(P(A), P(B)) ≤ P(A ∨ B) ≤ min(1, P(A) + P(B)).

The inequalities bound the probabilities of the two kinds of joint events given the probabilities of the individual events. For example, if A is "has lung cancer", and B is "has mesothelioma", then A & B is "has both lung cancer and mesothelioma", and A ∨ B is "has lung cancer or mesothelioma or both diseases", and the inequalities relate the risks of these events.

Note that logical conjunctions are denoted in various ways in different fields, including AND, &, ∧ and graphical AND-gates. Logical disjunctions are likewise denoted in various ways, including OR, |, ∨, and graphical OR-gates. If events are taken to be sets rather than logical propositions, the set-theoretic versions of the Fréchet inequalities are

Probability of an intersection of events
max(0,P(A) + P(B) − 1) ≤ P(A ∩ B) ≤ min(P(A), P(B)),
Probability of a union of events
max(P(A), P(B)) ≤ P(A ∪ B) ≤ min(1, P(A) + P(B)).

Numerical examples

If the probability of an event A is P(A) = a = 0.7, and the probability of the event B is P(B) = b = 0.8, then the probability of the conjunction. i.e., the joint event A & B, is surely in the interval

  P(A & B) = [max(0, a + b − 1), min(a, b)]
= [max(0, 0.7 + 0.8−1), min(0.7, 0.8)]
= [0.5, 0.7].

Likewise, the probability of the disjunction A ∨ B is surely in the interval

  P(A ∨ B) = [max(a, b), min(1, a + b)]
= [max(0.7, 0.8), min(1, 0.7 + 0.8)]
= [0.8, 1].

These intervals are contrasted with the results obtained from the rules of probability assuming independence, where the probability of the conjunction is P(A & B) = a × b = 0.7 × 0.8 = 0.56, and the probability of the disjunction is P(A ∨ B) = a + b − a × b = 0.94.

When the marginal probabilities are very small (or large), the Fréchet intervals are strongly asymmetric about the analogous results under independence. For example, suppose P(A) = 0.000002 = 2×10−6 and P(B) = 0.000003 = 3×10−6. Then the Fréchet inequalities say P(A & B) is in the interval [0, 2×10−6], and P(A ∨ B) is in the interval [3×10−6, 5×10−6]. If A and B are independent, however, the probability of A & B is 6×10−12 which is, comparatively, very close to the lower limit (zero) of the Fréchet interval. Similarly, the probability of A ∨ B is 4.999994×10−6, which is very close to the upper limit of the Fréchet interval. This is what justifies the rare-event approximation[5] often used in reliability theory.


Proofs

The proofs are elementary. Recall that P(A ∨ B) = P(A) + P(B) − P(A & B), which implies P(A) + P(B) − P(A ∨ B) = P(A & B). Because all probabilities are no bigger than 1, we know P(A ∨ B) ≤ 1, which implies that P(A) + P(B) − 1 ≤ P(A & B). Because all probabilities are also positive we can similarly say 0 ≤ P(A & B), so max(0, P(A) + P(B) − 1) ≤ P(A & B). This gives the lower bound on the conjunction.

To get the upper bound, recall that P(A & B) = P(A|B) P(B) = P(B|A) P(A). Because P(A|B) ≤ 1 and P(B|A) ≤ 1, we know P(A & B) ≤ P(A) and P(A & B) ≤ P(B). Therefore, P(A & B) ≤ min(P(A), P(B)), which is the upper bound.

The best-possible nature of these bounds follows from observing that they are realized by some dependency between the events A and B. Comparable bounds on the disjunction are similarly derived.

Extensions

When the input probabilities are themselves interval ranges, the Fréchet formulas still work as a probability bounds analysis. Hailperin[2] considered the problem of evaluating probabilistic Boolean expressions involving many events in complex conjunctions and disjunctions. Some[6][7] have suggested using the inequalities in various applications of artificial intelligence and have extended the rules to account for various assumptions about the dependence among the events. The inequalities can also be generalized to other logical operations, including even modus ponens.[6][8] When the input probabilities are characterized by probability distributions, analogous operations that generalize logical and arithmetic convolutions without assumptions about the dependence between the inputs can be defined based on the related notion of Fréchet bounds.[7][9][10]

See also

References

  1. ↑ Boole, G. (1854). An Investigation of the Laws of Thought, On Which Are Founded the Mathematical Theories of Logic and Probability. Walton and Maberly, London. See Boole's "major" and "minor" limits of a conjunction on page 299.
  2. ↑ 2.0 2.1 Hailperin, T. (1986). Boole's Logic and Probability. North-Holland, Amsterdam.
  3. ↑ Fréchet, M. (1935). Généralisations du théorème des probabilités totales. Fundamenta Mathematica 25: 379–387.
  4. ↑ Fréchet, M. (1951). Sur les tableaux de corrélation dont les marges sont données. Annales de l'Université de Lyon. Section A: Sciences mathématiques et astronomie 9: 53–77.
  5. ↑ Collet, J. (1996). Some remarks on rare-event approximation. IEEE Transactions on Reliability 45: 106–108.
  6. ↑ 6.0 6.1 Wise, B.P., and M. Henrion (1986). A framework for comparing uncertain inference systems to probability. Uncertainty in Artificial Intelligence, edited by L.N. Kanal and J.F. Lemmer, Elsevier Science Publishers, B.V. North-Holland, Amsterdam.
  7. ↑ 7.0 7.1 Williamson, R.C. (1989). Probabilistic Arithmetic. Dissertation, University of Queensland.
  8. ↑ Wagner, C.G. (2004). Modus tollens probabilized. British Journal for the Philosophy of Science 55: 747–753.
  9. ↑ Weisstein, Eric W. Fréchet bounds. MathWorld--A Wolfram Web Resource.
  10. ↑ Rüschendorf, L. (1991). Fréchet-bounds and their applications. Pages 151–187 in Advances in Probability Distributions with Given Marginals, Mathematics and Its Applications 67, edited by G. Dall'Aglio, S. Kotz and G. Salinetti, Kluwer, Dordrecht.
Retrieved from "https://infogalactic.com/w/index.php?title=Fréchet_inequalities&oldid=511173080"