Lecture notes · Math for Computer Science · Lecture 18

Probability Introduction

MIT 6.042J Mathematics for Computer Science, lecture 18, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

The professor explains why probability matters in math and computer science, warns that gut feelings often fail, and introduces the Monty Hall game show problem.

Key ideas

Probability is one of the most important subjects in math and computer science. Most upper-level computer science courses expect you to already know its basics. 0:46
Your gut feeling, or intuition, is often wrong. The professor says the answer is often the other way from what you first think. 2:12
Probability can be simple if you follow the basic principles and a step-by-step method. The key is to write each step down instead of trusting your gut. 6:32
The Monty Hall problem is the first example. A prize is hidden behind one of three doors, and after the host opens a door showing a goat, the contestant must decide whether to switch. 9:01

Words to know

probability: How likely something is to happen, measured with numbers.
intuition: A quick gut feeling about an answer, without working it out step by step.
probabilistic algorithm: A set of computer steps that uses coin flips or random numbers to get a result, often running faster as a result.
false positive: A test that says you have something when you actually do not.

Example

Think of a friend hiding a coin in one of three cupped hands and asking you to guess. Your gut might say the choice does not matter, but writing down each possible outcome and its chance shows the real answer. The lesson makes the same point: writing the steps beats trusting your feelings.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

The class is testing whether a game show contestant should switch boxes, and the professor warns that a gut feeling can mislead you on this kind of question.

Key ideas

The lesson asks whether a contestant should switch their choice after the host reveals one box that does not hold the prize. The professor says the right strategy matters a lot. 10:20
Three volunteers each pick a box, one box is revealed, and each then decides whether to stick or switch. The class watches to see what happens. 12:51
All three volunteers who switched won, but the professor says three games cannot prove the answer. Anything could have happened in three tries. 17:55
Students disagree about the odds: some think switching helps, some think it is 50-50, and a few think it is 100%. The professor says the answer can be worked out exactly, not guessed. 18:17
The professor says intuition and hand-waving arguments, which are quick reasons without proof, are very tricky here. The exact answer comes from mathematics. 18:38

Words to know

probability: How likely something is to happen, often written as a number or fraction.
intuition: A feeling or gut sense about what is true, without working it out step by step.
trials: Single attempts at the same experiment or game, such as one round of the box game.
hand-waving argument: A quick explanation that sounds convincing but skips the real proof.

Example

A friend says a card trick worked for them three times in a row, so it must always work. Three successes do not prove that, because a few lucky results can happen by chance. The same idea applies to the box game, where three wins do not tell us the true odds.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part tells the Monty Hall story, where experts argued about whether to switch doors, and introduces the first step for solving probability problems: listing all possible outcomes.

Key ideas

In a three-door game show, you pick a door, and the host opens another door that has a goat. The question is whether you should switch to the remaining closed door. 20:21
Marilyn said yes, switch. She said your first door has a 1 in 3 chance and the other closed door has a 2 in 3 chance. Many mathematicians wrote in saying she was wrong and the odds were 1 in 2. 21:07
The lesson says MIT agreed with Marilyn, and that switching gives a 2 in 3 chance of winning. The lesson also says the host always opens a door with a goat. 27:29
The lesson says the experts who were wrong relied on intuition, which means gut feeling, and did not follow the basic steps. The first step is to list the sample space, which is the set of all possible outcomes. 28:14

Words to know

sample space: The full list of everything that could happen in an experiment or game.
outcome: One single result that could happen. The lesson also calls it a sample point or atomic event.
experiment: Any situation with an uncertain result, such as a game show, that you can study for chances.
intuition: A gut feeling about what is right, without working through the steps.

Example

Imagine a game with a million doors where you pick one, and the host opens every other door except one, leaving 777,777 closed. The lesson uses this to show why it feels like the one left closed is likely to have the car. It is a helpful picture, but the lesson says it is not a proof.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows how to list every possible outcome of the Monty Hall game when the player always switches, using a tree diagram.

Key ideas

