8 of 111

Declare a Random Variable to be Binomial

Number of successes

Is distributed as a

Binomial

With these parameters

Num trials

Probability of success on each trial

9 of 111

Automatically Know the PMF

Probability that there are k successes

Probability Mass Function for a Binomial

* This is also called the binomial term

10 of 111

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

11 of 111

You Get So Much For Free!

12 of 111

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?

Let X be the # of people date before marrying

I accidentally started with 0 last week!

13 of 111

Four Prototypical Trajectories

What if we could summarize the whole beautiful PMF into a single number?

14 of 111

Expected Value

Loop over all values x that X can take on

The value

The probability of that value

15 of 111

Properties of Expectation (more on this later)

Linearity:

Expectation of a sum is the sum of expectations

Unconscious statistician:

16 of 111

Four Prototypical Trajectories

End Review

17 of 111

Four Prototypical Trajectories

Variance

18 of 111

Intuition: Peer Grading

Peer Grading on Coursera HCI.

31,067 peer grades for 3,607 students.

19 of 111

Intuition: Peer Grading

100

True grade

P(X=x)

20 of 111

Intuition: Measure of Spread

Consider the following 3 distributions (PMFs)

All have the same expected value, E[X] = 3
But “spread” in distributions is different
Invent a formal quantification of “spread”?

21 of 111

Peer grading in Coursera HCI

100

Let X be a random variable that represents a peer grade

μ = E[X] = 57.5

22 of 111

Peer grading in Coursera HCI

100

Let X be a random variable that represents a peer grade

μ = E[X] = 57.5

Var(X) = E [(X – μ)²]

23 of 111

Peer grading in Coursera HCI

100

Var(X) = E [(X – μ)²]

Let X be a random variable that represents a peer grade

μ = E[X] = 57.5

(x – μ)²

25 points

1056 points²

P(X = x)

0.02

24 of 111

Peer grading in Coursera HCI

100

Let X be a random variable that represents a peer grade

μ = E[X] = 57.5

(x – μ)²

25 points

1056 points²

80 points

506 points²

P(X = x)

0.02

0.09

Var(X) = E [(X – μ)²]

25 of 111

Peer grading in Coursera HCI

100

Let X be a random variable that represents a peer grade

μ = E[X] = 57.5

(x – μ)²

25 points

1056 points²

80 points

506 points²

50 points

56 points²

P(X = x)

0.02

0.09

0.12

Var(X) = E [(X – μ)²]

26 of 111

Peer grading in Coursera HCI

100

Let X be a random variable that represents a peer grade

μ = E[X] = 57.5

(x – μ)²

25 points

1056 points²

80 points

506 points²

50 points

56 points²

…

E [(X – μ)²] = 52 points²

P(X = x)

0.02

0.09

0.12

Var(X) = E [(X – μ)²]

27 of 111

Peer grading in Coursera HCI

100

Let X be a random variable that represents a peer grade

μ = E[X] = 57.5

(x – μ)²

25 points

1056 points²

80 points

506 points²

50 points

56 points²

…

E [(X – μ)²] = 52 points²

P(X = x)

Std(X) = 7.2 points

0.02

0.09

0.12

Var(X) = E [(X – μ)²]

28 of 111

100

Normalized histograms are approximations of probability mass functions

29 of 111

Peer grading in Coursera HCI

100

(x – μ)²

25 points

1056 points²

80 points

506 points²

50 points

56 points²

…

E [(X – μ)²] = 52 points²

μ = E[X] = 57.5

Let X be a random variable that represents a peer grade

P(X = x)

Std(X) = 7.2 points

0.02

0.09

0.12

30 of 111

How Should We Measure Spread?

100

Different Possibility:

On average..

The random variable X

The mean of X

distance

Spread stat.

μ = E[X] = 57.5

Let X be a random variable

31 of 111

Variance

If X is a random variable with mean μ then the variance of X, denoted Var(X), is:

Variance is a formal definition of the spread of a random variable.

Also known as the 2nd Central Moment, or square of the Standard Deviation

Var(X) = E [(X – μ)²]

32 of 111

Computing Variance

Law of unconscious statistician

Notation

33 of 111

How do you get E[X²]?

Unconscious statistician:

E[X²]:

34 of 111

Standard Deviation?

Units are in points squared

Units are in points

35 of 111

Example: Variance of a Dice Roll

Let X be the result of rolling a 6 sided dice.
What is Var(X)?

Piech & Cain, CS109, Stanford University

36 of 111

Example: Variance of a Dice Roll

Let X be the result of rolling a 6 sided dice.
What is Var(X)?

Piech & Cain, CS109, Stanford University

37 of 111

Example: Variance of a Dice Roll

Let X be the result of rolling this weird 6 sided dice.
What is Var(X)?

Piech & Cain, CS109, Stanford University

38 of 111

Example: Variance of a Dice Roll

Let X be the result of rolling this weird 6 sided dice.
What is Var(X)?

Piech & Cain, CS109, Stanford University

39 of 111

Variance of a 6 Sided Dice

40 of 111

Fundamental Properties of Random Variables

Random Variable

Moments

P(X = x)

Semantic Meaning

E[X]

Measure of spread

Var(X)

Std(X)

Mode(X)

Support

41 of 111

You Get So Much For Free!

42 of 111

Curious? Proof of Variance for a Binomial (Hard Way)

43 of 111

Four Prototypical Trajectories

Now the easy way….

44 of 111

Variance of a Bernoulli

45 of 111

Variance of a Binomial?

46 of 111

Variance of a Binomial (Easy Way)

Is this true? Is the variance of the sum the sum of variance?

Only if X_is are independent!

Definitions

Proved

Want to Show

Proof

47 of 111

Is Peer Grading Accurate Enough?

Peer Grading on Coursera HCI.

31,067 peer grades for 3,607 students.

Tuned Models of Peer Assessment. C Piech, J Huang, A Ng, D Koller

Looking ahead

48 of 111

Is Peer Grading Accurate Enough?

1. Defined random variables for:

True grade (s_i) for assignment i
Observed (z_i^j) score for assign i
Bias (b_j) for each grader j
Variance (r_j) for each grader j

Tuned Models of Peer Assessment. C Piech, J Huang, A Ng, D Koller

2. Designed a probabilistic model that

defined the distributions for all random variables

Problem param

Looking ahead

49 of 111

Is Peer Grading Accurate Enough?

Tuned Models of Peer Assessment. C Piech, J Huang, A Ng, D Koller

2. Designed a probabilistic model that

defined the relationship between all the random variables

3. Found the variable assignments that maximized the probability of our observed data

1. Defined random variables for:

True grade (s_i) for assignment i
Observed (z_i^j) score for assign i
Bias (b_j) for each grader j
Variance (r_j) for each grader j

Looking ahead

Inference or Machine Learning

50 of 111

99% within 10pp

Before:

After:

Yes, With Probabilistic Modelling

Tuned Models of Peer Assessment. C Piech, J Huang, A Ng, D Koller

81% within 10pp

Std 7.2

Std 4.7

51 of 111

“sweet spot of grading”: ~ 20 minutes

Grading Sweet Spot

52 of 111

Four Prototypical Trajectories

Ready..

53 of 111

Algorithmic Ride Sharing

54 of 111

Probability of k requests from this area in the next 1 min

55 of 111

Probability of k requests from this area in the next 1 min

56 of 111

Probability of k requests from this area in the next 1 min

On average λ = 5 requests per minute

57 of 111

Probability of k requests from this area in the next 1 min

We can break the next minute down into seconds

…

On average λ = 5 requests per minute

58 of 111

Probability of k requests from this area in the next 1 min

On average λ = 5 requests per minute

