Counting Outcomes and Sample Spaces | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 5.1 Free with a free account

Counting Outcomes and Sample Spaces

Discrete Mathematics · Chapter 5: Counting Methods and Basic ProbabilitySection 5.1 · lesson 27 of 879 min · free with a free account

← Constructing Proofs by InductionNext lesson: The Addition and Multiplication Rules →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Every possible result, each counted exactly once.

  • Define a sample space, an outcome and an event
  • Enumerate a multi-stage experiment with a tree diagram
  • Compute a classical probability as a ratio of counts
  • Recognize when that ratio is not a valid probability

Transcript

Everything said in the video, section by section (1,273 words). Read along, or search it.

Counting Methods and Basic Probability

Counting Outcomes and Sample Spaces

Chapter five turns to counting, and to the most basic ideas of probability. This first section builds the language for being precise about chance. What can happen, how to list it all systematically, and how a probability can be computed as a ratio of counts. Everything here is counted by direct enumeration, to make clear exactly what the faster shortcuts in section five point two are shortcuts for.

The Opening Problem

2 Requests, Same Server?

A load balancer sits in front of a small web service. It routes each incoming request to exactly one of three backend servers, A, B, or C, chosen uniformly at random. For a single request, describing what can happen is easy. It lands on A, on B, or on C. But an engineer checking whether the routing behaves as intended, needs to reason about more than one request at a time. For instance, out of two consecutive requests, how often should both land on the same server, just by chance? Answering that takes precision about two things. Exactly what the full range of possible outcomes is. And how to count them, without missing any, or listing any twice.

Definition

Sample Space, Outcome, Event

Every question about chance starts from a random process, called an experiment, together with a complete list of what it could produce. The sample space of an experiment, written with the Greek letter omega, is the set of every possible result. A single element of the sample space is called an outcome. An event is any subset of the sample space. It occurs on a given run exactly when the outcome that actually happens is a member of it. An event with exactly one outcome is a simple event. One with more than one outcome is a compound event. And at the two extremes, the whole sample space is an event that always occurs, while the empty set, containing no outcomes, never occurs.

One Request

3 Outcomes, No Overlap, No Gap

For a single request, the sample space is the set A, B, C. There are exactly three outcomes. And since routing is uniform, there's no reason to expect one more often than another. The request is routed to A is the simple event containing just A. The request is not routed to A is the compound event B, C. It occurs whenever the actual outcome is B, or is C. It's worth being exact about what counts as a legitimate sample space. A, B, C covers every possibility, with no overlap and no gap. Every request lands on exactly one server. A description like normal routing, or unusual routing, might seem to describe the same experiment. But unless those two labels are defined so every outcome falls into exactly one of them, it's not the same kind of object. And generally, its members can't be assumed equally likely.

Tree Diagrams

Enumerating an Experiment in Stages

The single-request sample space was short enough to write out by inspection. But many experiments happen in stages. First one choice is made, then another. Listing every combination correctly, with nothing missing and nothing repeated, gets error-prone quickly if it's done by guesswork. A tree diagram removes the guesswork. From a starting point, draw one branch for each possible result of the first stage. Then, from the tip of each of those branches, draw one branch for each result of the second stage, and so on, for as many stages as the experiment has. The construction guarantees a clean correspondence. Every complete path from the root to a leaf fixes one result at every stage, so it's exactly one outcome. And every outcome traces out exactly one path. Because it goes both ways, counting leaves is the same as counting outcomes. Nothing is missed, and nothing is counted twice.

Worked Example 1

2 Consecutive Requests

Now the first worked example. Two requests arrive one after another, each independently routed to A, B, or C. Stage one has three branches, one for each server that could handle the first request. From the tip of each, stage two again has three branches, one for each server that could handle the second request. Every path fixes a server for each request, so each leaf is labeled as an ordered pair. First request's server, then second request's server. Reading off all nine leaves gives the sample space. The three highlighted leaves, A A, B B, and C C, are the outcomes where both requests land on the same server.

The Tree as Code

Nested Loops Mirror the Branches

