4. Stochastic Thinking

Introduction

The speaker introduces the course and encourages viewers to support MIT OpenCourseWare.

Family Trees

The speaker discusses family trees and whether it is possible to represent all ancestral relationships as a tree.

• A counterexample is given with Oedipus Rex, where it is not possible to represent all ancestral relationships as a tree.

• Tom Lehrer's song "Oedipus Rex" is recommended for those interested in learning more about the story.

• Relevant reading material is provided for further study.

Uncertainty

The topic of uncertainty is introduced, which will be discussed in future lectures.

• The world is often hard to understand due to uncertainty.

• This course diverges from typical introductory computer science courses by focusing on uncertainty rather than functional programming.

• Facing uncertainty head-on is necessary when trying to write computations that help understand the world.

Causal Nondeterminism

The concept of causal nondeterminism and its impact on understanding the world are discussed.

• For most of history, people believed in Newtonian mechanics where every effect has a cause and the world can be understood causally.

• In the early 20th century, Bohr and Heisenberg put forth the Copenhagen doctrine of causal nondeterminism, which asserts that the world at its most fundamental level behaves in a way that cannot be predicted.

• Einstein disagreed with this doctrine and famously said "God does not play dice."

• Two coins are used as an example to illustrate how uncertainty affects outcomes.

Entrusting Quarters

In this section, John Guttag talks about nondeterminism and probability. He starts by discussing a scenario where someone entrusts him with quarters and asks the audience to guess whether there are two heads, two tails or one of each.

Nondeterminism in Computation

• The fact that we never have complete knowledge of the world suggests that we might as well treat it as inherently unpredictable.

• Predictive nondeterminism underlines pretty much everything else we're going to be doing here.

• When we think about nondeterminism in computation, we use the word stochastic process.

Implementing Randomness in Python

• We can implement a random process in Python using the library random.

• There are two specifications for rolling a die: underdetermined and stochastic.

• The function random.choice takes as an argument a sequence, in this case a list, and randomly chooses one member of the list uniformly.

Probability and Counting

• Probability is all about counting, especially discrete probability.

• To calculate probability, you start by counting the number of events that have the property of interest and divide it by the number of possible events.

• When rolling a die five times, there are 6^5 possible outcomes.

Conclusion

In this lecture, John Guttag introduces nondeterminism and probability. He discusses how predictive nondeterminism underlies most computations. He also explains how to implement randomness in Python using the library random. Finally, he talks about how probability is all about counting and shows an example of calculating probabilities when rolling a die five times.

Probability and Counting

In this section, the speaker introduces the concept of probability and explains how to calculate the probability of a specific event occurring.

Calculating Probability

• The probability of an event is calculated by dividing the number of outcomes that satisfy the event by the total number of possible outcomes.

• Any specific combination is equally probable.

• Probabilities always range from 0 to 1.

• The probability of an event not occurring is simply 1 minus its probability.

Multiplicative Rule

• When events are independent, the probability of all events occurring is equal to the product of their individual probabilities.

• This rule only holds if events are actually independent.

Example Calculation

In this section, the speaker provides an example calculation using American football teams to demonstrate how to use probabilities in practice.

Football Example

• The speaker uses two prominent American football teams as an example.

• The probability of both teams winning next Sunday can be calculated using the multiplicative rule.

• To calculate the probability of at least one team losing, we subtract our previous result from 1.

Understanding Probability

In this section, the speaker discusses how to determine whether two events are independent and the importance of getting it right. They also introduce a code for simulating dice games.

Working with Independent Events

• It can be challenging to determine whether two events are independent.

• The probability of an event can have a significant impact on the outcome.

• The estimated probability from simulations is not always the same as the actual probability.

Simulating Dice Games

• Simulating dice games is easier than simulating football games.

• Most simulations follow a similar structure: initialize variables, run trials, sum up results, and divide by number of trials.

• The simulation code computes estimated probabilities and compares them to actual probabilities.

Pseudorandom Numbers

• Computers cannot generate truly random numbers.

• Instead, they use pseudorandom numbers generated by algorithms that start with a seed.

• Seeds are often based on computer clocks that track elapsed time.

Introduction to Randomness

In this section, we learn about randomness and how to make it predictable. We also learn about the importance of setting a seed value when working with randomness.

Making Randomness Predictable

• To make randomness predictable, we can use the command random.seed and give it a value.

