Discrete Mathematics for Computer Science

Returning to Anil's two children, we saw that the sample space is

and we assumed a uniform probability function. The events we considered are

and

and we wanted to know \(P(A \mid B)\text{.}\) Writing \(A\) and \(B\) as subsets of the sample space \(S\text{,}\) we get

and

Using Definition 3.2.1, it follows that

which is the same answer as we got before.

Assume we roll a fair die, i.e., we choose an element uniformly at random from the sample space

Consider the events

and

What is the conditional probability \(P(A \mid B)\text{?}\) To determine this probability, we assume that event \(B\) occurs, i.e., the roll of the die resulted in one of \(1\text{,}\) \(3\text{,}\) and \(5\text{.}\) Given that event \(B\) occurs, event \(A\) occurs in one out of these three possibilities. Thus, \(P(A \mid B)\) should be equal to \(1/3\text{.}\) We are going to verify that this is indeed the answer we get when using Definition 3.2.1: Since

and

we have

Let us now consider the conditional probability \(P(B \mid A)\text{.}\) Thus, we are given that event \(A\) occurs, i.e., the roll of the die resulted in \(3\text{.}\) Since \(3\) is an odd integer, event \(B\) is guaranteed to occur. Therefore, \(P(B \mid A)\) should be equal to \(1\text{.}\) Again, we are going to verify that this is indeed the answer we get when using Definition 3.2.1:

This shows that, in general, \(P(A \mid B)\) is not equal to \(P(B \mid A)\text{.}\) Observe that this is not surprising. (Do you see why?)

Assume we roll a red die and a blue die; thus, the sample space is

where \(i\) is the result of the red die and \(j\) is the result of the blue die. We assume a uniform probability function. Thus, each outcome has a probability of \(1/36\text{.}\)

Let \(D_1\) denote the result of the red die and let \(D_2\) denote the result of the blue die. Consider the events

and

Are these events independent?

• Since

  \begin{equation*} A = \{ (1,6) , (2,5) , (3,4) , (4,3) , (5,2) , (6,1) \} , \end{equation*}

  we have \(P(A) = 6/36 = 1/6\text{.}\)

• Since

  \begin{equation*} B = \{ (4,1) , (4,2) , (4,3) , (4,4) , (4,5) , (4,6) \} , \end{equation*}

  we have \(P(B) = 6/36 = 1/6\text{.}\)

• Since

  \begin{equation*} A \cap B = \{ (4,3) \} , \end{equation*}

  we have \(P(A \cap B) = 1/36\text{.}\)

• It follows that \(P(A \cap B) = P(A) \cdot P(B)\) and we conclude that \(A\) and \(B\) are independent.

As an exercise, you should verify that the events

and

are not independent.

Now consider the two events

and

Since \(A_3 \cap B_3 = \emptyset\text{,}\) we have

On the other hand, \(P \left( A_3 \right) = 1/12\) and \(P \left( B_3 \right) = 1/6\text{.}\) Thus,

and the events \(A_3\) and \(B_3\) are not independent. This is not surprising: If we know that \(B_3\) occurs, then \(A_3\) cannot not occur. Thus, the event \(B_3\) has an effect on the probability that the event \(A_3\) occurs.

Consider flipping a coin three times and assume that the result is a uniformly random element from the sample space

where, e.g., \(HHT\) indicates that the first two flips result in heads and the third flip results in tails. Define the events

and

If we write these events as subsets of the sample space, then we get

and

It follows that

Thus, the sequence \(A,B,C\) is pairwise independent. Since

we have

Thus,

and, therefore, the sequence \(A,B,C\) is not mutually independent. Of course, this is not surprising: If both events \(A\) and \(B\) occur, then event \(C\) also occurs.

Assume we flip three coins. The sample space is

where, e.g., \(TTH\) indicates that the first two coins come up tails and the third coin comes up heads.

Let \(X : S \rightarrow \mathbb{R}\) be the random variable that maps any outcome (i.e., any element of \(S\)) to the number of heads in the outcome. Thus,

If we define the random variable \(Y\) to be the function \(Y: S \rightarrow \mathbb{R}\) that

• maps an outcome to \(1\) if all three coins come up heads or all three coins come up tails, and
• maps an outcome to \(0\) in all other cases,

then we have

Since a random variable is a function \(X : S \rightarrow \mathbb{R}\text{,}\) it maps any outcome \(\omega\) to a real number \(X(\omega)\text{.}\) Usually, we just write \(X\) instead of \(X(\omega)\text{.}\) Thus, for any outcome in the sample space \(S\text{,}\) we denote the value of the random variable, for this outcome, by \(X\text{.}\) In the example above, we flip three coins and write

and

Let us return to the example in which we flip three coins. Assume that the coins are fair and the three flips are mutually independent. Consider again the corresponding random variables \(X\) and \(Y\text{.}\) It should be clear how we determine, for example, the probability that \(X\) is equal to \(0\text{,}\) which we will write as \(P(X=0)\text{.}\) Using our interpretation of “\(X=0\)” as being the event \(\{TTT\}\text{,}\) we get

Similarly, we get

We have two urns \(U_i\) and \(U_j\text{.}\) \(U_i\) contains 2 black balls and 3 white balls. \(U_j\) contains 1 black ball and 1 white ball. An urn is chosen at random, then a ball is chosen at random from it. If a black ball is chosen, what is the probability it came from urn \(U_i\text{?}\)

Let \(I\) be the event urn \(U_i\) is chosen and \(B\) be the event a black ball is chosen.

1. Note that the probability of choosing either urn is \(P(I) = P(\overline{I}) = 1/2\) and the probability that we chose a black ball from urn \(U_i\) is \(P(B \mid I) = 2/5\text{.}\)

2. Next we need to know the probability of choosing a black ball no matter which urn was chosen. This is the probability of choosing a black ball from either urn.

   \begin{equation*} \begin{array}{rl} P(B) & = P(B|I)P(I) + P(B|\overline{I})P(\overline{I})\\ & = (2/5)(1/2) + (1/2)(1/2)\\ & = (1/5) + (1/4)\\ & = (9/20) \end{array} \end{equation*}

3. Calculate the probability urn \(U_i\) is where the black ball came from \(P(I|B)\) using Bayes' Rule:

   \begin{equation*} \begin{array}{rl} P(I|B) & = \frac{P(B|I)P(I)}{P(B)}\\ & =\frac{(2/5)(1/2)}{9/20}\\ & = \frac{1/5}{(9/20)}\\ & = \frac{4}{9} \end{array} \end{equation*}