Suppose we have $n$ events $X_1, X_2, ..., X_n$ and we write down every possible conditional probability we can form from a subset of these events. So we're interested in all probabilities such as:

  • $P(X_i)$,
  • $P(X_i, X_j), \; i \neq j$
  • $P(X_i | X_j), \; i \neq j$
  • $P(X_i, X_j, X_k), \; i \neq j \neq k$
  • $P(X_i | X_j, X_k), \; i \neq j \neq k$
  • $P(X_i, X_j | X_k), \; i \neq j \neq k$
  • ...

Here, $X_i, X_j$ is shorthand for the logical AND operator ($X_i \wedge X_j$), which is the only binary operator between the $X_i$ I'm interested in here. Obviously, many of these probabilities are related to each other, such as

$P(X_1, X_2) = P(X_1 | X_2) P(X_2)$.

My question is: how many of these probabilities would you need to specify (i.e., give numerical values) at a minimum to work out all other probabilities with the standard laws of probability?

  • $\begingroup$ it's an interesting question but still not that clear to me. do you want all the joint ( and unconditional ) probabilities of two of the X_i's or ALL the joint probabilities of any of number of the X_i's ? Either way, I still don't know the answer but it's interesting to think about so I want to know what to think about. Also, it sounds like these variables have some unknown joint distribution, correct ? ( clearly,: they're not independent ) $\endgroup$ – mlofton May 9 '19 at 17:58
  • 1
    $\begingroup$ @mlofton I am interested in all joint probabilities, not just of pairs of $X_i$. And yes, the joint distribution is generally unknown. $\endgroup$ – Sjoerd Smit May 9 '19 at 22:07

The conditional probabilities completely determine the joint probability distribution, at least insofar as it can be revealed by these events, and (obviously) are determined by it. The crux of the matter is to find the set algebra determined by these events $\mathcal X = \{X_1, X_2, \ldots, X_n\}.$

If the $X_i$ aren't already subsets of a common set $\Omega,$ define $$\Omega = \bigcup_{X\in\mathcal X} X,$$ the union of all the events, which is allowed by the axioms of set theory. As a matter of notation, for any $\mathcal{A}\subset \Omega,$ write $\mathcal{A}^0 = \Omega\setminus \mathcal{A}$ for its complement and $\mathcal{A}^1=\mathcal{A}$ for the set itself.

Probability calculations deal with complements of events and unions of disjoint events. We therefore need to construct a collection of sets that is closed under such operations and includes the $X_i.$ To this end construct all $2^n$ possible intersections of the $X_i$ and their complements. That is, for each sequence $\mathbf{e}=(e_1,e_2, \ldots, e_n)$ of zeros and ones, construct

$$\mathcal{X}(\mathbf{e}) = X_1^{e_1} \cap X_2^{e_2} \cap \cdots \cap X_n^{e_n}.$$

If you wish to imagine a Venn diagram of the $X_i$ (in two or more dimensions) the various $\mathcal{X}(\mathbf{e})$ are the connected components of the diagram after the boundaries of the circles (or hyperspheres) have been removed: $e_i=1$ means you're inside $X_i$ and $e_i=0$ means you are outside it.

There might be fewer then $2^n$ distinct nonempty components. (A worked example appears at the end of this post.) Let their number be $N,$ which therefore lies between $0$ and $2^n$ inclusive. These are the atomic sets determined by $\mathcal X.$ Clearly, distinct atomic sets are disjoint.

From now on, assume $\Omega$ is not empty, so that $N \ge 1.$

A probability measure $\mathbb{P}$ assigns non-negative numbers to the $X_i$ (and all sets that can be formed from them and $\Omega$ by means of countable numbers of complements, intersections, and unions). Let this collection of sets generated by $\Omega$ and $\mathcal X$ be called $\mathfrak{S}.$ It is the set of events determined by the $X_i.$ Only events need to be given probabilities.

The values of $\mathbb{P}$ are limited only by two axioms:

  1. $\mathbb{P}(\Omega) = 1.$

  2. When $\mathcal{E}_i \in \mathfrak{S}$ are disjoint, $$\mathbb{P}\left(\bigcup_i \mathcal{E}_i\right) = \sum_i \mathbb{P}(\mathcal {E}_i).$$

