2.1 Experiments, Sample Spaces, and Events

The relationship between probability and gambling has been known for some time. Over the years, some famous scientists and mathematicians have devoted time to probability: Galileo wrote on dice games; Laplace worked out the probabilities of some gambling games; and Pascal and Bernoulli, while studying games of chance, contributed to the basic theory of probability. Since the time of this early work, the theory of probability has become a highly developed branch of mathematics. Throughout these beginning sections on basic probability theory, we will often use games of chance to illustrate basic ideas that will form the foundation for more advanced concepts. To start with, a few simple definitions are presented.

Definition 2.1: An experiment is a procedure we perform (quite often hypothetical) that produces some result. Often the letter E is used to designate an experiment (e.g., the experiment E₅ might consist of tossing a coin five times).

Definition 2.2: An outcome is a possible result of an experiment. The Greek letter xi (ξ;) is often used to represent outcomes (e.g., the outcome ξ;₁ of experiment E₅ might represent the sequence of tosses heads-heads-tails-heads-tails; however, the more concise HHTHT might also be used).

Definition 2.3: An event is a certain set of outcomes of an experiment (e.g., the event C associated with experiment E₅ might be C = {all outcomes consisting of an even number of heads}).

Definition 2.4: The sample space is the collection or set of “all possible” distinct (collectively exhaustive and mutually exclusive) outcomes of an experiment. The letter S is used to designate the sample space, which is the universal set of outcomes of an experiment. A sample space is called discrete if it is a finite or a countably infinite set. It is called continuous or a continuum otherwise.

The reason we have placed quotes about the words all possible in Definition 2.4 is explained by the following imaginary situation. Suppose we conduct the experiment of tossing a coin. While it is conceivable that the coin may land on edge, experience has shown us that such a result is highly unlikely to occur. Therefore, our sample space for such experiments typically excludes such unlikely outcomes. We also require, for the present, that all outcomes be distinct. Consequently, we are considering only the set of simple outcomes that are collectively exhaustive and mutually exclusive.

There are also infinite sets that are uncountable and that are not continuous, but these sets are beyond the scope of this book. So for our purposes, we will consider only the preceding two types of sample spaces. It is also possible to have a sample space that is a mixture of discrete and continuous sample spaces. For the remainder of this chapter, we shall restrict ourselves to the study of discrete sample spaces.

A particular experiment can often be represented by more than one sample space. The choice of a particular sample space depends upon the questions that are to be answered concerning the experiment. This is perhaps best explained by recalling Example 2.3 in which a pair of dice was rolled. Suppose we were asked to record after each roll the sum of the numbers shown on the two faces. Then, the sample space could be represented by only eleven outcomes, ξ;₁ = 2, ξ;₂ = 3, ξ;₃ = 4, …, ξ;₁₁ = 12. However, the original sample space is in some way, more fundamental, since the sum of the die faces can be determined from the numbers on the die faces. If the second representation is used, it is not sufficient to specify the sequence of numbers that occurred from the sum of the numbers.

2.2 Axioms of Probability

Now that the concepts of experiments, outcomes, and events have been introduced, the next step is to assign probabilities to various outcomes and events. This requires a careful definition of probability. The words probability and probable are commonly used in everyday language. The meteorologist on the evening news may say that rain is probable for tomorrow or he may be more specific and state that the chance (or probability) of rain is 70%. Although this sounds like a precise statement, we could interpret it in several ways. Perhaps, it means that about 70% of the listening audience will experience rain. Or, maybe if tomorrow could be repeated many times, 70% of the tomorrows would have rain while the other 30% would not. Of course, tomorrow cannot be repeated and this experiment can only be run once. The outcome will be either rain or no rain. The meteorologist may like this interpretation since there is no way to repeat the experiment enough times to test the accuracy of the prediction. However, there is a similar interpretation that can be tested. We might say that any time a day with similar meteorological conditions presents itself, the following day will have rain 70% of the time. In fact, it may be his or her past experience with the given weather conditions that led the meteorologist to the prediction of a 70% chance of rain.

It should be clear from our everyday usage of the word probability that it is a measure of the likelihood of various events. So in general terms, probability is a function of an event that produces a numerical quantity that measures the likelihood of that event. There are many ways to define such a function, which we could then call probability. In fact, we will find several ways to assign probabilities to various events, depending on the situation. Before we do that, however, we start with three axioms that any method for assigning probabilities must satisfy:

