CS202 Study Guide

Unit 5: Probability

 5a. State the definitions of terms that apply to probability within the context of this course

  • What is the essential goal of probability?
  • Why is a tree of possibilities important?
  • How does our ability to count play in probability?
  • What are the steps of a basic analysis process?

Fundamentally, probability asks the question, "Out of all possible outcomes, what percentage of the time could a specific outcome, or group of outcomes, be expected to occur, under the specified circumstances?" This is an important consideration, for instance, when deciding on how to allocate resources as a team tries to account for what is "most likely" to happen. This consideration is critical because reaching infinite perfection in many situations requires infinite resources. Yet, resources are always finite. So, we try to rank possibilities by their likelihood of occurring and then account for those.

We are often faced with situations where all the variables are not known. But, we still must make the best choice possible within that situation, although it may turn out we make the wrong choice when all is said and done. (This is not our fault, just the way things turned out.) One approach to making the best choice possible is to build a decision tree based on what we know. Here is an example of such a tree:

Notice that not all paths through the tree are shown and not all paths are labeled. This avoids clutter while adding clarity. The tree shows how one event can lead to another with a certain probability. Player 1 makes a choice (the tree root), then Player 2 can make a choice until no other choices can be made. A player cannot make a choice that has already been made. If we make purely random choices, the tree shows the chance that a particular choice will be made. Once no further choices can be made (a leaf of the tree), we have reached the final event and can calculate the probability of that event. Looking at the tree, the final event D has a probability of  \dfrac{1}{4} \times \dfrac{1}{3} \times \dfrac{1}{2} \times \dfrac{1}{1}=
    0.0417 = 4.17\% . It is thus possible to calculate the probability of subsequent events at any tree node. Clearly, probabilities are not always uniform when considering all possible outcomes.

