Chapter 13Sets and the Probability of Events
In Part I (calculus) and Part II (linear algebra), we acquired “tools for following change” and “tools for handling coupled quantities all at once.” From Part III on, we finally make chance itself an object of mathematics. Tomorrow's weather, the face that shows when a die is rolled, the moment at which an atomic nucleus in a material decays—we cannot predict the result of any single occurrence exactly, but we can treat mathematically “roughly what fraction of the time it happens.” The system that defines this “fraction” rigorously and computes with it is probability theory. This chapter is its starting point, and it corresponds to the first four pages of Yasuhide Mochizuki's “Mathematics Notes: Fundamentals of Probability,” that is, to items (1) through (18). It is only four pages long, but the words introduced here—set, event, sample space, probability, addition rule, complementary event, independence, repeated trials—will form the vocabulary that runs through this entire book, from expected values (Chapter 14) to the continuous probability distributions you will meet later and the Boltzmann distribution of statistical mechanics. Short as it is, this is not a chapter to skim past; on the contrary, getting each definition exactly right, line by line, will greatly affect how well you understand everything that follows.
In fact, nearly all the tools of this chapter have already appeared in high school mathematics—the notation of sets ($\in,\subset,\cap,\cup$), Venn diagrams, the symbol $_n\mathrm{C}_r$ from permutations and combinations, and the probability $P(A)=n(A)/n(U)$ when outcomes are equally likely. What this chapter does is to take another look at these, this time in the language of events, and to forge them into a common language with no gaps and no overlaps. In Sections 13.1 and 13.2 we review the operations on sets themselves (intersection, union, complement) and their algebraic laws (De Morgan's laws), and in Section 13.3 we translate that same language of sets into the setting of probability theory, “trials” and “events.” Section 13.4 gives the definition of probability itself, and Section 13.5 introduces, one after another, the four tools used most often in practical probability computations—the addition rule, complementary events, independence, and repeated trials (binomial probability). You will notice that the same symbols ($A\cap B$, $\bar A$, and so on) are defined twice, once in the language of sets and once in the language of events; this is a deliberate design—why the same symbols may be reused (because an event is nothing other than a set built on the sample space $U$) is explained carefully in Section 13.3.
- Basic operations on sets: intersection $A\cap B$, union $A\cup B$, empty set $\emptyset$, complement $\bar A$, and its properties $\bar\emptyset=U,\ \bar U=\emptyset,\ A\cap\bar A=\emptyset,\ A\cup\bar A=U,\ \bar{\bar A}=A$
- De Morgan's laws $\overline{A\cup B}=\bar A\cap\bar B,\ \overline{A\cap B}=\bar A\cup\bar B$ and their two proofs (an intuitive proof by a color-coded Venn diagram, and a general proof by the membership conditions of elements)
- The definitions of the words that set the stage for probability theory: trial, event, sample space (whole event), empty event, and elementary event
- The definition of probability $P(A)=n(A)/n(U)$ (the classical definition of probability, when the elementary events are equally likely)
- The addition rule $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ (the general case), and $P(A\cup B)=P(A)+P(B)$ when the events are mutually exclusive ($A\cap B=\emptyset$)
- The complementary event $\bar A$ and its probability $P(\bar A)=1-P(A)$ (the star of probability computations of the “at least one” type)
- The definition of independent trials, and the repeated-trials formula $_n\mathrm{C}_r\,p^r q^{n-r}$ ($q=1-p$)—a complete derivation of how binomial probabilities are built up from independence and the combinations $_n\mathrm{C}_r$
Source notes: Yasuhide Mochizuki, Mathematics Notes: Fundamentals of Probability, pp. 1–4.
13.1 Basic Operations on Sets and Venn Diagrams
This section is a review of what you learned in High School Mathematics (AD 01), Section 1.5 (basics of sets), but since probability theory is built on this language of sets, we check the notation one symbol at a time. A set is a “collection of things.” That $\alpha$ is an element (also called a member) of a set $A$ is written $\alpha\in A$ ($\in$ means “belongs to (a set)” or “is contained in”), and that it does not belong is written $\alpha\notin A$. Also, when every element of a set $A$ is also an element of a set $U$, we say that $A$ is a subset of $U$ and write $A\subset U$. Below, we use this notation to define operations between sets—operations that make a new set from two sets.
Definition 13.1: Set
A collection of things satisfying a certain condition is called a set.
A set itself is defined in the plain words “a collection of things,” but when we are given two sets $A,B$, there are two typical ways to make a new set from them—the method of “picking out only the part common to both,” and the method of “collecting an element if it belongs to either one.”
Definition 13.2: Intersection
The set of all elements common to sets $A$ and $B$ is called the intersection of $A$ and $B$ and is denoted by
$$ A\cap B $$(The symbol $\cap$ is read “cap,” and $A\cap B$ is read “A cap B.”) Written as a logical formula, $A\cap B=\{\alpha\mid \alpha\in A\text{ and }\alpha\in B\}$.
Definition 13.3: Union
The set of all elements that belong to either of the sets $A$ or $B$ is called the union of $A$ and $B$ and is denoted by
$$ A\cup B $$(The symbol $\cup$ is read “cup,” and $A\cup B$ is read “A cup B.”) Written as a logical formula, $A\cup B=\{\alpha\mid \alpha\in A\text{ or }\alpha\in B\}$. In mathematics, “or” is not exclusive—an element that belongs to both $A$ and $B$ (that is, an element of $A\cap B$) is of course also contained in $A\cup B$.
Definition 13.4: Empty set
The set with no elements at all is called the empty set and is denoted by $\emptyset$.
The intersection and the union were operations between two sets, but there is one more kind of set, formed from the relationship between “a single set and the larger set that contains it (the arena).” This is the complement. In probability theory, this set serving as the “arena” plays an especially important role (as the sample space).
Definition 13.5: Complement
Given a universal set $U$ and a subset $A$ of $U$ ($A\subset U$), the set of all elements of $U$ that do not belong to $A$ is called the complement of $A$ with respect to $U$ and is written
$$ \bar A $$in symbols.
Written as a logical formula, the complement is
$$ \bar A=\{\alpha\mid \alpha\in U\text{ and }\alpha\notin A\} $$Also, for the empty set $\emptyset$ and the universal set $U$, the relations
$$ \bar\emptyset=U,\qquad \bar U=\emptyset $$hold, and furthermore the relations
$$ A\cap\bar A=\emptyset,\qquad A\cup\bar A=U,\qquad \bar{\bar A}=A $$hold (the left-hand side of the last relation is read “the complement of the complement of $A$”).
Why do they hold? The five properties of the complement
Each of them can be confirmed in about one line by going back to the logical formula for Definition 13.5. Let us follow them while keeping Figure 13.3 in mind.
$\bar\emptyset=U$: $\bar\emptyset$ is the set of “elements that belong to $U$ and do not belong to $\emptyset$.” Since nothing belongs to $\emptyset$ to begin with, the condition “does not belong to $\emptyset$” holds automatically for every element of $U$. Hence $\bar\emptyset=U$.
$\bar U=\emptyset$: $\bar U$ is the set of “elements that belong to $U$ and do not belong to $U$,” but no element satisfies “belongs to $U$ and does not belong to $U$” at the same time, so $\bar U=\emptyset$.
$A\cap\bar A=\emptyset$: An element of $A\cap\bar A$ would have to be one that “belongs to $A$ and does not belong to $A$,” but this too is a condition that cannot hold at the same time, so again no element exists and $A\cap\bar A=\emptyset$.
$A\cup\bar A=U$: Take any element $\alpha$ of $U$. Then one of the two, either $\alpha\in A$ or $\alpha\notin A$ (that is, $\alpha\in\bar A$), always holds (this is the “law of excluded middle” that you learned in high school mathematics—of a proposition and its negation, exactly one is true). Therefore every element of $U$ belongs to $A\cup\bar A$, and $A\cup\bar A=U$.
$\bar{\bar A}=A$: $\bar{\bar A}$ is the “complement of $\bar A$,” that is, the set of all elements of $U$ that do not belong to $\bar A$. But “does not belong to $\bar A$” means (by the definition of $\bar A$) that “it is not the case that it does not belong to $A$,” which is the same as “belongs to $A$.” Hence $\bar{\bar A}=A$.
Example 13.1: Computing the basic set operations concretely
Let the universal set be $U=\{1,2,3,4,5,6,7,8\}$, and let $A=\{1,2,3,4\}$ and $B=\{3,4,5,6\}$. Find $A\cap B$, $A\cup B$, $\bar A$, and $\bar B$.
Solution. $A\cap B$ consists of the elements that belong to both $A$ and $B$, so we compare $A=\{1,2,3,4\}$ and $B=\{3,4,5,6\}$ and pick out the common elements $3,4$.
$$ A\cap B=\{3,4\} $$$A\cup B$ consists of the elements that belong to at least one of $A$ and $B$, so we collect all the elements $1,2,3,4$ of $A$ and $3,4,5,6$ of $B$ (counting repeated elements only once).
$$ A\cup B=\{1,2,3,4,5,6\} $$$\bar A$ consists of the elements that “belong to $U$ and do not belong to $A$,” so we remove $A=\{1,2,3,4\}$ from $U=\{1,\ldots,8\}$.
$$ \bar A=U\setminus A=\{5,6,7,8\} $$Similarly, removing $B=\{3,4,5,6\}$ from $U$ gives
$$ \bar B=U\setminus B=\{1,2,7,8\} $$(If we let $U,A,B$ correspond to the $U,A,B$ of Figures 13.1–13.3, we can picture these numbers actually lining up in the hatched regions. Although this is a computation that can be checked from the inclusion relations among sets alone, without SymPy, we have also verified that Python's set operations (the set type's &, |, and set difference) give the same result.)
13.2 De Morgan's Laws
The three operations defined in the previous section (intersection, union, and complement) are in fact not independent of one another; they are tied together by relations that convert one into another. That relation is the seemingly surprising fact that “the outside of the union of $A$ and $B$” and “the intersection of the outside of $A$ and the outside of $B$” turn out to be the same set. It is called De Morgan's laws. The name comes from the nineteenth-century mathematician Augustus De Morgan.
Theorem 13.1: De Morgan's laws
Let $U$ be the universal set and let $A,B$ be subsets of $U$. Then the following hold.
$$ \overline{A\cup B}=\bar A\cap\bar B, \qquad \overline{A\cap B}=\bar A\cup\bar B $$First, let us look at the intuitive check that uses the figure given in the original notes (the notes' “Evidence”). Figure 13.4(i) shows, within the universal set $U$, the outside of the union $A\cup B$ (that is, $\overline{A\cup B}$) with blue hatching. Figure 13.4(ii) shows, for the same $U,A,B$, $\bar A$ (the outside of circle $A$) with green hatching and $\bar B$ (the outside of circle $B$) with red hatching, and it emphasizes the part where the two colors overlap (the part that looks cross-hatched, that is, with crossing diagonal lines).
Proof (intuitive check with a Venn diagram)
Let $U$ be the universal set and let $A,B$ be subsets of $U$. As can be seen from the figure, the complement $\overline{A\cup B}$ of the union $A\cup B$ in Figure 13.4(i) (blue hatching) and the intersection $\bar A\cap\bar B$ of $\bar A$ and $\bar B$ in (ii) (the part where green and red overlap) both indicate the same region, “the outside of circle $A$ and also the outside of circle $B$.” Therefore $\overline{A\cup B}=\bar A\cap\bar B$ holds.
This check by a figure is intuitive and easy to follow, but merely “looking the same” is not enough as a mathematical proof. So let us also give a general proof: we take one arbitrary element $x$ and trace, by logical case analysis, whether it belongs to the left-hand side or to the right-hand side.
Proof (general proof via membership conditions of elements)
Proof of $\overline{A\cup B}=\bar A\cap\bar B$: For an arbitrary element $x$ of $U$, it suffices to show that the following chain of equivalences holds (saying that two sets are equal is the same as saying that “belongs to one $\iff$ belongs to the other” holds for every element).
$$ \begin{aligned} x\in\overline{A\cup B} &\iff x\notin A\cup B\\ &\iff \lnot(x\in A\text{ or }x\in B)\\ &\iff (x\notin A)\text{ and }(x\notin B)\\ &\iff x\in\bar A\text{ and }x\in\bar B\\ &\iff x\in\bar A\cap\bar B \end{aligned} $$The first equivalence is by the definition of the complement (Definition 13.5), the second by the definition of the union (Definition 13.3), the third by the logical law “the negation of ‘$P$ or $Q$’ is ‘not $P$, and not $Q$’” (this is precisely De Morgan's law for propositions, which appeared in the study of propositions in high school mathematics—De Morgan's laws for sets are in fact nothing more than a translation of this logical law into the language of sets), the fourth by the definition of the complement, and the fifth by the definition of the intersection (Definition 13.2). Hence, for an arbitrary $x$ we have $x\in\overline{A\cup B}\iff x\in\bar A\cap\bar B$, and therefore $\overline{A\cup B}=\bar A\cap\bar B$.
Proof of $\overline{A\cap B}=\bar A\cup\bar B$: Similarly,
$$ \begin{aligned} x\in\overline{A\cap B} &\iff x\notin A\cap B\\ &\iff \lnot(x\in A\text{ and }x\in B)\\ &\iff (x\notin A)\text{ or }(x\notin B)\\ &\iff x\in\bar A\text{ or }x\in\bar B\\ &\iff x\in\bar A\cup\bar B \end{aligned} $$and hence $\overline{A\cap B}=\bar A\cup\bar B$ holds. ∎
Intuition: Why do “or” and “and” swap?
De Morgan's laws can be summed up in one sentence: “taking the outside (taking the complement) interchanges $\cup$ (or) and $\cap$ (and).” Intuitively, “belongs to neither $A$ nor $B$” can be rephrased as “(does not belong to $A$) and (does not belong to $B$)”—since “both are ×,” the two conditions are joined by “and.” On the other hand, “does not belong to $A\cap B$” means “it is not the case that it belongs to both of $A,B$,” which means “it does not belong to $A$, or it does not belong to $B$—at least one of them is ×,” and so we get “or.” This interchange of “and” and “or” does not appear in the later chapters of this book, but it is an important law that shows up everywhere—in logic, in electronic circuits (NAND/NOR gates), in the conditional expressions of programming (!(a && b) == (!a || !b)), and so on.
Example 13.2: Verifying De Morgan's laws concretely
For the same $U=\{1,\ldots,8\}$, $A=\{1,2,3,4\}$, $B=\{3,4,5,6\}$ as in Example 13.1, verify concretely each of $\overline{A\cup B}=\bar A\cap\bar B$ and $\overline{A\cap B}=\bar A\cup\bar B$.
Solution. From Example 13.1 we had $A\cup B=\{1,2,3,4,5,6\}$, $\bar A=\{5,6,7,8\}$, $\bar B=\{1,2,7,8\}$. The left-hand side is
$$ \overline{A\cup B}=U\setminus\{1,2,3,4,5,6\}=\{7,8\} $$and the right-hand side is
$$ \bar A\cap\bar B=\{5,6,7,8\}\cap\{1,2,7,8\}=\{7,8\} $$so the two sides agree ($=\{7,8\}$). Next, since $A\cap B=\{3,4\}$ by Example 13.1, the left-hand side is
$$ \overline{A\cap B}=U\setminus\{3,4\}=\{1,2,5,6,7,8\} $$and the right-hand side is
$$ \bar A\cup\bar B=\{5,6,7,8\}\cup\{1,2,7,8\}=\{1,2,5,6,7,8\} $$so here too the two sides agree ($=\{1,2,5,6,7,8\}$). (Both equalities have been verified with Python set operations.)
The examples so far have dealt with the case in which $A,B$ are in a general position (they overlap only partially). Finally, let us consider a special position—the case in which one is entirely contained in the other—and practice both a proof problem and a drawing problem.
Example 13.3: Intersection and union when one set is a subset of the other (proof and drawing)
Suppose that sets $A,B$ satisfy $A\subset B$. Show that $A\cap B=A$ and $A\cup B=B$ by (1) drawing a Venn diagram to check it intuitively, and (2) proving it logically using equivalences on the membership conditions of elements.
Solution. (1) Check by drawing: That $A\subset B$ (every element of $A$ also belongs to $B$) means that, in a Venn diagram, circle $A$ can be drawn so that it fits entirely inside circle $B$ (Figure 13.5). If we hatch the whole of circle $A$ as in Figure 13.5(i), this is exactly $A\cap B$ (the part belonging to both)—the reason is that circle $A$ lies completely inside circle $B$, so “belongs to $A$” and “belongs to both $A$ and $B$” mean the same thing. Similarly, if we hatch the whole of circle $B$ as in Figure 13.5(ii), this is exactly $A\cup B$ (the part belonging to at least one of them)—the reason is that circle $A$ does not stick out of circle $B$, so “belongs to at least one of $A$ and $B$” and “belongs to $B$” mean the same thing.
(2) Logical proof: First we show $A\cap B=A$. In general, $A\cap B\subset A$ always holds (by the definition of the intersection, Definition 13.2). Therefore it suffices to show the reverse inclusion $A\subset A\cap B$. Take $x\in A$ arbitrarily; by the assumption $A\subset B$, we also have $x\in B$. Hence $x\in A$ and $x\in B$, that is, $x\in A\cap B$. Thus $A\subset A\cap B$ holds, and together with the inclusion $A\cap B\subset A$ shown above, this gives
$$ A\cap B=A $$Next we show $A\cup B=B$. In general, $B\subset A\cup B$ always holds (by the definition of the union, Definition 13.3), so it suffices to show the reverse inclusion $A\cup B\subset B$. Take $x\in A\cup B$ arbitrarily; then $x\in A$ or $x\in B$. If $x\in B$, that itself is the conclusion, so there is nothing to prove. If $x\in A$, then $x\in B$ by the assumption $A\subset B$. In either case $x\in B$, so $A\cup B\subset B$ holds, and together with the inclusion $B\subset A\cup B$ shown above, this gives
$$ A\cup B=B $$∎ Let us also check this with a concrete example. If $A=\{1,2\}$ and $B=\{1,2,3,4\}$, then $A\subset B$, and $A\cap B=\{1,2\}=A$ and $A\cup B=\{1,2,3,4\}=B$, so the claims indeed hold (verified with Python set operations).
13.3 The Language of Trials and Events
Now that the set operations are all in place, we finally set the stage for probability theory. Probability theory deals with acts whose results are determined by chance, such as “rolling a die,” “tossing a coin,” and “drawing lots.” To distinguish between such an act itself and the things that actually happen as a result of that act, we introduce the following two terms.
Definition 13.6: Trial
An experiment or observation (or the like) on some matter, one that can be repeated under the same conditions and whose result is determined by chance, is called a trial.
Intuition: Concrete examples of a “trial”
Rolling a die is a trial! Tossing a coin, drawing one card, and drawing lots are likewise all trials. They have two points in common: they can be “repeated any number of times in the same way,” and “the result of each individual run is not known until we try it (it is governed by chance).”
Definition 13.7: Event
What occurs as a result of performing a trial is called an event.
For example, for the trial of rolling a die, “an even number comes up,” “a number 3 or less comes up,” and “a 1 comes up” are all events. It is natural to represent an event by a set, as a collection of possible outcomes—indeed, the event “an even number comes up” can be identified with the set $\{2,4,6\}$ itself. To make this identification precise, we first give a name to the set of “all possible outcomes.”
Definition 13.8: Sample space
In a trial, let $U$ be the set of all possible cases. The event represented by the universal set $U$ is called the sample space.
Definition 13.9: Empty event
The event represented by the empty set $\emptyset$ is called the empty event.
The sample space $U$ is “the set of all outcomes of the trial,” and in the setting of probability theory, $U$ plays the role of the “universal set” in the definition of the complement in Section 13.1. The empty event $\emptyset$ corresponds to an “event that never occurs” (for example, “a 7 comes up” when rolling a die). Finally, we give a name to each individual element of $U$—that is, to the smallest events, which cannot be decomposed any further.
Definition 13.10: Elementary event
In a trial, let $U$ be the set of all possible cases. An event represented by a set consisting of a single element of $U$ is called an elementary event.
Example 13.4: Writing out the elementary events explicitly (example from the original notes)
For the trial of rolling a die, write out the sample space $U$ and all the elementary events.
Solution. A die shows exactly one of $1$ through $6$, so the sample space is
$$ U=\{1,2,3,4,5,6\} $$An elementary event is “a set consisting of a single element of $U$,” so the elementary events are the sets obtained by making each element of $U$ into a set, one at a time:
$$ \{1\},\ \{2\},\ \{3\},\ \{4\},\ \{5\},\ \{6\} $$These are the six elementary events. (The event “a 1 comes up” is represented, as a set, by $\{1\}$, which has one element—the reason we write an “event” and “the set representing that event” with the same symbol is that an event is defined in this way as a subset of the sample space $U$.)
Let us now confirm what it means that the set notation of Section 13.1 can be read, just as it is, in the language of events. Since an event is defined as “a subset of the sample space $U$,” for two events $A,B$ we can consider the intersection $A\cap B$, the union $A\cup B$, and the complement $\bar A$ just as they are. The only difference is that we reread them not as “operations on sets” but in the “language of events”—that is, in the language of “occurring and not occurring.” We will carry out this rereading one operation at a time in Sections 13.4 and 13.5, but the notation itself can be used entirely as it is, exactly as learned in Sections 13.1 and 13.2. In the next example, let us confirm the ideas of elementary events and the sample space with a trial other than rolling a die (tossing a coin).
Example 13.5: The sample space and elementary events for the trial of tossing a coin twice
For the trial of tossing a coin twice, write out the sample space $U$ and all the elementary events.
Solution. A single toss of a coin has two possible outcomes, heads (H) or tails (T). Since we toss the coin twice, writing out all the combinations of the results of the first and second tosses gives the sample space
$$ U=\{(H,H),\ (H,T),\ (T,H),\ (T,T)\} $$There are $2\times2=4$ possible outcomes in all. Therefore the elementary events are the sets obtained by making each of these four elements into a set, one at a time:
$$ \{(H,H)\},\ \{(H,T)\},\ \{(T,H)\},\ \{(T,T)\} $$These are the four elementary events. (In the die example (Example 13.4) there were six elementary events; this number is determined by “how many outcomes are possible in a single trial”—six for a die, and $2^2=4$ for two coin tosses. This idea of “multiplying the numbers of cases” will be used again in earnest for repeated trials in Section 13.5.)
13.4 Definition of Probability and Its Properties
Now that the setting of trials, events, the sample space, and elementary events is in place, we finally define “probability” itself, the star of this chapter.
Definition 13.11: Probability
In a single trial, the proportion with which an event $A$ is expected to occur is called the probability of the event $A$ and is denoted by $P(A)$ ($P$ derives from the initial letter of the word “probability.” The standard reading is that $P(A)$ stands for “the probability of the event $A$”). Moreover, when in this trial every elementary event can be expected to occur to the same degree (we say in this case that the elementary events are “equally likely”), the probability $P(A)$ that the event $A$ occurs is defined by
\begin{equation} P(A)=\frac{n(A)}{n(U)} \label{eq:13-prob-def} \end{equation}Here $n(A)$ is the number of elements belonging to the event $A$ (i.e., a set), and $n(U)$ is the number of elements belonging to the sample space $U$ (i.e., the total number of elementary events).
Caution: Do not use the formula without first confirming that the outcomes are “equally likely”
The formula $P(A)=n(A)/n(U)$ in Definition 13.11 is a definition that rests squarely on the premise that “every elementary event can be expected to occur to the same degree.” For example, with a lopsided die (one whose center of gravity is displaced), the probability of rolling a $1$ and the probability of rolling a $6$ may not be equal—for such a die the counting formula $n(A)/n(U)$ cannot be used as it stands. Unless stated otherwise, all the examples treated from this chapter on assume that the outcomes are “equally likely” (a homogeneous die, an unbiased coin, a well-shuffled deck of playing cards, and so on).
Example 13.6: Probability for the number rolled on a die
A single die is rolled once. Let $A$ be the event “the number rolled is a multiple of 3.” Find $P(A)$.
Solution. The sample space is $U=\{1,2,3,4,5,6\}$, so $n(U)=6$. The event $A$ is “a multiple of 3,” so $A=\{3,6\}$ and $n(A)=2$. The faces of a die are equally likely, so by Definition 13.11
$$ P(A)=\frac{n(A)}{n(U)}=\frac{2}{6}=\frac13 $$is obtained.
Now that probability has been defined, let us reread the set operations treated in Sections 13.1 and 13.3 (intersection and union) in the “language of events”—the language of occurring and not occurring. The symbols themselves, $A\cap B$ and $A\cup B$, stay exactly as they were; nothing changes.
Definition 13.12: Product event
The event “event $A$ and event $B$ both occur” is called the product event of $A$ and $B$, and we write
$$ A\cap B $$for it.
Definition 13.13: Sum event
The event “event $A$ or event $B$ occurs” is called the sum event, and we write
$$ A\cup B $$for it.
Intuition: Why did we define the same symbol $A\cap B$ twice?
In Definition 13.2 of Section 13.1, we defined $A\cap B$ as “the set of all elements common to the sets $A$ and $B$.” In Definition 13.12, we have defined the same symbol $A\cap B$ over again, as “the event that the event $A$ and the event $B$ both occur.” This may seem contradictory, but in fact there is no contradiction at all—an event was a subset of the sample space $U$ (Definitions 13.7 and 13.8), so “the event $A$ and the event $B$ both occur” means precisely that “the outcome (as an elementary event) belongs both to $A$ and to $B$,” and this refers to exactly the same thing as belonging to the intersection $A\cap B$ as a set. The same holds for sum events and complementary events (next section). In other words, Definitions 13.12 and 13.13 merely “rephrase” Definitions 13.2 and 13.3, and nothing new needs to be done in computations.
13.5 Mutually Exclusive Events, Complementary Events, Independence, and Repeated Trials
In this section we introduce, one by one, the four tools that are actually used most often in computing probabilities—the addition rule for mutually exclusive events, the probability of a complementary event, independence, and repeated trials (binomial probabilities).
Definition 13.14: Mutually exclusive
When two events $A,B$ can never occur at the same time, that is, when the product event satisfies $A\cap B=\emptyset$, the two events $A,B$ are said to be mutually exclusive (in Japanese, the term is pronounced “haihan”).
How we find the probability of the sum event $A\cup B$ depends on whether the events are mutually exclusive. The addition rule summarizes this.
Theorem 13.2: Addition rule
For events $A,B$,
$$ A\cap B=\emptyset\text{ (mutually exclusive):}\quad P(A\cup B)=P(A)+P(B) $$ $$ \begin{aligned} &A\cap B\neq\emptyset\text{:}\\ &\qquad P(A\cup B)=P(A)+P(B)-P(A\cap B) \end{aligned} $$hold.
Caution: It is “$A\cap B=\emptyset$,” not “$P(A\cap B)=\emptyset$”
$P(A\cap B)$ is a probability—a real number between $0$ and $1$ inclusive (Definition 13.11)—whereas $\emptyset$ is a set that has no elements. A real number and a set are different kinds of objects, in different “dimensions,” so to speak, and the two cannot be joined by “$=$” (the equation $P(A\cap B)=0$ would at least make sense, but $P(A\cap B)=\emptyset$ is a misuse of notation). The condition used when we defined mutual exclusiveness in Definition 13.14 was “the product event $A\cap B=\emptyset$”—that is, an equation between events—so the case distinction in Theorem 13.2 is likewise written to match, as equations between sets (events): “when $A\cap B=\emptyset$” and “when $A\cap B\neq\emptyset$.”
Theorem 13.2 is nothing more than a translation, into the language of probability, of the “sum rule for counting” learned in high school mathematics. In fact, the equation for the general case follows directly from the following fact about counting elementary events (the principle of inclusion–exclusion).
Proof
When we count the elements belonging to $A\cup B$, simply adding the number $n(A)$ of elements belonging to $A$ and the number $n(B)$ of elements belonging to $B$ overcounts by exactly the elements belonging to $A\cap B$ (since they belong both to $A$ and to $B$, they get counted exactly twice, once when counting $n(A)$ and once when counting $n(B)$). Therefore, if we subtract the duplicated portion once, we obtain the correct number.
$$ n(A\cup B)=n(A)+n(B)-n(A\cap B) $$Dividing both sides by $n(U)$ (under the premise that the elementary events are equally likely, we use Definition 13.11, $P(X)=n(X)/n(U)$), we obtain
$$ \frac{n(A\cup B)}{n(U)}=\frac{n(A)}{n(U)}+\frac{n(B)}{n(U)}-\frac{n(A\cap B)}{n(U)} $$that is,
\begin{equation} P(A\cup B)=P(A)+P(B)-P(A\cap B) \label{eq:13-addition-law} \end{equation}This is the equation for the general case. In particular, when $A,B$ are mutually exclusive ($A\cap B=\emptyset$, hence $n(A\cap B)=0$ and $P(A\cap B)=0$), the last term vanishes and $P(A\cup B)=P(A)+P(B)$. ∎
Example 13.7: Applying the addition rule to mutually exclusive events
Consider the trial of drawing one ball from a bag containing three red balls, two white balls, and four blue balls. Let $A$ be the event “a red ball is drawn” and $B$ the event “a white ball is drawn.” Find $P(A\cup B)$ (the probability that a red or white ball is drawn).
Solution. There are $3+2+4=9$ balls in all, so $n(U)=9$. The event $A$ is that of drawing a red ball (three balls), so $n(A)=3$, and the event $B$ is that of drawing a white ball (two balls), so $n(B)=2$. A single ball cannot be both red and white at the same time, so $A$ and $B$ are mutually exclusive ($A\cap B=\emptyset$). Therefore, by Theorem 13.2 (the mutually exclusive case),
$$ \begin{aligned} P(A\cup B)&=P(A)+P(B)\\ &=\frac{n(A)}{n(U)}+\frac{n(B)}{n(U)}\\ &=\frac39+\frac29\\ &=\frac13+\frac29\\ &=\frac59 \end{aligned} $$is obtained. (Counting directly, the balls that are red or white number $3+2=5$, so $P(A\cup B)=5/9$, and we can confirm that the two results agree.)
Definition 13.15: Complementary event
For an event $A$, the event that $A$ does not occur is called the complementary event of $A$, and we write
$$ \bar A $$for it.
Using complementary events, probabilities of the type “at least one ○○ occurs” can often be computed more easily than by counting directly. Let us derive the formula for this from the addition rule (Theorem 13.2).
Theorem 13.3: Probability of a complementary event
For any event $A$,
\begin{equation} P(\bar A)=1-P(A) \label{eq:13-complement-prob} \end{equation}holds.
Proof
By the properties of the complement (Section 13.1 of this chapter), $A\cup\bar A=U$ and $A\cap\bar A=\emptyset$ ($A$ and $\bar A$ are mutually exclusive). Therefore, by Theorem 13.2 (the addition rule for the mutually exclusive case),
$$ P(A\cup\bar A)=P(A)+P(\bar A) $$Now $A\cup\bar A=U$, and the probability that the sample space $U$ occurs is $P(U)=n(U)/n(U)=1$ (just substitute $A=U$ into Definition 13.11). Hence
$$ 1=P(U)=P(A\cup\bar A)=P(A)+P(\bar A) $$and solving this for $P(\bar A)$ gives $P(\bar A)=1-P(A)$. ∎
Example 13.8: The probability of “at least once” via the complementary event
A coin is tossed three times. Find the probability that heads appears at least once.
Solution. Let $A=$ “heads appears at least once.” Counting $A$ directly is tedious (we would have to count all the cases in which heads appears once, twice, and three times). So we consider the complementary event. $\bar A=$ “heads never appears,” that is, the event “tails appears all three times.” The results of three coin tosses number $2^3=8$ in all, and among them $\bar A$ (the one outcome $T,T,T$) is exactly one outcome, so
$$ P(\bar A)=\frac{1}{8} $$Therefore, by Theorem 13.3,
$$ P(A)=1-P(\bar A)=1-\frac18=\frac78 $$is obtained. (In problems of the “at least once” type, considering the complementary event in this way—here, “does not occur even once”—often simplifies the computation considerably.)
Definition 13.16: Independent
When two trials do not affect each other's results, these trials are said to be independent.
For example, when the same coin is tossed twice, whether the first toss comes up heads or tails has no influence whatsoever on the result of the second toss—this is what independence means. For independent trials, the probability that “the first is ○○ and the second is ××” is found by the simple multiplication $P(\text{first trial gives ○○})\times P(\text{second trial gives ××})$ (this will be generalized when this book rigorously defines the independence of random variables, but here we use it as an intuitive fact). Using this idea of multiplication, we can compute “the probability that a particular event occurs exactly $r$ times when the same independent trial is repeated $n$ times”—this is the final topic of this section, repeated trials. The formula involves the combination symbol $_n\mathrm{C}_r$ from high school mathematics, so let us first review it briefly.
Math Note: Review of the combinations $_n\mathrm{C}_r$
$_n\mathrm{C}_r$ (read “n-C-r,” meaning “the number of combinations when choosing $r$ items from $n$ items”) is the total number of ways to choose $r$ items from $n$ distinct items without regard to order, and is given by
$$ {}_n\mathrm{C}_r=\frac{n!}{r!\,(n-r)!} $$where $n!=n\times(n-1)\times\cdots\times2\times1$ is the factorial. For example, $_4\mathrm{C}_2=\dfrac{4!}{2!\,2!}=\dfrac{24}{2\times2}=6$, which corresponds to the fact that there are six ways to choose two items out of four (indeed, if the four items are $\{1,2,3,4\}$, the six ways are $\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}$). In the repeated-trials formula, we use $_n\mathrm{C}_r$ as the number of possible answers to the question “on which $r$ of the $n$ trials does the event occur?”
Theorem 13.4: Repeated-trials formula
Suppose that an event $A$ occurs with probability $p$ in a single trial. When this trial is repeated $n$ times (independently each time), the probability that the event $A$ occurs exactly $r$ times is
\begin{equation} {}_n\mathrm{C}_r\cdot p^r\cdot q^{\,n-r}\qquad(\text{where }q=1-p) \label{eq:13-repeated-trials} \end{equation}.
Proof (completing the repeated-trials formula—using the idea behind the binomial theorem)
The original notes leave only the heading “Explaination” [sic] for this theorem before the page runs out (this is judged not to be a slip of the pen, but simply a case where the paper ended before the continuation was written), and in this book we write out the rest through to the end.
Step 1: The probability of $r$ occurrences in one fixed order. Among the $n$ trials, consider one fixed order: for example, event $A$ occurs only in the first $r$ trials, and in the remaining $n-r$ trials $A$ does not occur (the complementary event $\bar A$ occurs, with probability $q=1-p$, Theorem 13.3), that is, the order ($\underbrace{A,A,\ldots,A}_{r},\underbrace{\bar A,\ldots,\bar A}_{n-r}$). Since the trials are independent (Definition 13.16), the probability that this fixed order occurs is obtained by multiplying together the probabilities of all the individual trials.
$$ \begin{aligned} &\underbrace{p\times p\times\cdots\times p}_{r\text{ factors}}\times\underbrace{q\times q\times\cdots\times q}_{n-r\text{ factors}}\\ &=p^r q^{\,n-r} \end{aligned} $$Moreover, this is not limited to the specific order “the first $r$ trials”: whichever $r$ trials we fix as the ones on which $A$ occurs, we obtain exactly the same value $p^rq^{n-r}$—because for independent trials, the product does not change when the order of multiplication is rearranged.
Step 2: How many orders are there? The total number of ways of choosing “on which $r$ of the $n$ trials $A$ occurs” is precisely the number of combinations $_n\mathrm{C}_r$ confirmed in the Math Note review (we choose, from the $n$ trials, the $r$ trials on which $A$ occurs, without regard to order).
Step 3: Adding up. Different choices of “on which $r$ trials $A$ occurs” are mutually exclusive events (a given sequence of trial outcomes cannot fit two or more of the choices at the same time). Therefore, by the generalized addition rule (the extension of Theorem 13.2 to $_n\mathrm{C}_r$ mutually exclusive events—the case of three events is treated in Exercise 13.4), the total probability is simply the sum of the individual probabilities $p^rq^{n-r}$, one for each of the $_n\mathrm{C}_r$ choices. But as we saw in Step 1, the probability is the same value $p^rq^{n-r}$ for every arrangement, so we obtain
$$ \begin{aligned} P(\text{exactly }r\text{ occurrences})&=\underbrace{p^rq^{n-r}+p^rq^{n-r}+\cdots+p^rq^{n-r}}_{{}_n\mathrm{C}_r\text{ terms}}\\ &={}_n\mathrm{C}_r\cdot p^r\cdot q^{\,n-r} \end{aligned} $$∎ Figure 13.8 shows the tree diagram for the case $n=3$ (tossing a coin three times)—among the $2^3=8$ leaves in total (the ends of the rightmost branches), you can see that the number of leaves with exactly $r$ heads coincides exactly with $_3\mathrm{C}_r$ (which is $1,3,3,1$ for $r=0,1,2,3$, respectively).
Example 13.9: Applying the repeated-trials formula to independent repeated trials
When one die is rolled four times, find the probability that “a 1 comes up exactly twice.”
Solution. The probability that a 1 comes up in a single roll of the die is $p=\dfrac16$, and the probability that it does not is $q=1-p=\dfrac56$. Since the trials of rolling the die four times are independent of one another (Definition 13.16), we can apply Theorem 13.4 (the repeated-trials formula) with $n=4$ and $r=2$. First, computing $_4\mathrm{C}_2$ with the formula from the Math Note review gives
$$ {}_4\mathrm{C}_2=\frac{4!}{2!\,2!}=\frac{4\times3}{2\times1}=6 $$Therefore we obtain
$$ \begin{aligned} P&=\,{}_4\mathrm{C}_2\cdot p^2\cdot q^{2}\\ &=6\times\left(\frac16\right)^{2}\times\left(\frac56\right)^{2}\\ &=6\times\frac{1}{36}\times\frac{25}{36}\\ &=\frac{150}{1296}=\frac{25}{216} \end{aligned} $$In decimal form, $25/216\approx0.1157$, that is, about 11.6%. (Verified against a brute-force computation in SymPy that enumerates all outcomes of the four dice rolls; the results agree.)
13.6 Summary and Exercises
13.6.1 Summary
- Basic operations on sets: the intersection $A\cap B$ (read “cap”; elements belonging to both), the union $A\cup B$ (read “cup”; elements belonging to at least one of them), and the complement $\bar A=U\setminus A$. Properties: $\bar\emptyset=U,\bar U=\emptyset,A\cap\bar A=\emptyset,A\cup\bar A=U,\bar{\bar A}=A$.
- De Morgan's laws: $\overline{A\cup B}=\bar A\cap\bar B$, $\overline{A\cap B}=\bar A\cup\bar B$. “Taking the outside (the complement) swaps $\cup$ and $\cap$.”
- The language of trials and events: a trial (an experiment whose result is decided by chance), an event (something that happens as a result of a trial; a subset of the sample space $U$), the sample space (whole event) $U$, the empty event $\emptyset$, and an elementary event (an event consisting of a single element of $U$). The product event and the sum event are simply the intersection and union of sets, reread in the language of events.
- Definition of probability: when the elementary events are equally likely, $P(A)=n(A)/n(U)$.
- Addition rule: in general, $P(A\cup B)=P(A)+P(B)-P(A\cap B)$. When the events are mutually exclusive ($A\cap B=\emptyset$), $P(A\cup B)=P(A)+P(B)$.
- Probability of a complementary event: $P(\bar A)=1-P(A)$. It shows its power in probability calculations of the “at least once” type.
- Independence (trials that do not affect one another) and the repeated-trials formula: when independent trials are repeated $n$ times, the probability that the event $A$ (of probability $p$) occurs exactly $r$ times is $_n\mathrm{C}_r\,p^r q^{n-r}$ ($q=1-p$).
13.6.2 Exercises
Exercise 13.1: Verifying the distributive law with a Venn diagram and with logical formulas
For sets $A,B,C$, show that the distributive law $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ holds: (a) verify it visually by drawing a Venn diagram, and (b) prove it in general by using the membership conditions of elements (equivalence transformations of the form $x\in\cdots\iff\cdots$).
Hint: For (a), draw a Venn diagram with three circles $A,B,C$, like those in Figures 13.1 and 13.2, and check by eye that both sides give the same region. For (b), proceed exactly as in the proof of Theorem 13.1 (Section 13.2): start from “$x\in A\cap(B\cup C)\iff x\in A$ and ($x\in B$ or $x\in C$)” and carry out the equivalence transformations using the distributive law of logical operations $P\land(Q\lor R)\iff(P\land Q)\lor(P\land R)$ (which appears in the study of propositions in high school mathematics).
Exercise 13.2: De Morgan's laws for three sets
For sets $A,B,C$, prove that $\overline{A\cup B\cup C}=\bar A\cap\bar B\cap\bar C$ holds.
Hint: Either of two methods will do: use the proof of the two-set case of Theorem 13.1 (Section 13.2) twice, or write down the membership conditions of elements directly for the three sets. For the former, view the union as $A\cup B\cup C=(A\cup B)\cup C$ and apply Theorem 13.1 twice ($\overline{(A\cup B)\cup C}=\overline{A\cup B}\cap\bar C=(\bar A\cap\bar B)\cap\bar C$).
Exercise 13.3: Probability of a sum event with playing cards
In the trial of drawing one card from a deck of 52 playing cards (jokers excluded), let $A$ be the event “the card is a face card (a J, Q, or K)” and let $B$ be the event “the card is a heart.” Find $P(A)$, $P(B)$, $P(A\cap B)$, and $P(A\cup B)$.
Hint: The events $A,B$ are not mutually exclusive (there are face cards among the hearts), so use the general case of the addition rule (Theorem 13.2). We have $n(A)=4\text{ (suits)}\times3\text{ (J, Q, K)}=12$ and $n(B)=13$, and $A\cap B$ is “the face cards among the hearts,” so $n(A\cap B)=3$.
Exercise 13.4: Extending the addition rule to three mutually exclusive events
For three mutually exclusive events $A,B,C$ ($A\cap B=B\cap C=C\cap A=\emptyset$), show (using Theorem 13.2) that $P(A\cup B\cup C)=P(A)+P(B)+P(C)$ holds, and check this equality in a concrete example ($U=\{1,\ldots,12\}$, $A=\{1,2,3\}$, $B=\{4,5,6,7\}$, $C=\{8,9,10\}$).
Hint: Let $D=B\cup C$. Since $A$ overlaps with neither of the sets $B,C$, $A$ and $D$ are also mutually exclusive (check this first). Then apply Theorem 13.2 (the addition rule for mutually exclusive events) twice in all: once to $A\cup D=A\cup(B\cup C)$ and once to $D=B\cup C$ itself. This is the case $_n\mathrm{C}_r=3$ (three events) of the “generalized addition rule” used in “Step 3” of the proof of the repeated-trials formula (Theorem 13.4) in Section 13.5.
Exercise 13.5: Probability for two dice using the complementary event
When two dice are rolled at the same time, find the probability that the sum of the numbers shown is a multiple of 5, by both (a) counting directly and (b) using the complementary event, and confirm that the two answers agree.
Hint: The sum can take any value from $2$ to $12$, so the sum is a multiple of 5 only when it is $5$ or $10$. The sample space has $6\times6=36$ outcomes. In (b), count the complementary event “the sum is not a multiple of 5.”
Exercise 13.6: Application to reliability engineering—the repeated-trials formula
Suppose that a certain switch fails with probability $p=0.05$ each time it is used, independently in each case. When $n=10$ of these switches are used, find the probability that exactly $r=2$ of them fail.
Hint: Let $A$ be the event “one switch fails” (probability $p=0.05$), let $q=1-p=0.95$ be the probability that it does not fail, and apply Theorem 13.4 (the repeated-trials formula) directly. First compute $_{10}\mathrm{C}_2$, and then multiply by $p^2q^8$.
13.6.3 References
- Yasuhide Mochizuki, Mathematics Notes: Fundamentals of Probability (handwritten lecture notes, in Japanese). The source of this chapter.
- Department of Statistics, College of Arts and Sciences, University of Tokyo (ed.), Kiso Tōkeigaku I: Tōkeigaku Nyūmon [Basic Statistics I: Introduction to Statistics], University of Tokyo Press, 1991 (in Japanese).
- W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed., Wiley, 1968.