Axiom 2.1: For any event A, Pr(A) ≥ 0 (a negative probability does not make sense).

Axiom 2.2: If S is the sample space for a given experiment, Pr(S) = 1 (probabilities are normalized so that the maximum value is unity).

Axiom 2.3a: If A ∩ B = Ø, then Pr(A ∪ B) = Pr(A) + Pr(B).

As the word axiom implies, these statements are taken to be self-evident and require no proof. In fact, the first two axioms are really more of a self-imposed convention. We could have allowed for probabilities to be negative or we could have normalized the maximum probability to be something other than one. However, this would have greatly confused the subject and we do not consider these possibilities. From these axioms (plus one more to be presented shortly), the entire theory of probability can be developed. Before moving on to that task, a corollary to Axiom 2.3a is given.

Corollary 2.1: Consider M sets A₁, A₂, …, A_M which are mutually exclusive, A_i ∩ A_j = Ø for all i ≠ j,

(2.1)

Proof: This statement can be proven using mathematical induction. For those students who are unfamiliar with this concept, the idea behind induction is to show that if the statement is true for M = m, then it must also hold for M = m + 1. Once this is established, it is noted that by Axiom 2.3a, the statement applies for M = 2, and hence it must be true for M = 3. Since it is true for M = 3, it must also be true for M = 4, and so on. In this way, we can prove that Corollary 2.1 is true for any finite M. The details of this proof are left as an exercise for the reader (see Exercise 2.7).

Unfortunately, the proof just outlined is not sufficient to show that Corollary 2.1 is true for the case of an infinite number of sets. That has to be accepted on faith and is listed here as the second part of Axiom 2.3.

Axiom 2.3b: For an infinite number of mutually exclusive sets, A_i , i = 1, 2, 3 …, A_i ∩ A_j = Ø for all i ≠ j,

(2.2)

It should be noted that Axiom 2.3a and Corollary 2.1 could be viewed as special cases of Axiom 2.3b. So, a more concise development could be obtained by starting with Axioms 2.1, 2.2, and 2.3b. This may be more pleasing to some, but we believe the approach given here is little easier to follow for the student learning the material for the first time.

The preceding axioms do not tell us directly how to deal with the probability of the union of two sets that are not mutually exclusive. This can be determined from these axioms as is now shown.

Theorem 2.1: For any sets A and B (not necessarily mutually exclusive),

(2.3)

Proof: We give a visual proof of this important result using the Venn diagram shown in Figure 2.1. To aid the student in the type of reasoning needed to complete proofs of this type, it is helpful to think of a pile of sand lying in the sample space shown in Figure 2.1. The probability of the event A would then be analogous to the mass of that subset of the sand pile that is above the region A and likewise for the probability of the event B. For the union of the two events, if we simply added the mass of the sand above A to the mass of the sand above B, we would double count that region which is common to both sets. Hence, it is necessary to subtract the probability of A ∩ B. We freely admit that this proof is not very rigorous. It is possible to prove Theorem 2.1 without having to call on our sand analogy or even the use of Venn diagrams. The logic of the proof will closely follow what we have done here. The reader is led through that proof in Exercise 2.8.

Figure 2.1 Venn diagram for proof of Theorem 2.1.

Many other fundamental results can also be obtained from the basic axioms of probability. A few simple ones are presented here. More will be developed later in this chapter and in subsequent chapters. As with Theorem 2.1, it might help the student to visualize these proofs by drawing a Venn diagram.

Theorem 2.2: .

Proof:

Theorem 2.3: If A ⊂ B, then Pr(A) ≤ Pr(B).

Proof: See Exercise 2.10.

2.3 Assigning Probabilities

In the previous section, probability was defined as a measure of the likelihood of an event or of events which satisfyAxioms 2.1–2.3. How probabilities are assigned to particular events was not specified. Mathematically, any assignment that satisfies the given axioms is acceptable. Practically speaking, we would like to assign probabilities to events in such a way that the probability assignment actually represents the likelihood of occurrence of that event. Two techniques are typically used for this purpose and are described in the following paragraphs.