Being able to count possible combinations of items allows us to calculate the probability that a certain combination will occur. Specific combinations have limited opportunity to occur given a limited universe of items that can be combined in various ways. For example, what is the chance that we will draw four aces from a deck of 52 playing cards? Begin by recalling that \left(\begin{array}{l} n \\ k\end{array}\right)  refers to selecting groups of k objects from a base group of n objects, without replacement. That syntax is also written as C(n,k) in various books, papers, and articles. It is calculated as \dfrac{n!}{k!(n - k)!}. Dealing four aces from a total of four aces can only be done in C(4,4) = 1 way. Dealing any non-ace card from the rest of the 48 cards can be done by C(48,1) ways. Any five cards can be drawn from a deck of 52 cards in C(52,5) ways, the total number of different five-card hands. Thus, the probability of dealing the four aces is \dfrac{C(4,4) \times

Following a formal process of calculation allows us to overcome the limitations of human intuition. Here is a good general process: 

  1. Identify all possible outcomes.
  2. Identify all desired outcomes.
  3. Calculate probability of each possible outcome.
  4. Calculate probability of each desired outcome.

Review Introduction to Discrete Probability.


5b. Calculate conditional probabilities (the probability of event Y occurring if event X has already occurred)

  • What is the difference between dependent and independent events?
  • Describe a decision tree and show its value.
  • What does "conditional probability" mean?
  • How does one calculate a conditional probability?

Conditional probability gives the probability that an event will occur after some other event has occurred. Decision trees offer a structure that allows us to compute probabilities for some chain of dependent events. Thus, as trials combine to create events, we can overcome the limits of human intuition using an objective process coupled with a clear framework.

Let's dig deeper into conditional probability by examining an elementary example. Imagine that there are four experiments that we want to conduct, given our research into a particular topic. Because of our limited budget, we can only conduct two of those experiments. We have to choose two of the four possibilities and then proceed to conduct those two. We decide that there is an equal chance of choosing any two of the four experiments (under a uniform distribution) and then an equal chance (under a uniform distribution) of one of the two experiments being successful. What is the chance that a given pair of experiments will be selected? What is the chance that a particular experiment will be successful?

A solution, for this very simple situation, can be visualized with a decision tree, as shown in this figure:

There are only six pairs of experiments that can be selected. Thus, the chance of selecting a given pair is 17%. For each pair, the chance of success is 50%. Thus, the conditional probability of a given experiment's success is 0.50 x 0.17 = 0.09 = 9%, given the situation described. Of course, in reality, scientific experiments may well all fail entirely. But, even then, value is attained since it is important to know what does not work.

Review Conditional Probability.


5c. Compute the probability of independent events

  • How does the probability of an independent event affect the probability of a dependent event?
  • What is the difference between P(A ∩ B) and P(A | B)?
  • What does P(B) mean?

If we ask the value of P(A | B), the conditional probability of Event-A occurring given that independent Event-B has already occurred, we first have to know the probability of independent Event-B, P(B). Event-A is dependent upon Event-B for this calculation. P(B) is calculated as |{B}| / |{all possible events}|.

As an example of an independent event, P(B): if there are 25 blue products out of 100 total products then the probability of a random (uniform distribution) product selection being blue equals 25/100 = 0.25, 25%.

P(A ∩ B) is the probability that Event-A and Event-B occur at the same time, the intersection of Event-A and Event-B. If Event-A and Event-B cannot occur at the same time, they are mutually exclusive,
so P(A ∩ B) = 0.

An example of a dependent event, P(A | B) = P(A ∩ B) / P(B): Assume there are 50 yellow products. Now we ask, what is the chance that a blue product is picked (Event-A) from the total collection of 100 products, knowing that a blue or yellow product was picked (Event-B)? We first have to determine how many products overlap in the total collection of blue and yellow products, | A ∩ B |. Clearly,
{blue} ∩ {blue, yellow} = {blue}. We already know that P(blue) = 0.25. P(blue U yellow) = (25 + 50) / 100 = 0.75. Thus we come to the result that P(A ∩ B) / P(A U B) = 0.25 / 0.75 = 1/3 = P(A | B).

In this way, we arrive at the probability of a dependent event happening as a result of an independent event. This bears greatly on applications such as calculating the probability of a fault occurring in a critical piece of equipment. We start all the independent failures that can occur and then calculate the probability that certain failures can occur at the same time. Clearly, we want to do this objectively and carefully, without worrying about whether or not we would like such things to occur or if we can afford for them to occur or afford to keep them from occurring. Rather, what is important is that we know failure rates and their impacts. If we cannot afford to deal with all possibilities safely, we should not undertake the task. A good contrary example is the report of a failed oil-drilling platform causing death and billions of dollars in heavy pollution because funding was refused by "management" for maintenance and repairs.



5d. Estimate the chance of occurrence of a specific event within a collection of events.

  • What do we mean by "a collection of events"?
  • How does set theory aid us in calculating probabilities?
  • What is the difference between discrete and continuous probability?

Discrete probability estimates the probability that a specific (discrete) event will occur. Discrete events are those with a finite number of outcomes. Examples are: rolling a specific number with standard dice or getting heads or tails after flipping a coin. When we flip a coin, there are only two possible outcomes: heads or tails. When we roll a six-sided die, we can only obtain one of six possible outcomes, 1, 2, 3, 4, 5, or 6. 

Continuous probability deals with variables such as the height of a human, values which can vary over an infinitely continuous scale. Whereas discrete probability deals with countable stand-alone events, continuous probability deals with values on a continuous scale. This is much like dealing with integers, which can take on only certain values, vs. floating-point numbers, which can take on an infinite number of values between any two integer values. We do not address continuous probability in this course.

A collection of events is when we refer to some member(s), {M} of a given set of all possible events, {E}. (Note that {M} is a subset of {E}.) For example, the roll of a standard six-sided die can only result in six events, {E} = {1, 2, 3, 4, 5, 6}. We can ask the probability of some set of events occurring. An example is P(M) = P(1) so that {M} = {1}. We can also ask about the independent probability of an even value being rolled, P(M) = P(2, 4, 5) so that {M} = {2, 4, 6}. P(M) = |{M}| / |{E}|

Using set theory we can determine {M1} ∩ {M2} and {M3} U {M4}, both of which are needed to calculate dependent probabilities. P(A | B) = |{A ∩ B}| / |{A U B}|.

Review Sample Spaces, Events, and Their Probabilities.


Unit 5 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

  • collection of events
  • conditional probability
  • continuous probability
  • decision tree
  • dependent events
  • discrete events 
  • discrete probability
  • independent events
  • leaf
  • probability
  • random
  • root
  • trials
  • uniform