…

At each second either get a request or you don’t.

Let X = Number of requests in the minute

We can break the next minute down into seconds

59 of 111

Probability of k requests from this area in the next 1 min

On average λ = 5 requests per minute

…

At each second either get a request or you don’t.

Let X = Number of requests in the minute

We can break the next minute down into seconds

60 of 111

Probability of k requests from this area in the next 1 min

On average λ = 5 requests per minute

…

At each second either get a request or you don’t.

Let X = Number of requests in the minute

But what if there are two requests in the same second?

We can break the next minute down into seconds

61 of 111

Probability of k requests from this area in the next 1 min

On average λ = 5 requests per minute

We can break that next minute down into milli-seconds

…

60,000

But what if there are two requests in the same millisecond?

At each milli-second either get a request or you don’t.

Let X = Number of requests in the minute

62 of 111

Probability of k requests from this area in the next 1 min

On average λ = 5 requests per minute

…

60,000

Can we do any better than milli-seconds?

At each milli-second either get a request or you don’t.

Let X = Number of requests in the minute

We can break that next minute down into milli-seconds

63 of 111

Probability of k requests from this area in the next 1 min

On average λ = 5 requests per minute

We can break that minute down into infinitely small buckets

Infinitesimal…

Let X = Number of requests in the minute

Who wants to see some cool math?

64 of 111

Probability of k requests from this area in the next 1 min

65 of 111

Probability of k requests from this area in the next 1 min

66 of 111

Simeon-Denis Poisson (1781-1840) was a prolific French mathematician

Published his first paper at 18, became professor at 21, and published over 300 papers in his life

He reportedly said “Life is good for only two things, discovering mathematics and teaching mathematics.”

Simeon-Denis Poisson

67 of 111

Poisson Random Variable

X is a Poisson Random Variable: the number of occurrences in a fixed interval of time.

λ is the “rate”
X takes on values 0, 1, 2…
has distribution (PMF):

68 of 111

Poisson Process

Consider events that occur over time

Earthquakes, radioactive decay, hits to web server, etc.
Have time interval for events (1 year, 1 sec, whatever...)
Events arrive at rate: λ events per interval of time

Split time interval into n ➔ ∞ sub-intervals

Assume at most one event per sub-interval
Event occurrences in sub-intervals are independent
With many sub-intervals, probability of event occurring in any given sub-interval is small

# events in original time interval ~ Poi(λ)

69 of 111

To the reader!

70 of 111

Poisson is great when you have a rate!

71 of 111

Poisson is great when you have a rate and you care about # of occurrences!

72 of 111

Make sure that the time unit for “rate” and match the probability question

73 of 111

Four Prototypical Trajectories

Two quick examples!

74 of 111

Earthquakes

Average of 2.79 major earthquakes per year.

What is the probability of 3 major earthquakes next year?

75 of 111

Earthquake Probability Mass Function

Let X = number of earthquakes next year

P(X = x)

Number of earthquakes (x)

76 of 111

Earthquakes

77 of 111

Limited sample containers

A primatologist is studying a group of chimpanzees in the wild.

On average, 15 usable biological samples (e.g., hair samples) are collected per day.

Each sample must be stored in its own sterile container.

The researcher only brought 10 containers into the field.

What is the probability that the researcher runs out of containers during the day?

Let X be the number of usable biological samples taken.

from scipy import stats

def main():

lam = int(input("Number of samples per day: "))

num_containers = int(input("Number of containers brought: "))

X = stats.poisson(lam)

prob_enough_containers = 0

for i in range(0, num_containers + 1):

pr_i_samples = X.pmf(i)

prob_enough_containers += pr_i_samples

print(f"Prob of running out: {1 - prob_enough_containers}")

PMF of Poisson

λ = 15

78 of 111

Limited sample containers, follow-up

A primatologist is studying a group of chimpanzees in the wild.

On average, 15 usable biological samples (e.g., hair samples) are collected per day.

Each sample must be stored in its own sterile container.

How many containers should the researcher bring so that the probability of running out is at most 5%?

79 of 111

Limited sample containers, follow-up

A primatologist is studying a group of chimpanzees in the wild.

On average, 15 usable biological samples (e.g., hair samples) are collected per day.

Each sample must be stored in its own sterile container.

How many containers should the researcher bring so that the probability of running out is at most 5%?

This is the same distribution as before: X ~ Poi(𝞴=15), but now we want:

We can use a program (next slide) to check each cumulative sum until we find the one that fits.

80 of 111

Limited sample containers, follow-up

from scipy import stats

def main():

lam = int(input("Number of samples per day: "))

prob_of_not_running_out = int(input("What maximum probability of running out do you want to determine? (e.g, 5 for probability of running out is at max 5%)? "))

X = stats.poisson(lam)

prob_enough_containers = 0

minimum_num = -1

cdf_of_min = 0

for i in range(lam * 2): # try all possibilities up to twice the number

cdf = X.cdf(i)

print(f"Number of containers: {i}, P(X<={i}) = {cdf}")

if cdf > 1 - prob_of_not_running_out / 100 and minimum_num == -1:

minimum_num = i

cdf_of_min = cdf

print(f"You should bring {minimum_num} containers to have a maximum of {prob_of_not_running_out}% chance of running out.")

81 of 111

Limited sample containers, follow-up

Number of samples per day: What maximum probability of running out do you want to determine? 15

(e.g, 5 for probability of running out is at max 5%)? 5

Number of containers: 0, P(X<=0) = 3.0590232050182594e-07

Number of containers: 1, P(X<=1) = 4.894437128029217e-06

Number of containers: 2, P(X<=2) = 3.930844818448459e-05

...

Number of containers: 21, P(X<=21) = 0.9468935935407288

Number of containers: 22, P(X<=22) = 0.9672557550672212

Number of containers: 23, P(X<=23) = 0.9805354256279772

Number of containers: 24, P(X<=24) = 0.9888352197284497

Number of containers: 25, P(X<=25) = 0.9938150961887332

Number of containers: 26, P(X<=26) = 0.9966881018388968

Number of containers: 27, P(X<=27) = 0.9982842160889877

Number of containers: 28, P(X<=28) = 0.9991392772943934

Number of containers: 29, P(X<=29) = 0.9995815503316723

You should bring 22 containers to have a maximum of 5% chance of running out.

82 of 111

Poisson in Python

Function	Description
X.pmf(k)	P(X = k)
X.cdf(k)	P(X ≤ k)
X.mean()	E[X]
X.var()	Var(X)
X.std()	Std(X)

from scipy import stats # great package

X = stats.poisson(2.5) # X ~ Poi(λ = 2.5)

print(X.pmf(2)) # P(X = 2)

83 of 111

Four Prototypical Trajectories

Poisson can approximate a Binomial!

Wait why would you want to do that?

1) Binomial can be expensive to compute.

2) Connections help build math intuition.

84 of 111

Storing Data in DNA

All the movies, images, emails and other digital data from more than 600 smartphones (10,000 gigabytes) can be stored in the faint pink smear of DNA at the end of this test tube.

85 of 111

Storing Data in DNA

Will more than 1% of DNA storage become corrupt?

In DNA (and real networks) store large strings
Length n ≈ 10⁴
Probability of corruption of each base pair is very small p ≈ 10^-6
X ~ Bin(10⁴, 10^-6) is unwieldy to compute

Extreme n and p values arise in many cases

# bit errors in steam sent over a network
# of servers crashes in a day in giant data center

86 of 111

Storing Data in DNA

Will the DNA storage become corrupt?

In DNA (and real networks) store large strings
Length n ≈ 10⁴
Probability of corruption of each base pair is very small p ≈ 10^-6
X ~ Poi(λ = 10⁴ * 10^-6 = 0.01)