One outcome, also called a sample point, is a full record of one game. It has three parts: where the prize is, which box the player picked, and which box was revealed. 30:55
Not every combination of three numbers is a real outcome. The host cannot reveal the prize box, and the host cannot reveal the box the player picked. 34:08
The tree method builds the full list step by step. First place the prize, then the player's pick, then the reveal, with branches for each choice. 35:37
Once the tree is complete, there are 12 possible outcomes. For each one, you can check whether the player won by switching, which means ending on the prize box. 38:59

Words to know

outcome (sample point): One complete possible result of the game, with every random choice filled in.
sample space: The full set of all possible outcomes.
tree method: A way of listing all outcomes by drawing branches for each choice, one step at a time, like a decision tree.
switch: In this game, the player changes from the box they first picked to the other closed box.

Example

Think of a school raffle where one ticket wins. Writing down where the prize was, who picked which ticket, and which ticket was shown as a non-winner gives you one complete record of the event. Doing this for every possible way it could go gives you the full list of outcomes.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains that solving the Monty Hall puzzle needs more than a list of possible outcomes, because each outcome also needs a probability, and the starting assumptions must be stated.

Key ideas

Listing all the outcomes is not enough. Each outcome also needs a likelihood, which is how probable it is, and the outcomes are not always equally likely. 40:40
A probability space is the sample space (the list of all outcomes) plus a probability function that gives each outcome a number. 41:25
Every probability must be between 0 and 1, and all the probabilities together must add up to 1. 42:37
Assigning the right probabilities is most of the work. If you give every outcome the same probability when they are not equally likely, you get the wrong answer. 44:32
Before you solve a problem, state your assumptions clearly, such as where the prize is placed and how the player and host choose boxes. Make them reasonable, because they act like starting rules. 49:07

Words to know

sample space: The full list of every result that could happen in an experiment.
probability function: A rule that gives each outcome a number between 0 and 1 showing how likely it is.
probability space: The sample space together with the probability function for each outcome.
assumption: Something you accept as true at the start of a problem so you can work it out, which you should write down.

Example

Flip a fair coin. The chance of heads is 1/2, so if you flip it many times, about half the flips should land heads. That is what a probability means: the share of times an outcome shows up when you repeat the experiment a lot.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part shows how to find the chance of each possible result in the Monty Hall game by multiplying along each path in a tree, then adding up the paths that win.

Key ideas

Each edge of the tree gets a probability, based on the choices the lesson assumed. For example, Carol picks each box she can reveal with probability 1/2. 50:36
The probability of one sample point, which is one possible final outcome, is found by multiplying the probabilities along the path that leads to it. 51:49
Multiplying makes sense because at every step there is a chance to take a different branch, and each step cuts down the chance of landing on that outcome. 54:28
To find the chance of winning, add up the probabilities of all the winning sample points. Switching gives six winning points at 1/9 each, so the total is 2/3. 56:18
An event is a set of outcomes, and its probability is the sum of the probabilities of those outcomes. Since winning and losing cover everything, losing by switching is 1/3. 59:00

Words to know

sample point: One possible final result of the whole process, such as one full path through the game from start to finish.
sample space: The full list of all possible final results of the process.
event: A group of results that we care about, such as all the ways the player wins.
subset: A smaller group taken from a bigger group. Every event is a subset of the sample space.

Example

Think of a tree with branches for each choice in the game. To find how likely one final result is, follow its branch and multiply the chances at each fork, like 1/3 times 1/3 times 1/2 to get 1/18. To find how likely a group of results is, such as all the winning ones, add up their chances.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

This part shows how to work out chances in two games, the Monty Hall-style box choice and a dice game, and introduces the idea of a uniform sample space.

Key ideas

If you switch boxes, you win 2 out of 3 times. So if you stay, you win only 1 out of 3 times, because staying only wins when you first picked the right box. 1:01:03
Gut feelings can be wrong. The professor warns that you must reason carefully instead of trusting intuition, because a small change in the facts can change the answer. 1:01:23
Each die in the dice game has three faces, and each face has a 1 in 3 chance of coming up. A tree diagram lists every possible result so you can count who wins. 1:03:38
With the dice, there are nine equally likely results. Counting them shows that die C wins 5 of the 9, so C is the better pick in this game. 1:09:14
A sample space is uniform when every possible outcome has the same probability. In the dice game, each of the nine outcomes has a chance of 1/9. 1:09:36