In many experiments, it is possible to specify all of the outcomes of the experiment in terms of some fundamental outcomes which we refer to as atomic outcomes. These are the most basic events that cannot be decomposed into simpler events. From these atomic outcomes, we can build more complicated and more interesting events. Quite often we can justify assigning equal probabilities to all atomic outcomes in an experiment. In that case, if there are M mutually exclusive exhaustive atomic events, then each one should be assigned a probability of 1/M. Not only does this make perfect common sense, it also satisfies the mathematical requirements of the three axioms which define probability. To see this, we label the M atomic outcomes of an experiment E as ξ; ₁ , ξ;₂, …, ξ;_M . These atomic events are taken to be mutually exclusive and exhaustive. That is, ξ;_i ∩ ξ;_j = Ø for all i ≠ j, and ξ; ₁ ∪ ξ; ₂ ∪ … ∪ ξ; _M = S. Then by Corollary 2.1 and Axiom 2.2,

(2.4)

If each atomic outcome is to be equally probable, then we must assign each a probability of Pr(ξ; _i ) = 1/M for there to be equality in the preceding equation. Once the probabilities of these outcomes are assigned, the probabilities of some more complicated events can be determined according to the rules set forth in Section 2.2. This approach to assigning probabilities is referred to as the classical approach.

Care must be taken when using the classical approach to assigning probabilities. If we define the set of atomic outcomes incorrectly, unsatisfactory results may occur. In Example 2.8, we may be tempted to define the set of atomic outcomes as the different sums that can occur on the two dice faces. If we assign equally likely probability to each of these outcomes, then we arrive at the assignment

(2.5)

Anyone with experience in games involving dice knows that the likelihood of rolling a 2 is much less than the likelihood of rolling a 7. The problem here is that the atomic events we have assigned are not the most basic outcomes and can be decomposed into simpler outcomes as demonstrated in Example 2.8.

This is not the only problem encountered in the classical approach. Suppose we consider an experiment that consists of measuring the height of an arbitrarily chosen student in your class and rounding that measurement to the nearest inch. The atomic outcomes of this experiment would consist of all the heights of the students in your class. However, it would not be reasonable to assign an equal probability to each height. Those heights corresponding to very tall or very short students would be expected to be less probable than those heights corresponding to a medium height. So, how then do we assign probabilities to these events? The problems associated with the classical approach to assigning probabilities can be overcome by using the relative frequency approach.

The relative frequency approach requires that the experiment we are concerned with be repeatable, in which case, the probability of an event, A, can be assigned by repeating the experiment a large number of times and observing how many times the event A actually occurred. If we let n be the number of times the experiment is repeated and n_A the number of times the event A is observed, then the probability of the event A can be assigned according to

(2.6)

This approach to assigning probability is based on experimental results and thus has a more practical flavor to it. It is left as an exercise for the reader (see Exercise 2.15) to confirm that this method does indeed satisfy the axioms of probability, and is thereby mathematically correct as well.

To get an exact measure of the probability of an event, we must be able to repeat the event an infinite number of times—a serious drawback to this approach. In the dice rolling experiment of Example 2.8, even after rolling the dice 10,000 times, the probability of observing a 5 was measured to only two significant digits. Furthermore, many random phenomena in which we might be interested are not repeatable. The situation may occur only once, and therefore we cannot assign the probability according to the relative frequency approach.

2.4 Joint and Conditional Probabilities

Suppose that we have two events, A and B. We saw a few results in the previous section that dealt with how to calculate the probability of the union of two events, A ∪ B. At least as frequently, we are interested in calculating the probability of the intersection of two events, A ∩ B. This probability is referred to as the joint probability of the events A and B, Pr(A ∩ B). Usually, we will use the simpler notation Pr(A, B). This definition and notation extends to an arbitrary number of sets. The joint probability of the events, A₁, A₂, …, A_M , is Pr(A₁ ∩ A₂ ∩ … ∩ A_M ) and we use the simpler notation Pr(A₁, A₂, … A_M ) to represent the same quantity.

Now that we have established what a joint probability is, how does one compute it? To start with, by comparing Axiom 2.3a and Theorem 2.1, it is clear that if A and B are mutually exclusive, then their joint probability is zero. This is intuitively pleasing, since if A and B are mutually exclusive, then Pr(A, B) = Pr(Ø), which we would expect to be zero. That is, an impossible event should never happen. Of course, this case is of rather limited interest, and we would be much more interested in calculating the joint probability of events that are not mutually exclusive.