• When debugging programs with randomness, it's important to set random.seed to a value so that you get the same answer every time. However, debug with more than one value of this to ensure that you didn't just get lucky with your seed.

Understanding Probability Estimates

• When running simulations for events that are rare, it takes a lot of trials to get a good estimate of the frequency of an event.

• The estimated probability is not the actual probability and should not be confused with it.

• If you're getting an estimated probability from a simulation, know that it's just an estimate and not the actual probability.

Importance of Simulations

In this section, we learn about why simulations can be useful even when there is a closed-form solution available.

The Birthday Problem

• The birthday problem asks what is the probability of at least two people in a group having the same birthday.

• There is actually a nice closed-form solution for calculating this probability if each birthdate is equally likely. However, simulations can still be useful in solving this problem.

Approximating the Birthday Problem

In this section, we learn how to approximate the probability of two people sharing a birthday using simulation and compare it with the actual probability computed using a formula. We also see why simulating the problem is easier than computing the exact probability.

Simulating the Birthday Problem

• To approximate the solution, we write a simulation that takes two arguments - the number of people in a group and the number of people who share a birthday.

• Assuming that every birthday is equally likely, possible dates range from 1 to 366 because some years have February 29.

• We keep track of the number of people born on each date by starting with none. For each person in the group, we make a random choice of possible dates and increment that element of the list by 1. At the end, we look at the maximum number of birthdays and see if it's greater than or equal to the number of same.

• The estimated probability obtained from simulation is pretty good for different numbers of people in a group.

• We print both estimated and actual probabilities computed using math library for different numbers of people in a group.

Why Simulation is Easier Than Computing Exact Probability

• The estimates are pretty good from my simulation. However, for larger groups like 100, estimating exact probability becomes difficult as it involves complex formulas.

• Changing simulation to find out probability for three people sharing a birthday instead of two is easy compared to computing exact probability which involves complicated formulas with many possibilities.

Introduction to Probability

In this section, the speaker explains why simulations are used to answer probabilistic questions and how they can be easier than doing probability calculations on paper. The speaker also discusses the assumption that all birthdays are equally likely and presents a heat map of common birthdates in the US.

Simulations vs. Probability Calculations

• Simulations are used to answer probabilistic questions because they can be easier than doing probability calculations on paper.

• The assumption that all birthdays are equally likely is discussed, and a heat map of common birthdates in the US is presented.

• The speaker asks if MIT students' birthdays are distributed differently from other dates and shows a heat map for MIT students.

Uncommon Birthdays

• July 4th is an uncommon birthday, possibly because obstetricians don't like working on holidays.

• Christmas day is also not a very common birthday.

• MIT students have some exceptional birth dates, such as February 12th where there were five birthdays.

Adjusting Simulation Models

• The simulation model is adjusted to account for the distribution of birthdates using duplicated dates with different probabilities.

• The relative frequency of each date being chosen by same date is changed in the simulation model.

• Running the simulation model with these changes dramatically changes the answer.

Overall, this section introduces simulations as a tool for answering probabilistic questions and discusses how they can be easier than doing probability calculations on paper. The speaker also presents a heat map of common birthdates in the US and discusses how uncommon birthdays can affect probability calculations. Finally, the simulation model is adjusted to account for the distribution of birthdates, resulting in a change in the answer.

Simulation Models

In this section, the speaker explains the difference between optimization models and simulation models. He also highlights that simulation models are only an approximation to reality.

Optimization Models vs Simulation Models

• Optimization models are prescriptive and tell you how to achieve an effect.

• Simulation models describe possible outcomes but don't tell you how to achieve them.

• Simulation models are used to model systems that are mathematically intractable.

• We need both optimization and simulation models.

Approximation of Reality

• A simulation model is only an approximation to reality.

• The distribution of birthdates used in the previous example was not quite right.

• All models are wrong, but some are actually very useful (George Box).

When Do We Use Simulations?

• Simulations are typically used for modeling systems that are mathematically intractable.

• They can also be used to extract intermediate results along the way to the answer.

Refining Simulations

• Simulations can be successively refined by playing "what if" games.

• Starting with a simple simulation, we can get ever more complexed to answer questions what if.

Producing a Random Walk Simulation

In this section, the speaker introduces producing a random walk simulation as an example of using simulations.

Using Simulations for Random Walks

• The next lecture will focus on producing a simulation of a random walk.

• This will serve as an example of using simulations.

Conclusion

The speaker concludes by stating that simulations allow us to play "what if" games and refine our understanding of complex systems.