Moments

Chris Gregg

CS109, Stanford University

Autumn 2026

1. Use New Random Variables!
2. Calculate Expectation of a Random Variable

​

Learning Goals

Four Prototypical Trajectories

Announcements

• Pset1 is due today
• Pset2 is out, due next week
• Hopefully you enjoyed your first tutorial! All feedback is welcome, either through your tutorial TA, or on Ed, or via an email to me (cgregg@stanford.edu)
• InLecture is going strong – we have a feedback form we would love for you to fill out! QR code:

Four Prototypical Trajectories

End Announcements

Four Prototypical Trajectories

Review

A random variable is a number which takes on values probabilistically.

A discrete random variable is fully described by a probability mass function.

For example Y is the number of heads in 5 coin flips

Let Y be a random variable

For example Y is the number of heads in 5 coin flips

It is an event when

Y takes on a value

*note: here equals means == in coding

Let Y be a random variable

For example Y is the number of heads in 5 coin flips

It is an event when

you ask any comparison question

Let Y be a random variable

Then this is a probability

(between 0 and 1)

For example Y is the number of heads in 5 coin flips

If this is a number

Then this is a function

For example Y is the number of heads in 5 coin flips

If this is a variable

For example Y is the number of heads in 5 coin flips

This is a function

Four Prototypical Trajectories

Random Variables are a big deal, because they allow other people to give you a PMF (and other helpful equations)

Four Prototypical Trajectories

Classics

Declare a Random Variable to be Binomial

Our random variable

Is distributed as a

Binomial

With these parameters

Num trials

Probability of success on each trial

Exactly k heads in n coin flips. Probability of exactly k heads:

18

Automatically Know the PMF

Probability that our variable takes on the value k

Probability Mass Function for a Binomial

* This is also called the binomial term

The PMF as a Graph: X ~ Bin(n = 20, p = 0.6)

20

Many Stories fit the Binomial

21

Four Prototypical Trajectories

End Review

Galton Board Time!

Galton Board Fun

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

Which bucket a marble lands in corresponds to the number of times the marble went right.

0

1

2

3

4

5

When a marble hits a pin, it has equal chance of going left or right.

Each pin represents an independent event.

Piech & Cain, CS109, Stanford University

Galton Board Fun

We can define a random variable (B)

representing which bucket a marble lands in.

B ~ Bin(n = levels, p = 0.5)

0

1

2

3

4

5

Piech & Cain, CS109, Stanford University

Galton Board Fun

What is the probability of a marble landing in each bucket?

We can define a random variable (B)

representing which bucket a marble lands in.

B ~ Bin(n = levels, p = 0.5)

0

1

2

3

4

5

Piech & Cain, CS109, Stanford University

Galton Board Fun

What is the probability of a marble landing in each bucket?

We can define a random variable (B)

representing which bucket a marble lands in.

B ~ Bin(n = levels, p = 0.5)

0

1

2

3

4

5

Piech & Cain, CS109, Stanford University

Galton Board Fun

What is the probability of a marble landing in each bucket?

We can define a random variable (B)

representing which bucket a marble lands in.

B ~ Bin(n = levels, p = 0.5)

0

1

2

3

4

5

Piech & Cain, CS109, Stanford University

Galton Board Fun

This is the PMF of the binomial!

What is the probability of a marble landing in each bucket?

We can define a random variable (B)

representing which bucket a marble lands in.

0

1

2

3

4

5

Piech & Cain, CS109, Stanford University

Youtube: The Galton Board

Where are We in CS109?

42

You are here

Classic Random Variables (with PMFs)

X ~ Bern(p)

Y ~ Bin(n, p)

X ~ Geo(p)

Y ~ NegBin(r, p)

Successes in one trial

Successes in n trials

Trials until one success

Trials until r success

Goal: Be Able to Use a New Random Variable

You are learning about servers…

You read about the MD1 queue…

You find a paper that says the length of a server “busy period” is distributed as a Borel with parameter μ = 0.2 …

Geometric Random Variable

• X is Geometric Random Variable: X ~ Geo(p)
• X is number of independent trials until first success
• p is probability of success on each trial
• Assumes p does not change
• X takes on values 1, 2, 3, …, with probability:

​

​

Geometric Random Variable

• X is Geometric Random Variable: X ~ Geo(p)

​

​

Example: Let X be the event that a flipped coin lands on its side. Both heads and tails are failures, but if the coin lands on its side, it would be a success. p=0.00002

​

What is the probability that it takes 10,000 or more flips to get a coin to land on its side?

Uh-oh…

Calculating Pi from Coin Flips

The reveal…

Geometric Random Variable

• X is Geometric Random Variable: X ~ Geo(p)

​

​

We would have to sum to infinity for this calculation:

Uh-oh…

(not fun to simulate, but stand by…)

Geometric Random Variable

• X is Geometric Random Variable: X ~ Geo(p)

​

​

Instead, we could calculate the complement:

Geometric Random Variable

• X is Geometric Random Variable: X ~ Geo(p)

​

​

It turns out that this:

does converge to a closed-form:

(same result as we calculated before)

Negative Binomial Random Variable

• X is Negative Binomial RV: X ~ NegBin(r, p)
• X is number of independent trials until r successes
• p is probability of success on each trial
• Assumes p does not change.
• X takes on value n with probability:

​

​

Classic Random Variables (with PMFs)

X ~ Bern(p)

Y ~ Bin(n, p)

X ~ Geo(p)

Y ~ NegBin(r, p)

Successes in n trials

Trials until one success

Trials until r success

​

1. Recognize a classic random variable type

​

​

1. Define a random variable to be that type, with parameters

​

​

1. Profit off the PMF

Recipe For Solving Problems:

Dating at Stanford

Each person you date has a 0.2 probability of being someone you spend your life with. What is the probability you need to date more than 5 people? Your meta goal: what steps would you take to answer this question?

Equity in the Courts

Berghuis v. Smith

If a group is underrepresented in a jury pool, how do you tell?

​

​

​

Justice Breyer [Stanford Alum] opened the questioning by invoking the binomial theorem.  He hypothesized a scenario involving “an urn with a thousand balls, and sixty are yellow, and nine hundred forty are navy-blue, and then you select them at random… twelve at a time.”  According to Justice Breyer and the binomial theorem, if the purple balls were under represented jurors then “you would expect… something like a third to a half of juries would have at least one yellow ball” on them. 

​

Equity in the Courts

​

• Approximation using Binomial distribution
• Assume P(blue ball) constant for every draw = 60/1000
• X = # blue balls drawn. X ~ Bin(12, 60/1000 = 0.06)
• P(X ≥ 1) = 1 – P(X = 0) ≈ 1 – 0.4759 = 0.5240

In Breyer’s description, should actually expect just over half of juries to have at least one non-white person on them

​

Bitcoin Mining

SHA-256 Hash( , )

Data

Fixed

Salt Choice

Number that looks like random bits

You “mine a bitcoin” if, for given data D, you find a salt number N such that Hash(D, N) produces a string that starts with g zeroes.

You “mine a bitcoin” if, for given data D, you find a number N such that Hash(D, N) produces a string that starts with g zeroes.

(a) What is the probability that Hash outputs a bit string which starts with g zeroes (in other words you mine a bitcoin)?

(b) What is the probability that you will need under 100 attempts to mine 2 bit coins?

Let Y be the number of tries until you mine 2 bitcoins.

Call this answer p_a

Let X be the number of zeros in the first g bits.

Classic Random Variables (with PMFs)

X ~ Bern(p)

Y ~ Bin(n, p)

X ~ Geo(p)

Y ~ NegBin(r, p)

Successes in n trials

Trials until one success

Trials until r success

Can Jacob Bernoulli Have a Variable Named After Him?

Here yee. I want to have a random variable named after myself. Huzzah.

Piech & Cain, CS109, Stanford University

Can Jacob Bernoulli Have a Variable Named After Him?

Here yee. I want to have a random variable named after myself. Huzzah.

X ~ Bern(p)

Yes - the Bernoulli random variable:

​

Piech & Cain, CS109, Stanford University

Can Jacob Bernoulli Have a Variable Named After Him?

Here yee. I want to have a random variable named after myself. Huzzah.

X ~ Bern(p)

Yes - the Bernoulli random variable:

• The Bernoulli is an indicator random variable (value is either 0 or 1).
• P(X = 1) = p
• P(X = 0) = 1 – p
• Examples: a single coin flip, one ad click, any binary event

(this is the whole PMF)

Piech & Cain, CS109, Stanford University

Random Variable Sums

Tails

Heads

Heads

Heads

Tails

Heads

Tails

Tails

Heads

The Binomial

Random Variable Sums

Tails

Heads

Heads

Heads

Tails

Heads

Tails

Tails

Heads

The Binomial

…is a sum of Bernoulli random variables

Random Variable Sums

Tails

Heads

Heads

Heads

Tails

Heads

Tails

Tails

Heads

The Binomial

…is a sum of Bernoulli random variables

Let X₁ ~ Bern(p = 1/2) and X₂ ~ Bern(p = 1/2).

Y ~ Bin(n = 2, p = 1/2)

Y = X₁ + X₂

Random Variable Sums

Tails

Tails

Heads

Tails

Tails

Heads

Tails

Tails

Heads

The Negative Binomial

Random Variable Sums

Tails

Tails

Heads

Tails

Tails

Heads

Tails

Tails

Heads

The Negative Binomial

…is a sum of Geometric random variables

Random Variable Sums

Tails

Tails

Heads

Tails

Tails

Heads

Tails

Tails

Heads

The Negative Binomial

…is a sum of Geometric random variables

Let X₁ ~ Geo(p = 1/3), X₂ ~ Geo(p = 1/3), and X₃ ~ Geo(p = 1/3).

Y ~ NegBin(r = 3, p = 1/3)

Y = X₁ + X₂ + X₃

Classic Random Variables (with PMFs)

X ~ Bern(p)

Y ~ Bin(n, p)

X ~ Geo(p)

Y ~ NegBin(r, p)

Successes in one trial

Successes in n trials

Trials until one success

Trials until r success

Time for some moments*

*Moments: numbers that summarize different aspects of a random variable

Expectation

Expected Value

Loop over all values x that X can take on

The value

The probability of that value

Expected Value

​

​

• Also called: Mean, Expectation, Weighted Average, Center of Mass, 1^st Moment

​

72

• Expected value answers the question:
• What is the average value we could expect some random variable to be?

Example: Expected Value of Dice Roll

• Let X be the result of rolling a 6-sided dice.

• What is the expectation of X?

Piech & Cain, CS109, Stanford University

Example: Expected Value of Dice Roll

• Let X be the result of rolling a 6-sided dice.

• What is the expectation of X?

Piech & Cain, CS109, Stanford University

Example: Expected Value of Dice Roll

• Let X be the result of rolling a 6-sided dice.

• What is the expectation of X?

Piech & Cain, CS109, Stanford University

Example: Expected Value of Dice Roll

• Let X be the result of rolling a 6-sided dice.

• What is the expectation of X?

• E[X] is not always an actual possible outcome for X

Piech & Cain, CS109, Stanford University

Lying With Statistics

Imagine a university has 3 classes, with 5, 10, and 150 students in each class.

We randomly choose a class with equal probability.

​

Let X be the chosen class’s size. What is E[X]?

​

​

Piech & Cain, CS109, Stanford University

Lying With Statistics

Imagine a university has 3 classes, with 5, 10, and 150 students in each class.

We randomly choose a class with equal probability.

​

Let X be the chosen class’s size. What is E[X]?

​

​

Piech & Cain, CS109, Stanford University

Lying With Statistics

Imagine a university has 3 classes, with 5, 10, and 150 students in each class.

We randomly choose a student with equal probability.

​

Let X be the chosen student’s class size. What is E[X]?

​

​

Piech & Cain, CS109, Stanford University

Lying With Statistics

Imagine a university has 3 classes, with 5, 10, and 150 students in each class.

We randomly choose a student with equal probability.

​

Let X be the chosen student’s class size. What is E[X]?

​

​

Piech & Cain, CS109, Stanford University

Expectation from Data

81

List called data

Length of data

Four Prototypical Trajectories

Expectation is a single number summary…

Four Prototypical Trajectories

Expectation leaves much to be desired…

Expectation vs PMF

• Let X be the number of problems that a randomly selected student has completed, as of 11a today.
• X takes on values, with uncertainty. X is a random variable.

84

PMF of X

Why People Care?

Properties of Expectation (proof later)

• Linearity:

​

• Consider X = 6-sided die roll, Winnings = 2X – 1.
• E[X] = 3.5 E[2X-1] = 6

​

​

​

​

​

​

​

​

Properties of Expectation (proof later)

• Linearity:

​

• Consider X = 6-sided die roll, Winnings = 2X – 1.
• E[X] = 3.5 E[2X-1] = 6

​

• Expectation of a sum is the sum of expectations

​

​

​

​

​

​

Properties of Expectation (proof later)

• Linearity:

​

• Consider X = 6-sided die roll, Winnings = 2X – 1.
• E[X] = 3.5 E[2X-1] = 6

​

• Expectation of a sum is the sum of expectations

​

​

• Unconscious statistician:

​

​

​

Law of the Unconscious Statistician (LOTUS)

Examples:

This lets you get the expectation of any function of a random variable.

Piech & Cain, CS109, Stanford University

Expectation of Classic Random Variables

Expected Value of Free Throws

• In basketball, players sometimes get a chance to shoot a free throw. If they make it, the team gets 1 point; otherwise they get no points.
• Some players are not very good at free throws, such as Shaq. While in the NBA, Shaq made only 53% of his free throws.

Let X be the points gained from Shaq attempting a free throw.

What is E[X]?

Expected Value of Free Throws