In the general case when A and B are not necessarily mutually exclusive, how can we calculate the joint probability of A and B? From the general theory of probability, we can easily see two ways to accomplish this. First, we can use the classical approach. Both events A and B can be expressed in terms of atomic outcomes. We then write A ∩ B as the set of those atomic outcomes that are common to both and calculate the probabilities of each of these outcomes. Alternatively, we can use the relative frequency approach. Let n_{A, B} be the number of times that A and B simultaneously occur in n trials. Then,

(2.7)

Often the occurrence of one event may be dependent upon the occurrence of another. In the previous example, the event A = {a red card is selected} had a probability of Pr(A) = 1/2. If it is known that event C = {a heart is selected} has occurred, then the event A is now certain (probability equal to 1), since all cards in the heart suit are red. Likewise, if it is known that the event C did not occur, then there are 39 cards remaining, 13 of which are red (all the diamonds). Hence, the probability of event A in that case becomes 1/3. Clearly, the probability of event A depends on the occurrence of event C. We say that the probability of A is conditional on C, and the probability of A given knowledge that the event C has occurred is referred to as the conditional probability of A given C. The shorthand notation Pr(A|C) is used to denote the probability of the event A given that the event C has occurred, or simply the probability of A given C.

Definition 2.5: For two events A and B, the probability of A conditioned on knowing that B has occurred is

(2.8)

The reader should be able to verify that this definition of conditional probability does indeed satisfy the axioms of probability (see Exercise 2.21).

We may find in some cases that conditional probabilities are easier to compute than the corresponding joint probabilities and hence, this formula offers a convenient way to compute joint probabilities.

(2.9)

This idea can be extended to more than two events. Consider finding the joint probability of three events, A, B, and C.

(2.10)

In general, for M events, A₁, A₂, …, A_M ,

(2.11)

2.5 Basic Combinatorics

In many situations, the probability of each possible outcome of an experiment is taken to be equally likely. Often, problems encountered in games of chance fall into this category as was seen from the card drawing and dice rolling examples in the preceding sections. In these cases, finding the probability of a certain event, A, reduces to an exercise in counting,

(2.12)

Sometimes, when the scope of the experiment is fairly small, it is straightforward to count the number of outcomes. On the other hand, for problems where the experiment is fairly complicated, the number of outcomes involved can quickly become astronomical, and the corresponding exercise in counting can be quite daunting. In this section, we present some fairly simple tools that are helpful for counting the number of outcomes in a variety of commonly encountered situations. Many students will have seen this material in their high school math courses or perhaps in a freshmen or sophomore level discrete mathematics course. For those who are familiar with combinatorics, this section can be skipped without any loss of continuity.

We start with a basic principle of counting from which the rest of our results will flow.

Principle of Counting: For a combined experiment, E = E₁ × E₂ where experiment E₁ has n₁ possible outcomes and experiment E₂ has n₂ possible outcomes, the total number of possible outcomes in the combined experiment is n = n₁ n₂.

This can be seen through a simple example.

This result can easily be generalized to a combination of several experiments.

Theorem 2.4: A combined experiment, E = E₁ × E₂ × E₃ … ×E_m , consisting of experiments E_i each with n _i outcomes, i = 1, 2, 3, …, m, has a total number of possible outcomes given by

(2.13)

Proof: This can be proven through induction and is left as an exercise for the reader (see Exercise 2.29).

In many problems of interest, we seek to find the number of different ways that we can rearrange or order several items. The orderings of various items are referred to as permutations. The number of permutations can easily be determined from the previous theorem and is given as follows:

Theorem 2.5 (Permutations): The number of permutations of n distinct elements is

(2.14)

Proof: We can view this as an experiment where we have items, numbered 1 through n which we randomly draw (without replacing any previously drawn item) until all n items have been drawn. This is a combined experiment with n sub-experiments, E = E₁ × E₂ × E₃ … E _n . The first experiment is E₁ = “select one of the n items” and clearly has n₁ = n possible outcomes. The second experiment is E₂ = “select one of the remaining items not chosen in E₁.” This experiment has n₂ = n−1 outcomes. Continuing in this manner, E₃ has n₃ = n −2 outcomes, and so on, until we finally get to the last experiment where there is only one item remaining left unchosen and therefore the last experiment has only n_n = 1 outcome. Applying Theorem 2.4 to this situation results in Equation (2.14).