The “rate” here is the number of corruptions per string

87 of 111

Poisson is a Binomial in the Limit

Poisson approximates Binomial where n is large, p is small, and λ = np is “moderate”
Different interpretations of "moderate"

n > 20 and p < 0.05
n > 100 and p < 0.1

Really, Poisson is Binomial as

n ➔ ∞ and p ➔ 0, where np = λ

88 of 111

Bin(10,0.3) vs Bin(100,0.03) vs Poi(3)

89 of 111

Owner unknown…

A Real License Plate Seen at Stanford

90 of 111

Poisson can be used to approximate a Binomial where n is large and p is small.

91 of 111

Central Moments with Poisson

Recall: Y ~ Bin(n, p)

E[Y] = np
Var(Y) = np(1 – p)

X ~ Poi(λ) where λ = np (n ➔ ∞ and p ➔ 0)

E[X] = np = λ
Var(X) = np(1 – p) = λ(1 – 0) = λ
Yes, expectation and variance of Poisson are same

92 of 111

Poisson Paradigm

Poisson can still provide a good way to model an event, even when assumptions are “mildly” violated. Can apply Poisson approximation when...

“Successes” in trials are not entirely independent.

Example: # entries in each bucket in large hash table

Probability of “Success” p in each trial varies slightly.

Example: average # requests to web server/sec. may fluctuate slightly due to load on network

93 of 111

Web Server Load

Consider requests to a web server in 1 second

In past, server load averages 2 hits/second
X = # hits server receives in a second
What is P(X < 5)?

Solution

94 of 111

Web Server Load

We can do this calculation in Python a couple of different ways

95 of 111

Web Server Load

We can do this calculation in Python a couple of different ways

>>> import math

>>> poi_sum = 0

>>> for i in range(5):

... poi_sum += math.e**-2 * 2**i / math.factorial(i)

...

>>> poi_sum

0.9473469826562889

96 of 111

Web Server Load

We can do this calculation in Python a couple of different ways

>>> from scipy import stats

>>> X = stats.poisson(2)

>>> X.cdf(4)

np.float64(0.9473469826562889)

97 of 111

Probability for Extreme Weather?

98 of 111

Hurricanes per Year since 1851

99 of 111

Four Prototypical Trajectories

To the code!

100 of 111

Historically ~ Poisson(8.5)

101 of 111

What is the probability of over 15 hurricanes in a season given that the distribution doesn’t change?

Let X = # hurricanes in a year. X ~ Poi(8.5)

Solution:

This is the pmf of a Poisson. Your favorite programming language has a function for it

= 0.0135

Improbability Drive

102 of 111

Four Prototypical Trajectories

Twice since 1966 there have been two years with over 30 hurricanes

103 of 111

What is the probability of over 30 hurricanes in a season given that the distribution doesn’t change?

Let X = # hurricanes in a year. X ~ Poi(8.5)

Solution:

Improbability Drive

This is the pdf of a Poisson. Your favorite programming language has a function for it

* Challenge: Calculate the probability of two years with over 30 hurricanes

104 of 111

The Distribution has Changed

105 of 111

Four Prototypical Trajectories

What’s up?

106 of 111

What’s Up?

107 of 111

CO2 leads to Hotter Oceans

107

108 of 111

What’s Up?

109 of 111

Four Prototypical Trajectories

Next Time

110 of 111

Bernoulli:

indicator of coin flip X ~ Ber(p)

Binomial:

# successes in n coin flips X ~ Bin(n, p)

Poisson:

# successes in n coin flips X ~ Poi(λ)

Geometric:

# coin flips until success X ~ Geo(p)

Negative Binomial:

# trials until r successes X ~ NegBin(r, p)

Zipf:

The popularity rank of a random word, from a natural language
X ~ Zipf(s)

Discrete Distributions