Bootstrapping
Chris Gregg
CS109, Stanford University
Summer, 2026
Today, we do science!
A real difference?
3
Learning in Context A |
4.44 |
3.36 |
5.87 |
2.31 |
... |
3.70 |
Learning in Context B |
2.15 |
3.01 |
2.02 |
1.43 |
... |
1.83 |
Claim: Group 1 and Group 2 are samples from different distributions with a 0.7 difference of means.
How confident are you in this claim?
18 students
23 students
Chris Piech, CS109
The Classic Science Test
4
Group 1 |
4.44 |
3.36 |
5.87 |
2.31 |
... |
3.70 |
Group 2 |
2.15 |
3.01 |
2.02 |
1.43 |
... |
1.83 |
Claim: Group 1 and Group 2 are samples from different distributions with a 0.7 difference of means.
How confident are you in this claim?
Chris Piech, CS109
GPT-4 Tells about the Importance of Bootstrapping
5
Chris Piech, CS109
GPT-4 Tells about the Importance of Bootstrapping
6
Chris Piech, CS109
GPT-4 Tells about the Importance of Bootstrapping
7
Chris Piech, CS109
In other words.
8
Datascientists
He bongclouded from level 400 data scientist to a level 3000 in hours
Chris Piech, CS109
In other words.
9
Datascientists
He bongclouded from level 400 data scientist to a level 3000 in hours
(Computer science)
Chris Piech, CS109
In other words.
10
Datascientists
He bongclouded from level 400 data scientist to a level 3000 in hours
(Computer science)
Chris Piech, CS109
Where are we in CS109?
11
You are here
Chris Piech, CS109
Uncertainty Theory
12
Beta Distributions
Adding Random Vars
Central Limit Theorem
Sampling
Algorithmic Analysis
Thompson Sampling
Bootstrapping
Information Theory +
Divergence
As requested by AI faculty
Chris Piech, CS109
Four Prototypical Trajectories
<announcements>
Chris Piech, CS109
Pset 5 is Out
14
You’ll need Monday’s lecture for some of the later problems.
Chris Piech, CS109
Due: Aug
10th
Chris Piech, CS109
Four Prototypical Trajectories
<end>
Chris Piech, CS109
Four Prototypical Trajectories
<review>
Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021
Central Limit Theorem (Summation)
18
Chris Piech, CS109
Central Limit Theorem (Average)
19
Chris Piech, CS109
Sample Mean and Standard Error for Song Averages
20
Chris Piech, CS109
Sample Mean and Standard Error for Pset Time Working
21
Error bars are standard error of the mean
Expectation of the sum of problems is sum of expectations:
pset1: 2.87 hours on answers�pset2: 4.23 hours on answers�pset3: 5.11 hours on answers
Total: 12.1 hours on answers
Budget: 50 hours for psets
Error bars are “standard error of the mean”
Chris Piech, CS109
Statistics Vs Distribution
22
22
Sampling statistics
Sampling distribution
vs
Chris Piech, CS109
[Aside] Distribution of PSet Completion Times
23
Grab Share (seconds)
Aside: could be Erlang, could be Gumbel
https://en.wikipedia.org/wiki/Erlang_distribution
Erlang
Gumbel
I don’t think its exponential. Must not be a poisson process!
Chris Piech, CS109
Time on PSets vs PEP Scores
24
Error bars are ”standard error of the mean”
14 Hours
7 Hours
Correlation is 0.2
p-value < 0.001
Chris Piech, CS109
Four Prototypical Trajectories
</review>
Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021
Any Geoguessers Out there?
Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021
Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021
Four Prototypical Trajectories
Happiness in Bhutan
Chris Piech, CS109
Motivating example
29
Chris Piech, CS109
Motivating example
30
Chris Piech, CS109
Motivating example
31
Chris Piech, CS109
Population
32
Chris Piech, CS109
Sample
33
Chris Piech, CS109
Sample
34
Collect one (or more) numbers from each person
Chris Piech, CS109
Chris Piech, CS109
A sample, mathematically
36
Chris Piech, CS109
A sample, mathematically
37
Chris Piech, CS109
A sample, mathematically
38
Chris Piech, CS109
A sample, mathematically
39
Chris Piech, CS109
A sample, mathematically
40
Chris Piech, CS109
A sample, mathematically
41
Chris Piech, CS109
A sample, mathematically
42
2x
Chris Piech, CS109
A sample, mathematically
43
2x
Chris Piech, CS109
A sample, mathematically
44
2x
Chris Piech, CS109
A sample, mathematically
45
2x
Chris Piech, CS109
A single sample
46
A happy�person
(+ 1 kitten)
Chris Piech, CS109
Our Report to Bhutan Government (after talking to 200 ppl)
47
83
Bhutan
Average Happiness
Average Happiness
0
450
Bhutan
Variance of Happiness
Happiness2
0
Chris Piech, CS109
Four Prototypical Trajectories
Side quest: sample variance
Chris Piech, CS109
Estimating the population variance
49
Chris Piech, CS109
Estimating the population variance
50
Chris Piech, CS109
Estimating the population variance
51
population�variance
Chris Piech, CS109
Estimating the population variance
52
population�variance
population mean
Chris Piech, CS109
Estimating the population variance
53
population�variance
population mean
Chris Piech, CS109
Estimating the population variance
54
population�variance
population mean
sample�variance
Chris Piech, CS109
Estimating the population variance
55
population�variance
population mean
sample�variance
Chris Piech, CS109
Estimating the population variance
56
population�variance
population mean
sample�variance
sample mean
Chris Piech, CS109
57
population�variance
population mean
Chris Piech, CS109
58
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
59
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
60
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
61
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
62
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
63
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
64
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
65
sample�variance
sample mean
population�variance
population mean
Chris Piech, CS109
66
sample�variance
sample mean
population�variance
population mean
0�Happiness
150
Chris Piech, CS109
67
population�variance
sample�variance
population mean
sample mean
0�Happiness
150
Chris Piech, CS109
68
population�variance
sample�variance
population mean
sample mean
0�Happiness
150
Chris Piech, CS109
69
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
70
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
71
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
72
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
73
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
74
This formula will always underestimate the variance…
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
Four Prototypical Trajectories
Ahhh! We are always underestimating!
What should we do?
Chris Piech, CS109
Estimating the population variance
76
Bug!
Chris Piech, CS109
Estimating the population variance
77
Bug!
Chris Piech, CS109
Estimating the population variance
78
population�variance
Bug!
Chris Piech, CS109
Estimating the population variance
79
population�variance
population mean
Bug!
Chris Piech, CS109
Estimating the population variance
80
population�variance
population mean
Bug!
Chris Piech, CS109
Estimating the population variance
81
population�variance
population mean
sample�variance
Bug!
Chris Piech, CS109
Estimating the population variance
82
population�variance
population mean
sample�variance
sample mean
Bug!
Chris Piech, CS109
Estimating the population variance
83
population�variance
population mean
sample�variance
sample mean
Chris Piech, CS109
84
(just for reference)
Chris Piech, CS109
Four Prototypical Trajectories
End Side Quest
Chris Piech, CS109
Our Report to Bhutan Government (after talking to 200 ppl)
86
83
Bhutan
Average Happiness
Average Happiness
0
450
Bhutan
Variance of Happiness
Happiness2
0
Chris Piech, CS109
But what about error bars???
87
83
Bhutan
Average Happiness
Average Happiness
0
450
Bhutan
Variance of Happiness
Happiness2
0
By CLT:
Chris Piech, CS109
Sample mean by the CLT
88
Chris Piech, CS109
Sample mean by the CLT
89
Chris Piech, CS109
Sample mean by the CLT
90
Chris Piech, CS109
Equations we used to get those values
91
sample�variance
estimate
sample mean
sample�mean
estimate
Std error of the mean
estimate
sample variance
Our best guess at the true mean
Our best guess at the true variance
How wrong do we think our mean estimate is?
Chris Piech, CS109
But what about error bars???
92
83
Bhutan
Average Happiness
Average Happiness
0
450
Bhutan
Variance of Happiness
Happiness2
0
By CLT:
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
93
83
Happiness
Probability Density
0
83
104
61
Plot twist: I give you the entire underlying distribution
How wrong is an estimate of sample variance, calculated from 200 people?
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
94
What is the std of the sample variance, calculated from 200 people?
Plot twist: I give you the entire underlying distribution
83
Happiness
Probability Density
0
83
104
61
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
95
What is the std of the sample variance, calculated from 200 people?
Plot twist: I give you the entire underlying distribution
83
Happiness
Probability Density
0
83
104
61
Answer: 10,000 times take a mock sample of 200, calculate the sample variance
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
96
What is the std of the sample variance, calculated from 200 people?
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
97
brute_force_algorithm():
# Estimate distribution of Sample Var with
# infinite resources
sample_vars = []
Repeat 10,000 times:
new_samples = collect_new_samples(n=200)
sample_var = calculate_sample_var(new_samples)
sample_vars.append(sample_var)
# You now have a distribution of sample vars
What is the std of the sample variance, calculated from 200 people?
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
98
brute_force_algorithm():
# Estimate distribution of Sample Var with
# infinite resources
sample_vars = []
Repeat 10,000 times:
new_samples = collect_new_samples(n=200)
sample_var = calculate_sample_var(new_samples)
sample_vars.append(sample_var)
# You now have a distribution of sample vars
sample_vars = [472.7, 478.4,
469.2, …, 476.2]
What is the std of the sample variance, calculated from 200 people?
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
99
brute_force_algorithm():
# Estimate distribution of Sample Var with
# infinite resources
sample_vars = []
Repeat 10,000 times:
new_samples = collect_new_samples(n=200)
sample_var = calculate_sample_var(new_samples)
sample_vars.append(sample_var)
# You now have a distribution of sample vars
sample_vars = [472.7, 478.4,
469.2, …, 476.2]
What is the std of the sample variance, calculated from 200 people?
Chris Piech, CS109
Four Prototypical Trajectories
[suspense]
Chris Piech, CS109
Four Prototypical Trajectories
Bootstrap:
Probability for Computer Scientists
Chris Piech, CS109
Four Prototypical Trajectories
Bootstraping allows you to:
Chris Piech, CS109
But what about error bars???
103
83
Bhutan
Average Happiness
Average Happiness
0
450
Bhutan
Variance of Happiness
Happiness2
0
By CLT:
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
104
brute_force_algorithm():
# Estimate distribution of Sample Var with
# infinite resources
sample_vars = []
Repeat 10,000 times:
new_samples = collect_new_samples(n=200)
sample_var = calculate_sample_var(new_samples)
sample_vars.append(sample_var)
# You now have a distribution of sample vars
sample_vars = [472.7, 478.4,
469.2, …, 476.2]
What is the std of the sample variance, calculated from 200 people?
Chris Piech, CS109
Four Prototypical Trajectories
Here comes the award winning idea….
Chris Piech, CS109
But Wait – What If You Actually Have a Good Estimate?
106
83
Happiness
Probability Density
0
83
104
61
You can estimate the PMF of the underlying distribution, using your sample.*
* This is just a histogram of your data!!
Chris Piech, CS109
Key Insight
107
90,
92,
92,
93,
94,
94,
94,
95,
IID Samples
90
92
93
94
95
91
Sample Distribution
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Chris Piech, CS109
Key Insight
108
90,
92,
92,
93,
94,
94,
94,
95,
IID Samples
90
92
93
94
95
91
Sample Distribution
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Chris Piech, CS109
Bootstrapping Assumption
109
The underlying distribution
The sample distribution
(aka the histogram of your data)
Chris Piech, CS109
Algorithm
110
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your stat
Chris Piech, CS109
Bootstrapping of Variance
111
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your variances
Chris Piech, CS109
Bootstrapping of Variance
112
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
113
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
114
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
115
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
116
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Happiness
PMF
0
83
104
61
Chris Piech, CS109
Bootstrapping of Variance
117
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Happiness
PMF
0
83
104
61
Chris Piech, CS109
Bootstrapping of Variance
118
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
119
Happiness
PMF
0
83
104
61
Vars = [472.7]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
120
Happiness
PMF
0
83
104
61
Vars = [472.7]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
121
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Happiness
PMF
0
83
104
61
Vars = [472.7]
Chris Piech, CS109
Bootstrapping of Variance
122
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Happiness
PMF
0
83
104
61
Vars = [472.7]
Chris Piech, CS109
Bootstrapping of Variance
123
Happiness
PMF
0
83
104
61
Vars = [472.7, 478.4]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
124
Happiness
PMF
0
83
104
61
Vars = [472.7, 478.4]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
125
Happiness
PMF
0
83
104
61
Vars = [472.7, 478.4, 469.2, …, 476.2]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your vars
Chris Piech, CS109
Bootstrapping of Variance
126
Variance values (S2)
Probability mass of variances (S2)
0
500
Sample Vars = [472.7, 478.4, 469.2, …, 476.2]
1000
Aside: the distribution of variance depends on the underlying distribution
If the underlying distribution is Gaussian, variance is “chi-squared”
Bootstrapping doesn’t need to know that…
Chris Piech, CS109
Our Report to Bhutan Government
127
83
Bhutan
0
450
Bhutan
0
Claim: The average happiness of Bhutan is 83 ± 2
Variance of Happiness S2
Chris Piech, CS109
Four Prototypical Trajectories
Validation with Sample Mean
Chris Piech, CS109
Bootstrapping of Means (we could do this with CLT)
129
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
130
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
131
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
132
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
133
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
134
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
135
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
136
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
137
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Happiness
PMF
0
83
104
61
Chris Piech, CS109
Bootstrapping of Means
138
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Happiness
PMF
0
83
104
61
Chris Piech, CS109
Bootstrapping of Means
139
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
140
Happiness
PMF
0
83
104
61
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
141
Happiness
PMF
0
83
104
61
Means = [82.7]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
142
Happiness
PMF
0
83
104
61
Means = [82.7]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
143
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Happiness
PMF
0
83
104
61
Means = [82.7]
Chris Piech, CS109
Bootstrapping of Means
144
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Happiness
PMF
0
83
104
61
Means = [82.7]
Chris Piech, CS109
Bootstrapping of Means
145
Happiness
PMF
0
83
104
61
Means = [82.7, 83.4]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
146
Happiness
PMF
0
83
104
61
Means = [82.7, 83.4]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
147
Happiness
PMF
0
83
104
61
Means = [82.7, 83.4, 82.9, 91.4, 79.3, 82.1, …, 81.7]
Bootstrap Algorithm (sample):
Estimate the PMF using the sample
Repeat 10,000 times:
You now have a distribution of your means
Chris Piech, CS109
Bootstrapping of Means
148
Means = [82.7, 83.4, 82.9, 91.4, 79.3, 82.1, …, 81.7]
Mean value
Probability of mean from sample of size 200
0
83
104
61
Chris Piech, CS109
Bootstrapping of Means
149
Means = [82.7, 83.4, 82.9, 91.4, 79.3, 82.1, …, 81.7]
Mean value
Probability of mean from sample of size 200
0
83
104
61
Chris Piech, CS109
Bootstrapping of Means
150
What is the probability that the mean is in the range 81 to 85?
Mean value
Probability of mean from sample of size 200
0
83
104
61
Chris Piech, CS109
Four Prototypical Trajectories
Contrast with Central Limit Theorem
Chris Piech, CS109
Four Prototypical Trajectories
Ok Good!
Chris Piech, CS109
Bootstrapping in Practice
153
def resample(samples, K):
# Estimate the PMF using the samples
# Draw K new samples from the PMF
X
PMF
0
83
104
61
Original samples
Chris Piech, CS109
Bootstrapping in Practice
154
def resample(samples, K):
# Estimate the PMF using the samples
# Draw K new samples from the PMF
return np.random.choice(samples, K,
replace = True)
X
PMF
0
83
104
61
Original samples
Chris Piech, CS109
Bootstrapping in Practice
155
def resample(samples, K):
# Estimate the PMF using the samples
# Draw K new samples from the PMF
return np.random.choice(samples, K,
replace = True)
X
PMF
0
83
104
61
Original samples
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
156
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
157
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
158
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
159
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
160
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
161
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
162
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
163
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
164
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
166
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
167
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
168
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
169
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
170
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
171
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
172
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
173
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
174
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
175
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90, 90]
Chris Piech, CS109
Four Prototypical Trajectories
Now with replace = False
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
177
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
178
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
179
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
180
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
181
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
182
[90, 92, 92, 93, 94, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
183
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Removed 94
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
184
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Removed 94
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
185
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
186
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
187
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
188
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
189
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
190
[90, 92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
191
[92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Removed 90
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
192
[92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Removed 90
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
193
[92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Removed 90
The probability of sampling a 90 is no longer 0.1
The probability of sampling 94 is no longer 0.3
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
194
[92, 92, 93, 94, 94, 95]
Original Samples:
90
92
93
94
95
91
0.3
0.5
0.1
Probability Mass, P(X = k)
k
Resample:
[94, 90]
Removed 90
The probability of sampling a 90 is no longer 0.1
The probability of sampling 94 is no longer 0.3
Chris Piech, CS109
OG Bootstrapping
Bootstrap Algorithm (sample):
Chris Piech, CS109
Bootstrapping in Practice
196
Bootstrap Algorithm (sample):
Chris Piech, CS109
Four Prototypical Trajectories
To the code!
Chris Piech, CS109
The Distribution of the Sampling Variance
198
Chris Piech, CS109
199
Bootstrap provides a way to calculate probabilities of statistics using code.
Chris Piech, CS109
200
Bradley Efron
Still a professor at Stanford
Won a National Science Medal
Invented bootstrapping in 1979
Chris Piech, CS109
Four Prototypical Trajectories
Works for any statistic*
*as long as your samples are IID and the underlying distribution doesn’t have a long tail
Chris Piech, CS109
The Classic Science Test
Group 1 |
4.44 |
3.36 |
5.87 |
2.31 |
... |
3.70 |
Group 2 |
2.15 |
3.01 |
2.02 |
1.43 |
... |
1.83 |
Claim: Group 1 and Group 2 are samples from different distributions with a 0.7 difference of means.
How confident are you in this claim?
Chris Piech, CS109
A real difference?
203
Learning in Context A |
4.44 |
3.36 |
5.87 |
2.31 |
... |
3.70 |
Learning in Context B |
2.15 |
3.01 |
2.02 |
1.43 |
... |
1.83 |
Claim: Group 1 and Group 2 are samples from different distributions with a 0.7 difference of means.
How confident are you in this claim?
18 students
23 students
Chris Piech, CS109
The Null Hypothesis
204
There is no difference between the two groups, so everyone is drawn from the same distribution. Any difference you observe is due to sampling error.
The universal distribution
Group A Samples
Group B Samples
Chris Piech, CS109
P-Value
205
The probability of obtaining test results at least as extreme as the result actually observed, if the null hypothesis is correct
The universal distribution
Group A Samples
Group B Samples
Diff: 3.1-2.4 = 0.7
What do we think about this? Okay or not?
Chris Piech, CS109
P-Value
206
A p-value measures how likely it would be to observe results at least as extreme as ours if the null hypothesis were true. In other words, it tells us whether the observed difference could reasonably be explained by random chance alone.
The universal distribution
Group A Samples
Group B Samples
Diff: 3.1-2.4 = 0.7
What do we think about this? Okay or not?
Chris Piech, CS109
P-Value
207
For example, if we observed a difference in means of 0.7 and computed a p-value of 0.008, that means that fewer than 1% of random samples from the same population would produce a difference that large just by chance.
The universal distribution
Group A Samples
Group B Samples
Diff: 3.1-2.4 = 0.7
What do we think about this? Okay or not?
Chris Piech, CS109
P-Value
208
A small p-value suggests that the observed difference would be very unlikely if the two samples really came from the same population, so it provides evidence that the populations are probably different.
The universal distribution
Group A Samples
Group B Samples
Diff: 3.1-2.4 = 0.7
What do we think about this? Okay or not?
Chris Piech, CS109
Four Prototypical Trajectories
To the code!
Chris Piech, CS109
Distribution of Mean Diffs under Null Hypothesis
210
P value: 0.008
Observed diff = 0.7
Chris Piech, CS109
Every* Science Result needs a p-value!
211
P value: 0.008
Observed diff = 0.7
* almost
Chris Piech, CS109
Four Prototypical Trajectories
Food For Thought
(if extra time)
Chris Piech, CS109
Puzzle
213
Results of flipping a coin 20 times. Give your belief distribution of p:
4 tails, 16 heads
How can you build distribution for p without using a prior?
Chris Piech, CS109
Two Opinions on Distributions
214
Results of flipping a coin 20 times. Give your belief distribution of p:
4 tails, 16 heads
Bayesian:
Let’s use Laplace prior X ~ Beta(2, 2)
X ~ Beta(a = 18, b = 6)
Chris Piech, CS109
Two Opinions on Distributions
215
Results of flipping a coin 20 times. Give your belief distribution of p:
4 tails, 16 heads
Bayesian:
Let’s use Laplace prior X ~ Beta(2, 2)
X ~ Beta(a = 18, b = 6)
Frequentist:
Let’s bootstrap
Chris Piech, CS109