A simple, but useful, extension to the number of permutations is the concept of k-permutations. In this scenario, there are n distinct elements and we would like to select a subset of k of these elements (without replacement).

Theorem 2.6 (k-permutations): The number of k-permutations of n distinct elements is given by

(2.15)

Proof: The proof proceeds just as in the previous theorem.

In many situations, we wish to select a subset of k out of n items, but we are not concerned about the order in which they are selected. In other words, we might be interested in the number of subsets there are consisting of k out of n items. A common example of this occurs in card games where there are 52 cards in a deck and we are dealt some subset of these 52 cards (e.g., 5 cards in a game of poker or 13 cards in a game of bridge). As far as the game is concerned, the order in which we are given these cards is irrelevant. The set of cards is the same regardless of what order they are given to us.

These subsets of k out of n items are referred to as combinations. The number of combinations can be determined by slightly modifying our formula for the number of k-permutations. When counting combinations, every subset that consists of the same k elements is counted only once. Hence, the formula for the number of k-permutations has to be divided by the number of permutations of k elements. This leads us to the following result:

Theorem 2.7 (Combinations): The number of distinct subsets (regardless of order) consisting of k out of n distinct elements is

(2.16)

The expression in Equation (2.16) for the number of combinations of k items out of n also goes by the name of the binomial coefficient. It is called this because the same number shows up in the power series representation of a binomial raised to a power. In particular, is the coefficient of the x^k y^n−k term in the power series expansion of (x + y)ⁿ (see Equation E.13 in Appendix E). A number of properties of the binomial coefficient are studied in Exercise 2.31.

As a brief diversion, at this point it is worthwhile noting that sometimes the English usage of certain words is much different than their mathematical usage. In Example 2.17, we talked about padlocks and their combinations. We found that the formula for k-permutations was used to count the number padlock combinations (English usage), whereas the formula for the number of combinations (mathematical usage) actually applies to something quite different. We are not trying to intentionally introduce confusion here, but rather desire to warn the reader that sometimes the technical usage of a word may have a very specific meaning whereas the non-technical usage of the same word may have a much broader or even different meaning. In this case, it is probably pretty clear why the non-technical meaning of the word “combination” is more relaxed than its technical meaning. Try explaining to your first grader why he needs to know a 3-permutation in order to open his school locker.

The previous result dealing with combinations can be viewed in the context of partitioning of sets. Suppose we have a set of n distinct elements and we wish to partition this set into two groups. The first group will have k elements and the second group will then need to have the remaining n - k elements. How many different ways can this partition be accomplished? The answer is that it is just the number of combinations of k out of n elements, . To see this, we form the first group in the partition by choosing k out of the n elements. There are ways to do this. Since there are only two groups, all remaining elements must go in the second group.

This result can then be extended to partitions with more than two groups. Suppose, for example, we wanted to partition a set of n elements into three groups such that the first group has n₁ elements, the second group has n₂ elements, and the third group has n₃ elements, where n₁ + n₂ + n₃ = n. There are ways in which we could choose the members of the first group. After that, when choosing the members of the second group, we are selecting n₂ elements from the remaining n−n₁ elements that were not chosen to be in the first group.

There are ways in which that can be accomplished. Finally, all remaining elements must be in the third and last group. Therefore, the total number of ways to partition n elements into three groups with n₁, n₂, n₃ elements, respectively, is

(2.17)

The last step was made by employing the constraint that n₁ + n₂ + n₃ = n. Following the same sort of logic, we can extend this result to an arbitrary number of partitions.

Theorem 2.8 (Partitions): Given a set of n distinct elements, the number of ways to partition the set into m groups where the ith group has n_i elements is given by the multinomial coefficient,

(2.18)

Proof: We have already established this result for the cases when m = 2, 3. We leave it as an exercise for the reader (see Exercise 2.30) to complete the general proof. This can be accomplished using a relatively straightforward application of the concept of mathematical induction.

Naturally, there are many more formulas of this nature for more complicated scenarios. We make no attempt to give any sort of exhaustive coverage here. Rather, we merely include some of the more commonly encountered situations in the field of combinatorics. Table 2.2 summarizes the results we have developed and provides a convenient place to find relevant formulas for future reference. In that table, we have also included the notation pⁿ_k to represent the number of k-permutations of n items and cⁿ_k to represent the number of combinations of k out of n items. This notation, or some variation of it, is commonly used in many textbooks as well as in many popularly used calculators.