Only axiom $(1)$ provides any numerical constraint. Here's the proof. First, note that the intersection of any $\mathcal{E}_i$ in axiom $(2)$ with any of the atomic sets $\mathcal{X}(\mathbf{e})$ is either empty or $\mathcal{X}(\mathbf{e})$ itself. From this it follows that each $\mathcal{E}_i$ is the union of the atomic sets it contains--and those atomic sets, as previously noted, are disjoint. Therefore, the probabilities of the atomic sets determine all the probabilities that can appear in axiom $(2)$.

Because $\Omega$ is the union of all the atomic sets, axioms $(1)$ and $(2)$ together imply the sum of the atomic probabilities is unity. Moreover, the demonstration shows more:

Any event is a union of atomic events. The probability of an event is the sum of the probabilities of the atomic sets within it.

Consequently, if we enumerate the atomic sets once and for all as $\mathcal{A}_1, \ldots, \mathcal{A}_N,$ and write

$$p_i = \mathbb{P}(\mathcal{A}_i)$$

for their probabilities, then

All probability measures on $\mathfrak S$ are determined by vectors $(p_1,p_2\ldots, p_N)$ of non-negative numbers that sum to unity, where $N$ is the number of atomic events determined by the $X_i.$

That imposes one linear equality on $N \ge 1$ independent numbers. Linear algebra tells us the solutions form a manifold of $N-1$ dimensions. Thus,

The number of probabilities that can be independently specified is one less than the number of atomic events determined by $\mathcal X.$

Let's do an example. Within the "universal set" $\Omega=\{0,1,2,3\},$ suppose $X_1 = \{0\},$ $X_2 = \{1,2\},$ and $X_3 = \{0,1,2\}.$ The atomic sets are (in arbitrary order)

$$\mathcal{A}_1 = \{0\},\quad \mathcal{A}_2 = \{1,2\},\quad \mathcal{A}_3 = \{3\}.$$

Consequently there are $2^N=8$ events. They are

$$\eqalign{ \mathfrak{S} &= \{\emptyset,&\{0\}=X_1,&\{1,2\}=X_2,&\{0,1,2\}=X_3,&\{3\},&\{0,3\},&\{1,2,3\},&\{0,1,2,3\}=\Omega\}\\ &= \{\emptyset,&\mathcal{A}_1,&\mathcal{A}_2,&\mathcal{A}_1\cup\mathcal{A}_2,&\mathcal{A}_3,&\mathcal{A}_1\cup\mathcal{A}_3,&\mathcal{A}_2\cup\mathcal{A}_3,&\mathcal{A}_1\cup\mathcal{A}_2\cup\mathcal{A}_3\}. }$$

Thus $N=3$ and it takes $N-1=2$ numbers to determine a probability measure. You could take them to be, say, $p_1 =\mathbb{P}\left(\{0\}\right)$ and $p_2 = \mathbb{P}(\left(\{1,2\}\right)$ and compute $p_3 = 1 - (p_1+p_2)$ from axiom $(2).$ The axioms force you to choose both $p_i$ to be nonnegative and they cannot sum to any more than $1.$

Finally, note that $\mathbb{P}(X_1)=p_1,$ $\mathbb{P}(X_2)=p_2,$ and $\mathbb{P}(X_3) = p_1+p_2.$ This shows that you cannot necessarily assign probabilities freely to each of the original sets $X_i:$ the axioms may force constraints on them. That's why considerations of the set algebra are unavoidable, because they reveal what those constraints are.

  • 1
    $\begingroup$ very nice. thanks. $\endgroup$ – mlofton May 10 '19 at 1:58

To study this matter, I can recommend the book by Paul Pfeiffer 'Applied Probability'. In Chapter 2, he discusses Minterm Analysis in considerable detail. Quoting from Pfeiffer : "A fundamental problem in elementary probability is to find the probability of a logical (Boolean) combination of a finite class of events, when the probabilities of certain other combinations are known. If we partition an event F into component events whose probabilities can be determined, then the additivity property implies the probability of F is the sum of these component probabilities. Frequently, the event F is a Boolean combination of members of a finite class say, {A, B, C} or {A, B, C, D} . For each such finite class, there is a fundamental partition determined by the class. The members of this partition are called minterms. Any Boolean combination of members of the class can be expressed as the disjoint union of a unique subclass of the minterms. If the probability of every minterm in this subclass can be determined, then by additivity the probability of the Boolean combination is determined." Pfeiffer provides many interesting examples.

  • $\begingroup$ +1 Welcome to our site, and thank you for fleshing out your original answer into a useful and interesting reply. $\endgroup$ – whuber May 11 '19 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.