Words to know

probability: How likely something is to happen, written as a number from 0 (never) to 1 (certain), or as a fraction like 1/3.
sample space: The full list of everything that could possibly happen in a game or test, such as all the faces a die can show.
tree diagram: A drawing that branches out from a starting point to show every possible result, so you can count them one by one.
uniform: The same in every case. A uniform sample space means every possible outcome has the same chance of happening.

Example

Picture three boxes with one prize hidden in one of them. If you pick a box and then switch to a different one, you are choosing from the two boxes you did not start with, and the lesson shows that switching wins more often than staying. Thinking about the boxes this way helps you see why the 1 in 3 odds for your first pick matter.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:20:00

This part shows that in a game of three dice, each die can beat one of the others, so there is no single best die, and it explains how rolling the dice twice changes the odds.

Key ideas

Each of the nine equal outcomes has a probability of 1/9. C beats A in 5 of those 9 outcomes, so C beats A with probability 5/9. 1:10:01
The professor picks second in the game and wins by choosing the die that beats the first pick. He shows that B beats C with probability 5/9. 1:13:17
A beats B, B beats C, and C beats A, each with probability 5/9. This is a cycle, so probabilities are not transitive: if X beats Y and Y beats Z, X does not always beat Z. 1:15:35
When each die is rolled twice and the two rolls are added, A's odds of beating B get even better. 1:18:50

Words to know

probability: How likely something is to happen, written as a fraction or number. A probability of 5/9 means it happens in 5 out of 9 equal chances.
sample space: The full list of all the possible results of an experiment. Here, the nine possible outcomes from picking one number on each die.
transitive: A rule where, if A beats B and B beats C, then A also beats C. The dice game breaks this rule, so probabilities here are not transitive.
tiebreaker: A rule for deciding a winner when two results are equal. The professor uses it when counting who wins the matchups.

Example

Think of rock, paper, and scissors. Rock beats scissors, scissors beats paper, and paper beats rock, so no single choice is best overall. The three dice in this lesson work the same way: each one beats another, and none beats all three.

3 checked practice questions for this part are in the app.

Part 9 · 1:20:00–1:23:53

This part shows how counting every possible roll of two special dice can reveal surprising wins that go against our intuition, and that the pattern can reverse depending on how many times the dice are rolled.

Key ideas

Each die has nine values, so comparing two dice means checking each value on one die against each value on the other. That makes 81 possible outcomes. 1:20:17
Instead of drawing a full four-level tree to list all 81 outcomes, you can use a nine-leaf tree for each die and then count how many times each die wins. A tie counts as half a win. 1:21:23
The result can feel wrong because our intuition is unreliable here. The math, though, is straightforward and gives a clear answer. 1:21:49
When the dice are rolled twice, the winning pattern reverses. A beats B on one roll, but after two rolls B is worse than A, and this loop goes all the way around, so A is worse than B, B is worse than C, and C is worse than A. 1:22:10
The pattern depends on how many rolls you make. Researchers showed that dice can be made so that the win pattern matches any tournament, which is a set of pairs where one side wins each match, if the dice have more sides and are rolled a certain number of times. 1:22:53

Words to know

outcome: One possible result of an experiment. Here, one pairing of a value from one die with a value from the other die.
leaf: The end point of a branch in a tree diagram. Each leaf stands for one possible result.
tournament: A set of games where every pair of players plays once, and one player always wins each game.
arbitrarily: As much as you want. The lesson says the dice can get as strange as you like.

Example

Picture three friends, A, B, and C, playing a game where each pair plays a match. Suppose A usually beats B, B usually beats C, and C usually beats A. No one is the clear best, and the results loop around in a circle, just like the dice in this lesson.

3 checked practice questions for this part are in the app.

← Lecture 16: Counting Rules I

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York