Table 2.2. Summary of combinatorics formulas

2.6 Bayes’s Theorem

In this section, we develop a few results related to the concept of conditional probability. While these results are fairly simple, they are so useful that we felt it was appropriate to devote an entire section to them. To start with, the following theorem was essentially proved in the previous section and is a direct result of the definition of conditional probability.

Theorem 2.9: For any events A and B such that Pr(B) ≠ 0,

(2.19)

Proof: From Definition 2.5,

(2.20)

Theorem 2.9 follows directly by dividing the preceding equations by Pr(B).

Theorem 2.9 is useful for calculating certain conditional probabilities since, in many problems, it may be quite difficult to compute Pr(A|B) directly, whereas calculating Pr(B|A) may be straightforward.

Theorem 2.10 (Theorem of Total Probability): Let B₁, B₂, …, B_n be a set of mutually exclusive and exhaustive events. That is, B_i ∩ B_j = Ø for all i ≠ j and

(2.21)

Then

(2.22)

Proof: As with Theorem 2.1, a Venn diagram (shown in Figure 2.2) is used here to aid in the visualization of our result. From the diagram, it can be seen that the event A can be written as

Figure 2.2 Venn diagram used to help prove the Theorem of Total Probability.

(2.23)

(2.24)

Also, since the B_i are all mutually exclusive, then the {A ∩ B_i } are also mutually exclusive so that

(2.25)

(2.26)

Finally by combining the results of Theorems 2.9 and 2.10, we get what has come to be know as Bayes’s theorem.

Theorem 2.11 (Bayes’s Theorem): Let B₁, B₂, …, B_n be a set of mutually exclusive and exhaustive events. Then,

(2.27)

As a matter of nomenclature, Pr(B_i ) is often referred to as the a priori¹ probability of event B_i, while Pr(B_i|A) is known as the a posteriori² probability of event B_i given A. Section 2.9 presents an engineering application showing how Bayes’s theorem is used in the field of signal detection. We conclude here with an example showing how useful Bayes’s theorem can be.

2.7 Independence

In Example 2.20, it was seen that observing one event can change the probability of the occurrence of another event. In that particular case, the fact that it was known that Seat 15 was selected lowered the probability that Row 20 was selected. We say that the event A = {Row 20 was selected} is statistically dependent on the event B = {Seat 15 was selected}. If the description of the auditorium were changed so that each row had an equal number of seats (e.g., say all 30 rows had 20 seats each), then observing the event B={Seat 15 was selected} would not give us any new information about the likelihood of the event A = {Row 20 was selected}. In that case, we say that the events A and B are statistically independent. Mathematically, two events A and B are independent if Pr(A|B) = Pr(A). That is, the a priori probability of event A is identical to the a posteriori probability of A given. Note that if Pr(A|B) = Pr(A), then the following two conditions also hold (see Exercise 2.22)

(2.28)

(2.29)

Furthermore, if Pr(A|B) ≠ Pr(A), then the other two conditions also do not hold. We can thereby conclude that any of these three conditions can be used as a test for independence and the other two forms must follow. We use the last form as a definition of independence since it is symmetric relative to the events A and B.

Definition 2.6: Two events are statistically independent if and only if

(2.30)

The previous example brings out a point that is worth repeating. It is a common mistake to equate mutual exclusiveness with independence. Mutually exclusive events are not the same thing as independent events. In fact, for two events A and B for which Pr(A) ≠ 0 and Pr(B) ≠ 0, A and B can never be both independent and mutually exclusive. Thus, mutually exclusive events are necessarily statistically dependent.

A few generalizations of this basic idea of independence are in order. First, what does it mean for a set of three events to be independent? The following definition clarifies this and then we generalize the definition to any number of events.

Definition 2.7: The events A, B, and C are mutually independent if each pair of events is independent; that is

(2.31a)

(2.31b)

(2.31c)

and in addition,

(2.31d)

Definition 2.8: The events A₁, A₂, …, A_n are independent if any subset of k ≤ n of these events are independent, and in addition

(2.32)