The same sample space can be built in code, by mirroring the tree's structure directly. An outer loop runs over the three possible results of stage one. Nested inside it, an inner loop runs over the three results of stage two. Each pass through the inner loop appends one ordered pair. That's one leaf of the tree. Running it prints nine total outcomes, the same nine pairs. It's exactly the branching structure of the tree, written as nested iteration instead of as a picture.

Definition

Classical Probability

With a sample space fully listed, the most basic way to measure how likely an event is comes from simply comparing counts. Let the sample space be finite, with every individual outcome equally likely, and let E be an event. The classical probability of E, also called the naive probability, is the number of outcomes in E, divided by the number of outcomes in the sample space. The formula depends entirely on that equally likely condition. If the outcomes don't all have the same chance of occurring, dividing one count by the other doesn't correctly compute a probability.

Worked Examples 2 and 3

Probabilities by Direct Counting

Back to the two requests, assuming each of the nine outcomes is equally likely. First, the probability that both requests land on the same server. Reading directly from the sample space, that event has three outcomes, A A, B B, and C C. So its probability is three out of nine, which is one third. Second, the probability that at least one request goes to server A. Scanning all nine outcomes for a pair with an A in either position gives five of them. So that probability is five ninths. Notice that both events were found by directly scanning and listing every qualifying outcome. The shortcut formulas for this are exactly what section five point two introduces.

Types of Events

4 Kinds of Event in One Sample Space

This table sorts events into the four types that come up again and again, using the single-request sample space. A simple event has exactly one outcome, like the set containing just A. It occurs when the outcome is A. A compound event has more than one outcome, like B, C. It occurs when the outcome is B, or is C. The certain event is the whole sample space. Whatever happens, it occurs. And the impossible event is the empty set. For example, routed to server D, which doesn't exist. No outcome can ever satisfy it.

Takeaways

Count Carefully, Then Divide

To summarize. A sample space lists every possible outcome, with no overlaps and no gaps. An event is any subset, and it occurs exactly when the actual outcome belongs to it. A tree diagram enumerates a multi-stage experiment with one path per outcome, so nothing is missed or double-counted. The classical formula, a count over a count, requires every outcome to be equally likely. Without that, the ratio isn't a valid probability. And grouping outcomes into a few convenient categories doesn't automatically produce a valid sample space. Here's something to think about. A student wants the probability that a random three-digit code has at least one repeated digit. They say a code has no repeats, exactly one pair, or all three digits the same. Two of those three involve a repeat, so the probability is two thirds. Using this section's definitions, what's wrong with that? Is that set of three really a sample space in this sense? And are its members equally likely?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Counting Outcomes and Sample Spaces

What are a sample space, an outcome, and an event in probability?
A sample space \Omega is the set of every possible result of an experiment, an outcome is one element of it, and an event is any subset of it. An event occurs exactly when the actual outcome is a member. For one request routed to server A, B, or C, \Omega=\{A,B,C\}, and "not routed to A" is the event \{B,C\}.
How do you use a tree diagram to list the outcomes of a multi-stage experiment?
Draw one branch for each result of the first stage, then from each branch tip draw one branch for each result of the second stage, and continue for every stage. Each root-to-leaf path is exactly one outcome, so counting leaves counts outcomes with nothing missed or repeated. Two requests among servers A, B, C give three branches that each split into three, so nine leaves.
How do you compute a classical probability as a ratio of counts?
Divide the number of outcomes in the event by the number of outcomes in the sample space: P(E)=|E|/|\Omega|. This works only when the sample space is finite and every outcome is equally likely. For two requests among three servers, "at least one goes to A" has outcomes AA, AB, AC, BA, CA, so its probability is 5/9.
When is a ratio of counts not a valid probability?
The ratio is not a valid probability when the counted outcomes are not equally likely, or when the list is not a true sample space. For three-digit codes, "no repeats, one pair, all the same" is a complete list, but its three categories are not equally likely. With digits 0–9 there are 720, 270, and 10 codes, so the answer is 280/1000, not 2/3.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →