Fréchet inequalities

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

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

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⁻⁶ and P(B) = 0.000003 = 3×10⁻⁶. Then the Fréchet inequalities say P(A & B) is in the interval [0, 2×10⁻⁶], and P(A ∨ B) is in the interval [3×10⁻⁶, 5×10⁻⁶]. If A and B are independent, however, the probability of A & B is 6×10⁻¹² 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⁻⁶, which is very close to the upper limit of the Fréchet interval. This is what justifies the rare-event approximation 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 considered the problem of evaluating probabilistic Boolean expressions involving many events in complex conjunctions and disjunctions. Some 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. 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.

Quantum Fréchet bounds

It is interesting that similar bounds hold also in Quantum Mechanics in the case of separable quantum systems and that entangled states violate these bounds. Let us consider a composite quantum system. In particular, we focus on a composite quantum system AB made by two finite subsystems denoted as A and B. Assume that we know the density matrix of the subsystem A, i.e., ρ A that is a trace-one positive definite matrix in C h n × n (the space of Hermitian matrices of dimension n × n ), and the density matrix of subsystem B denoted as ρ B . We can think of ρ A and ρ B as the marginals of the subsystems A and B. From the knowledge of these marginals, we want to infer something about the joint ρ A B in C h n m × n m . We restrict our attention to joint ρ A B that are separable. A density matrix on a composite system is separable if there exist p k ≥ 0 , { ρ 1 k } and { ρ 2 k } which are mixed states of the respective subsystems such that

where

Otherwise ρ A B is called an entangled state.

For separable density matrices ρ A B in C h n m × n m the following Fréchet like bounds hold:

ρ A B ≤ ρ A ⊗ I m  and  ρ A B ≤ I n ⊗ ρ B ,

and

ρ A B ≥ ρ A ⊗ I m + I n ⊗ ρ B − I n m  and  ρ A B ⪈ 0.

where the inequalities are matrix inequalities, ⊗ denotes the tensor product and I x the identity matrix of dimension x . It is evident that structurally the above inequalities are analogues of the classical Fréchet bounds for the logical conjunction. It is also worth to notice that when the matrices ρ A , ρ B and ρ A B are restricted to be diagonal, we obtain the classical Fréchet bounds.

The upper bound is known in Quantum Mechanics as reduction criterion for density matrices; it was first proven by and independently formulated by. The lower bound has been obtained in that provides a Bayesian interpretation of these bounds.

Numerical examples

We have observed that when the matrices ρ A , ρ B and ρ A B are restricted to be diagonal, we obtain the classical Fréchet bounds. To show that, let us consider again the previous numerical example. Consider ρ A = d i a g ( p a , p a ¯ ) = d i a g ( 0.7 , 0.3 ) , ρ B = d i a g ( p b , p b ¯ ) = d i a g ( 0.8 , 0.2 ) and then we have that

which for instance means that max ( 0.7 + 0.8 − 1 , 0 ) ≤ p a b ≤ min ( 0.7 , 0.8 ) , i.e., p a b ∈ [ 0.5 , 0.7 ] .

It is worth to point out that entangled states violate the above Fréchet bounds. Consider for instance the entangled density matrix (which is not separable):

which has marginal ρ A = ρ B = d i a g ( 1 / 2 , 1 / 2 ) . Entangled states are not separable and it can easily be verified that

since the resulting matrices have one negative eigenvalue.

Another example of violation of probabilistic bounds is provided by the famous Bell's inequality: entangled states exhibit a form of ``stochastic dependence stronger than the strongest classical dependence: and in fact they violate Fréchet like bounds.