There are basically two ways in which we can use this idea of independence. As was shown in Example 2.21, we can compute joint or conditional probabilities and apply one of the definitions as a test for independence. Alternatively, we can assume independence and use the definitions to compute joint or conditional probabilities that otherwise may be difficult to find. This latter approach is used extensively in engineering applications. For example, certain types of noise signals can be modeled in this way. Suppose we have some time waveform X(t) which represents a noisy signal which we wish to sample at various points in time, t₁, t₂, …, t_n . Perhaps, we are interested in the probabilities that these samples might exceed some threshold, so we define the events A_i = Pr(X(t_i ) > T), i = 1, 2, …, n. How might we calculate the joint probability Pr(A₁, A₂, …, A_n )? In some cases, we have every reason to believe that the value of the noise at one point in time does not effect the value of the noise at another point in time. Hence, we assume that these events are independent and write Pr(A₁, A₂, …, A_n ) = Pr(A₁)Pr(A₂) … Pr(A_n ).

2.8 Discrete Random Variables

Suppose we conduct an experiment, E, which has some sample space, S. Furthermore, let ξ; be some outcome defined on the sample space, S. It is useful to define functions of the outcome ξ;, X = f(ξ;). That is, the function f has as its domain all possible outcomes associated with the experiment, E. The range of the function f will depend upon how it maps outcomes to numerical values but in general will be the set of real numbers or some part of the set of real numbers. Formally, we have the following definition.

Definition 2.9: A random variable is a real valued function of the elements of a sample space, S. Given an experiment, E, with sample space, S, the random variable X maps each possible outcome, ξ; ∈ S, to a real number X(ξ;) as specified by some rule. If the mapping X(ξ;) is such that the random variable X takes on a finite or countably infinite number of values, then we refer to X as a discrete random variable; whereas, if the range of X(ξ;) is an uncountably infinite number of points, we refer to X as a continuous random variable.

Since X = f(ξ;) is a random variable whose numerical value depends on the outcome of an experiment, we cannot describe the random variable by stating its value; rather, we must give it a probabilistic description by stating the probabilities that the variable X takes on a specific value or values (e.g., Pr(X=3) or Pr(X > 8)). For now, we will focus on random variables which take on discrete values and will describe these random variables in terms of probabilities of the form Pr(X=x). In the next chapter when we study continuous random variables, we will find this description to be insufficient and will introduce other probabilistic descriptions as well.

Definition 2.10: The probability mass function (PMF), P_X (x), of a random variable, X, is a function that assigns a probability to each possible value of the random variable, X. The probability that the random variable X takes on the specific value x is the value of the probability mass function for x. That is, P_X (x) = Pr(X=x). We use the convention that upper case variables represent random variables while lower case variables represent fixed values that the random variable can assume.

From the preceding examples, it should be clear that the probability mass function associated with a random variable, X, must obey certain properties. First, since P_X (x) is a probability it must be non-negative and no greater than 1. Second, if we sum P_X (x) over all x, then this is the same as the sum of the probabilities of all outcomes in the sample space, which must be equal to 1. Stated mathematically, we may conclude that

(2.33a)

(2.33b)

When developing the probability mass function for a random variable, it is useful to check that the PMF satisfies these properties.

In the paragraphs that follow, we list some commonly used discrete random variables, along with their probability mass functions, and some real-world applications in which each might typically be used.

2.9 Engineering Application—An Optical Communication System

Figure 2.4 shows a simplified block diagram of an optical communication system. Binary data are transmitted by pulsing a laser or a light emitting diode (LED) that is coupled to an optical fiber. To transmit a binary 1, we turn on the light source for T seconds, while a binary 0 is represented by turning the source off for the same time period. Hence, the signal transmitted down the optical fiber is a series of pulses (or absence of pulses) of duration T seconds which represents the string of binary data to be transmitted. The receiver must convert this optical signal back into a string of binary numbers; it does this using a photodetector. The received light wave strikes a photoemissive surface, which emits electrons in a random manner. While the number of electrons emitted during a T second interval is random and thus needs to be described by a random variable, the probability mass function of that random variable changes according to the intensity of the light incident on the photoemissive surface during the T second interval. Therefore, we define a random variable X to be the number of electrons counted during a T second interval, and we describe this random variable in terms of two conditional probability mass functions, P_{X| 0}(k) = Pr(X =k|0 sent) and P _X|1(k) = Pr(X =k|1 sent). It can be shown through a quantum mechanical argument that these two probability mass functions should be those of Poisson random variables. When a binary 0 is sent, a relatively low number of electrons are typically observed; whereas, when a 1 is sent, a higher number of electrons is typically counted. In particular, suppose the two probability mass functions are given by

