6.3. Discrete Probability

Now that we know how to count objects, permutations, and combinations, a natural extension is to ask what is the chance or probability of a particular permutation, combination, etc. actually occurring?

First, let’s get some terminology.

6.3.1. Finite Probability

Finite probability derives from Pierre-Simon Laplace’s classic theory of probability. In this context we have three key terms.

Definition (experiment)

An experiment is a procedure which yields a particular outcome from a set of possible outcomes.

Definition (sample space)

The sample space of an experiment is the set of all possible outcomes.

Definition (event)

An event is a subset of a sample space.

The simplest method of determining the chance of a particular outcome occurring is counting the number of occurrence of that outcome and dividing by the total number of possible outcomes.

If you roll a fair 6-sided die, there is \(\frac{1}{6}\) chance of rolling a \(4\), right?

When we can do simple counting and division to compute probability, the outcomes are called equally likely.

Definition (equally likely outcomes)

In a finite sample space \(S\), if all outcomes are equally likely, then the probability of an event \(E\) occurring is \(p(E) = |E| / |S|\).

In a sample space of equally likely outcomes, we always have \(0 \leq p(E) \leq 1\) for any event \(E\). Indeed, since \(E \subset S\) and \(S\) is finite, then \(0 \leq |E| \leq |S|\).

In probability theory a classic problem is an “urn” filled with colored marbles.

Fig. 6.4 An urn filled with 5 blue marbles and 5 green marbles.

An urn of marbles

In an urn filled with \(12\) blue marbles and \(6\) green marbles, what is the probability that a marble chosen from the urn is blue?

There are \(18\) possible outcomes in the sample space because there are \(18\) total marbles.

The event \(E\) we are interested in is obtaining a blue marble. There are \(12\) of them. Thus:

\[ p(E) = 12/18 = \frac{2}{3} = 0.\overline{6} \]

Rolling dice

What is the probability of rolling two fair 6-sided dice and having their sum equal 9?

There are \(36\) possible outcomes when rolling two dice. Indeed, each outcome is \((d_1, d_2) \in \{1,2,3,4,5,6\}^2\).

Of those outcomes there are \((3,6)\), \((4,5)\), \((5,4)\), and \((6,3)\) which add to \(9\). Therefore, the probability is \(4/36 = 1/9\).

---

With and without replacement

When taking a sample (one step in an experiment), there are different ways for that sample to interact with the next.

• “With replacement” means that a sample does not affect the probability of the next.

• “Without replacement” means that a sample does affect the probability of the next.

This terminology comes again from the classic example of choosing marbles from urns.

Urns and replacement

Assume that an urn contains \(20\) marbles. \(12\) are blue and \(8\) are green. What is the probability of first drawing a blue marble and second drawing a green marble, when:

1. The first marble is put back into the urn before choosing the second (with replacement), and

2. The first marble is not put back into the urn (without replacement).

Solution:

1. With replacement, there are \(20\cdot 20 = 400\) possible outcomes by the product rule. On the first choice \(12/20\) marbles are blue. On the second choice \(8/20\) marbles are green. There is a \(12/20\) chance of drawing blue on the first draw. There is an \(8/20\) chance of drawing green on the second draw. In total, the number of outcomes which have blue first and green second is \(12 \cdot 8 = 96\). \(96/400 = 0.24\).

2. Without replacement, there are \(20 \cdot 19\) possible outcomes, since the first choice reduces the number of outcomes of the second choice. Therefore, \(380\) possible outcomes. There are still \(12\cdot 8\) outcomes which have blue first and green second. Thus, the total probability is \(96/380 \approx 0.2526\)

Probability of Complements and Unions

If we know the probability of an event occurring, what is the probability of an event not occurring?

Theorem

Let \(E\) be an event in the sample space \(S\). The probability of the complementary event \(\overline{E} = S \setminus E\), is:

\[ p(\overline{E}) = 1 - p(E) \]

Proof: The sample space is finite. We know that \(|\overline{E}| = |S| - |E|\). Thus:

\[ p(\overline{E}) = \frac{|S| - |E|}{|S|} = 1 - \frac{|E|}{|S|} = 1 - p(E). \qquad \blacksquare \]

Bits of probability

The bits of a byte are chosen randomly. What is the probability that at least one bit is \(1\)?

Let \(E\) be the event that at least one of those bits is \(1\). Then, \(\overline{E}\) is the even that none of the bits are \(1\).

For each bit we have two choices: \(0\) or \(1\). Thus, \(p(\overline{E}) = \frac{1}{2^8}\). There is exactly \(1\) byte with all 0s. By the product rule there are \(2^8\) possible choices for all the bits in a byte.

Therefore, the probability of having at least one bit being \(1\) is \(p(E) = 1 - \frac{1}{2^8} = \frac{255}{256}\)

So we know how to compute the probability of an event not occurring. The next obvious question is: what are the chances that either one of two events occurs?

Theorem

Let \(E_1\) and \(E_2\) be two events in the sample space \(S\). The probability that either event occurs is:

\[ p(E_1 \cup E_2) = p(E_1) + p(E_2) - p(E_1 \cap E_2) \]

Proof: this follows directly from the inclusion-exclusion principle applied to the sets \(E_1\) and \(E_2\):