• In basketball, players sometimes get a chance to shoot a free throw. If they make it, the team gets 1 point; otherwise they get no points.
• Some players are not very good at free throws, such as Shaq. While in the NBA, Shaq made only 53% of his free throws.

Let X be the points gained from Shaq attempting a free throw.

What is E[X]?

• For Bernoulli random variables, E[X] = p (always)

With Classic RVs, You Get Expectations For Free Too!

We Can Now Calculate Expectation of Binomial

X ~ Bin(n, p)

We Can Now Calculate Expectation of Binomial

X ~ Bin(n, p)

Let Y_i be 1 if trial i was a success, otherwise 0, with i from 1 to n. Y_i ~ Bern(p).

Tails

Heads

Heads

Heads

Tails

Heads

Tails

Tails

Heads

The Binomial

…is a sum of Bernoulli random variables

We Can Now Calculate Expectation of Binomial

X ~ Bin(n, p)

Let Y_i be 1 if trial i was a success, otherwise 0, with i from 1 to n. Y_i ~ Bern(p).

We Can Now Calculate Expectation of Binomial

Expectation of a sum is the sum of expectations:

X ~ Bin(n, p)

Let Y_i be 1 if trial i was a success, otherwise 0, with i from 1 to n. Y_i ~ Bern(p).

We Can Now Calculate Expectation of Binomial

• True for every binomial ever

X ~ Bin(n, p)

Let Y_i be 1 if trial i was a success, otherwise 0, with i from 1 to n. Y_i ~ Bern(p).

You Get So Much For Free!

Expected Value of Free Throws

• In basketball, players sometimes get a chance to shoot a free throw. If they make it, the team gets 1 point; otherwise they get no points.
• Some players are not very good at free throws, such as Shaq. While in the NBA, Shaq made only 53% of his free throws.

Let Y be the points gained from Shaq attempting 500 free throws.

What is E[Y]?

Expected Value of Free Throws

• In basketball, players sometimes get a chance to shoot a free throw. If they make it, the team gets 1 point; otherwise they get no points.
• Some players are not very good at free throws, such as Shaq. While in the NBA, Shaq made only 53% of his free throws.

Let Y be the points gained from Shaq attempting 500 free throws.

What is E[Y]?

Expected Value of Free Throws

• In basketball, players sometimes get a chance to shoot a free throw. If they make it, the team gets 1 point; otherwise they get no points.
• Some players are not very good at free throws, such as Shaq. While in the NBA, Shaq made only 53% of his free throws.

Let Y be the points gained from Shaq attempting 500 free throws.

What is E[Y]?

Expected Value of Free Throws

• In basketball, players sometimes get a chance to shoot a free throw. If they make it, the team gets 1 point; otherwise they get no points.
• Some players are not very good at free throws, such as Shaq. While in the NBA, Shaq made only 53% of his free throws.

Let Y be the points gained from Shaq attempting 500 free throws.

What is E[Y]?

• Challenge: If Shaq was 10% better at shooting free throws, how many more free throws would you expect him to make, out of 500?

Expected Value of The Geometric

If X ~ Geo(p), then

This definition has intuition built in:

• If Shaq makes about half his free throws, then on average, it will take him two shots to make one free throw. E[X] = (1/2)^-1 = 2.

Expected Value of The Geometric

If X ~ Geo(p), then

This definition has intuition built in:

• If Shaq makes about half his free throws, then on average, it will take him two shots to make one free throw. E[X] = (1/2)^-1 = 2.

• Note: Expectation is often not the mode (the most likely outcome)

Expected Value of The Negative Binomial

We can derive using the sum of expectations property, similar to binomials.

Tails

Tails

Heads

Tails

Tails

Heads

Tails

Tails

Heads

The Negative Binomial

…is a sum of Geometric random variables

Expected Value of The Negative Binomial

We can derive using the sum of expectations property, similar to binomials.

Let X_i ~ Geo(p), for each i from 1 to r.

Let Y ~ NegBin(r, p).

Expected Value of The Negative Binomial

Let X_i ~ Geo(p), for each i from 1 to r.

Let Y ~ NegBin(r, p).

We can derive using the sum of expectations property, similar to binomials.

Expected Value of The Negative Binomial

Let X_i ~ Geo(p), for each i from 1 to r.

Let Y ~ NegBin(r, p).

We can derive using the sum of expectations property, similar to binomials.

Expected Value of The Negative Binomial

Let X_i ~ Geo(p), for each i from 1 to r.

Let Y ~ NegBin(r, p).

We can derive using the sum of expectations property, similar to binomials.

Expectations of Classic Random Variables

X ~ Geo(p)

Y ~ NegBin(r, p)

X ~ Bern(p)

Y ~ Bin(n, p)

Four Prototypical Trajectories

Expectation is easy to work with, but still leaves much to be desired