Figure 2.4 Block diagram of an optical communication system.

(2.46a)

(2.46b)

In these two PMFs, the parameters R₀ and R₁ are interpreted as the “average” number of electrons observed when a 0 is sent and when a 1 is sent, respectively. Also, it is assumed that R₀ ≤ R₁, so when a 0 is sent we tend to observe fewer electrons than when a 1 is sent.

At the receiver, we count the number of electrons emitted during each T second interval and then must decide whether a “0” or “1” was sent during each interval. Suppose that during a certain bit interval it is observed that k electrons are emitted. A logical decision rule would be to calculate Pr(0 sent X =k) and Pr(1 sent X =k) and choose according to whichever is larger. That is, we calculate the a posteriori probabilities of each bit being sent, given the observation of the number of electrons emitted and choose the data bit which maximizes the a posteriori probability. This is referred to as a maximum a posteriori (MAP) decision rule and we decide that a binary 1 was sent if

(2.47)

otherwise, we decide a 0 was sent. Note that these desired a posteriori probabilities are backward relative to how the photodetector was statistically described. That is, we know the probabilities of the form Pr(X =k 1 sent) but we want to know Pr(1 sent X =k). We call upon Bayes’s theorem to help us convert what we know into what we desire to know. Using the theorem of total probability,

(2.48)

The a priori probabilities Pr(0 sent) and Pr(1 sent) are taken to be equal (to 1/2), so that

(2.49)

Therefore, applying Bayes’s theorem,

(2.50)

and

(2.51)

Since the denominators of both a posteriori probabilities are the same, we decide that a 1 was sent if

(2.52)

After a little algebraic manipulation, this reduces down to choosing in favor of a 1 if

(2.53)

otherwise, we choose in favor of 0. That is, the receiver for our optical communication system counts the number of electrons emitted and compares that number with a threshold. If the number of electrons emitted is above the threshold, we decide that a 1 was sent; otherwise, we decide a 0 was sent.

We might also be interested in evaluating how often our receiver makes a wrong decision. Ideally, the answer is that errors are very rare, but still we would like to quantify this. Toward that end, we note that errors can occur in two manners. First a 0 could be sent and the number of electrons observed could fall above the threshold, causing us to decide that a 1 was sent. Likewise, if a 1 is actually sent and the number of electrons observed is low, we would mistakenly decide that a 0 was sent. Again, invoking concepts of conditional probability, we see that

(2.54)

Let x₀ be the threshold with which we compare X to decide which data bit was sent. Specifically, let³ so that we decide a 1 was sent if X > x₀, and we decide a 0 was sent if X ≤ x₀. Then

(2.55)

Likewise,

(2.56)

Hence, the probability of error for our optical communication system is

(2.57)

Figure 2.5 shows a plot of the probability of error as a function of R₁ with R₀ as a parameter. The parameter R₀ is a characteristic of the photodetector used. We will see in later chapters that R₀ can be interpreted as the “average” number of electrons emitted during a bit interval when there is no signal incident on the photodetector. This is sometimes referred to as the “dark current.” The parameter R₁ is controlled by the intensity of the incident light. Given a certain photodetector, the value of the parameter R₀ can be measured. The required value of R₁ needed to achieve a desired probability of error can be found from Figure 2.5 (or from Equation 2.57 which generated that figure). The intensity of the laser or LED can then be adjusted to produce the required value for the parameter R₁.

Figure 2.5 Probability of error curves for an optical communication system; curves are parameterized from bottom to top with R₀ =1, 2, 4, 7, 10.

Section 2.1: Experiments, Sample Spaces, and Events

Section 2.2 Axioms of Probability

Section 2.3 Assigning Probabilities

Section 2.4 Joint and Conditional Probabilities

Section 2.5: Basic Combinatorics

Section 2.6: Bayes’s Theorem

Section 2.7: Independence

Section 2.8: Discrete Random Variables

Miscellaneous Problems

MATLAB Exercises