\[\begin{split} p(E_1 \cup E_2) &= \frac{|E_1 \cup E_2|}{|S|} = \frac{|E_1| + |E_2| - |E_1 \cap E_2|}{|S|} \\[1em] &= p(E_1) + p(E_2) - p(E_1 \cap E_2) \qquad \qquad \blacksquare \end{split}\]

Probability of divisibility

Given a randomly chosen positive integer less than \(1000\), what is the probability that the chosen number is divisible by \(3\) or is divisible by \(5\)?

Every third number is divisible by \(3\), so there are \(\lfloor 1000/3 \rfloor = 333\) numbers divisible by \(3\). Every fifth number is divisible by \(5\), so there are \(\lfloor 1000/5 \rfloor = 200\) numbers divisible by \(5\).

But, how many numbers are divisible by \(3\) and \(5\)? Since \(3\) and \(5\) are co-prime, the only way to be divisible by both is to be a multiple of \(15\). There are \(\lfloor 1000/15 \rfloor = 66\) such numbers.

Thus, the probability of the number being divisible by \(3\) or \(5\) is:

\[ \frac{333}{1000} + \frac{200}{1000} - \frac{66}{1000} = \frac{467}{1000} = 0.467 \]

The Monty Hall Problem

The Monty Hall problem is a classical probability argument applied to a game show.

You have three closed boxes to choose from. Two contain squids, and one contains gold! Choosing a box at random, you have a \(\frac{1}{3}\) chance of choosing the box with gold.

Of the two remaining unchosen boxes, the host opens one which contains a squid. They present you with this question: stick with your first choice or switch your box for the remaining closed box. Which do you do?

Probability says you should always switch.

On your first choice, the probability of choosing the gold is \(\frac{1}{3}\). Therefore, the probability of not choosing the gold is \(\frac{2}{3}\). Since the host always opens a box containing a squid, the probability of choosing gold when switching your choice is the same as the probability that your first choice not being gold. That is, \(\frac{2}{3}\).

6.3.2. Exercises

Exercise 6.11

In a lottery, the grand prize occurs when a player picks the same four digits, in order, as those chosen by a random mechanical process. Assume repeated numbers are allowed. What is the probability of winning? What is the probability of getting 3 out of 4 numbers correct?

Solution to Exercise 6.11

There are \(10\) possible choices for each digits. Since repeats are allowed and order matters, product rule tell us there is \(10^4\) possible choices of digits but only 1 winning outcome. Therefore, the probability is \(1/10^4 = 0.0001\).

To match exactly three digits, one of the four must be incorrect. To be incorrect, there are \(9\) possible choices. The digit that is incorrect can be any of the four digits. Since either the first digit can be wrong, or the second digit can be wrong, etc. then the sum rule tells us there are \(9 \times 4\) possible ways to choose a digit.

Therefore, the probability of matching exactly \(3\) numbers is \(36/10^4 = 0.0026\)

Exercise 6.12

In a lottery, a winner is determined by choosing \(6\) different numbers from the set \(\{1, 2, 3, \ldots, 49\}\). What is the probability of choosing the same \(6\) numbers?

Solution to Exercise 6.12

The set \(\{1,2,\ldots,49\} has \)49\( different numbers. How many ways are there to choose \)6\( of them? \)C(49,6) = \binom{49}{6} = 13983816\( Since there is only one exact match, the probability is \)1 / 13983816 \approx 0.0000000715$.

Exercise 6.13

In a roll of two 6-sided fair dice, what is the probability that the sum of the numbers showing on the dice is less than \(6\)?

Solution to Exercise 6.13

There are \(6 \times 6\) possible outcomes. How many have a sum less than \(6\)?

1. If the first dice is \(1\), the other can be \(1-4\)

2. If the first dice is \(2\), the other can be \(1-3\)

3. If the first dice is \(3\), the other can be \(1-2\)

4. If the first dice is \(4\), the other can be \(1\)

The total number of outcomes totally less than \(6\) are \(10\). Thus, the probability is \(\frac{10}{36} \approx 0.278\)

Exercise 6.14

In 5-card poker, 5 cards from a standard 52-card is dealt to each player.

1. What is the probability of being dealt a flush (all 5 cards of the same suit)?

2. What is the probability of being dealt a flush or a straight (5 cards, of any suit, in sequence; Ace is high or low)?

Solution to Exercise 6.14

There are \(\binom{52}{5}\) distinct hands.

How many different flushes are there? \(\binom{13}{5}\) different possible flushes for a particular suit. There are \(4\) possible suits. So, \(\binom{13}{5}\cdot 4 = 5148\). The probability of a flush is \(5148 / \binom{52}{5} \approx 0.00198\).

How many different straights are there? A-5, 2-6, 3-7, 4-8, 5-9, 6-10, 7-J, 8-Q, 9-K, 10-A. 10 different straights, ignoring suit. Including suit, each card can be 1 of 4 suits. \(10 \cdot 4^5\).

Now, how many straight flushes are there? For each suit there are \(10\) possible straight flushes. Thus, \(40\) in total.

\[\begin{split} p(Flush \cup Straight) &= p(Flush) + p(Straight) - p(Flush \cap Straight)\\ &= \frac{5148 + 10 \cdot 4^5 - 40}{\binom{52}{5}}\\ &\approx 0.0059 \end{split}\]