Bootstrapping
Chris Gregg
CS109, Stanford University
Autumn, 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: Dec
2nd
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
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
24
Chris Piech, CS109
Motivating example
25
Chris Piech, CS109
Motivating example
26
Chris Piech, CS109
Population
27
Chris Piech, CS109
Sample
28
Chris Piech, CS109
Sample
29
Collect one (or more) numbers from each person
Chris Piech, CS109
Chris Piech, CS109
A sample, mathematically
31
Chris Piech, CS109
A sample, mathematically
32
Chris Piech, CS109
A sample, mathematically
33
Chris Piech, CS109
A sample, mathematically
34
Chris Piech, CS109
A sample, mathematically
35
Chris Piech, CS109
A sample, mathematically
36
Chris Piech, CS109
A sample, mathematically
37
2x
Chris Piech, CS109
A sample, mathematically
38
2x
Chris Piech, CS109
A sample, mathematically
39
2x
Chris Piech, CS109
A sample, mathematically
40
2x
Chris Piech, CS109
A single sample
41
A happy�person
(+ 1 kitten)
Chris Piech, CS109
Our Report to Bhutan Government (after talking to 200 ppl)
42
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
44
Chris Piech, CS109
Estimating the population variance
45
Chris Piech, CS109
Estimating the population variance
46
population�variance
Chris Piech, CS109
Estimating the population variance
47
population�variance
population mean
Chris Piech, CS109
Estimating the population variance
48
population�variance
population mean
Chris Piech, CS109
Estimating the population variance
49
population�variance
population mean
sample�variance
Chris Piech, CS109
Estimating the population variance
50
population�variance
population mean
sample�variance
Chris Piech, CS109
Estimating the population variance
51
population�variance
population mean
sample�variance
sample mean
Chris Piech, CS109
52
population�variance
population mean
Chris Piech, CS109
53
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
54
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
55
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
56
0�Happiness
population�variance
population mean
150
Chris Piech, CS109
57
0�Happiness
population�variance
population mean
150
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
sample�variance
sample mean
population�variance
population mean
Chris Piech, CS109
61
sample�variance
sample mean
population�variance
population mean
0�Happiness
150
Chris Piech, CS109
62
population�variance
sample�variance
population mean
sample mean
0�Happiness
150
Chris Piech, CS109
63
population�variance
sample�variance
population mean
sample mean
0�Happiness
150
Chris Piech, CS109
64
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
65
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
66
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
67
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
68
150
0�Happiness
population�variance
sample�variance
population mean
sample mean
Chris Piech, CS109
69
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
71
Bug!
Chris Piech, CS109
Estimating the population variance
72
Bug!
Chris Piech, CS109
Estimating the population variance
73
population�variance
Bug!
Chris Piech, CS109
Estimating the population variance
74
population�variance
population mean
Bug!
Chris Piech, CS109
Estimating the population variance
75
population�variance
population mean
Bug!
Chris Piech, CS109
Estimating the population variance
76
population�variance
population mean
sample�variance
Bug!
Chris Piech, CS109
Estimating the population variance
77
population�variance
population mean
sample�variance
sample mean
Bug!
Chris Piech, CS109
Estimating the population variance
78
population�variance
population mean
sample�variance
sample mean
Chris Piech, CS109
79
(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)
81
83
Bhutan
Average Happiness
Average Happiness
0
450
Bhutan
Variance of Happiness
Happiness2
0
Chris Piech, CS109
But what about error bars???
82
83
Bhutan
Average Happiness
Average Happiness
0
450
Bhutan
Variance of Happiness
Happiness2
0
By CLT:
Chris Piech, CS109
Sample mean by the CLT
83
Chris Piech, CS109
Sample mean by the CLT
84
Chris Piech, CS109
Sample mean by the CLT
85
Chris Piech, CS109
Equations we used to get those values
86
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???
87
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!
88
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!
89
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!
90
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!
91
What is the std of the sample variance, calculated from 200 people?
Chris Piech, CS109
Hypothetical – You have the underlying distribution!
92
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!
93
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!
94
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???
98
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!
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
Here comes the award winning idea….
Chris Piech, CS109
But Wait – What If You Actually Have a Good Estimate?
101
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
102
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
103
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
104
The underlying distribution
The sample distribution
(aka the histogram of your data)
Chris Piech, CS109
Algorithm
105
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
106
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
107
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
108
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
109
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
110
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
111
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
112
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
113
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
114
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
115
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
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
Vars = [472.7]
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
Vars = [472.7]
Chris Piech, CS109
Bootstrapping of Variance
118
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
119
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
120
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
121
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
122
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)
124
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
125
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
126
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
127
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
128
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
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
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
131
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
132
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
133
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
134
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
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
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
137
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
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
Means = [82.7]
Chris Piech, CS109
Bootstrapping of Means
139
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
140
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
141
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
142
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
143
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
144
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
145
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
148
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
149
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
150
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)
151
[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)
152
[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)
153
[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)
154
[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)
155
[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)
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:
[94]
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:
[94]
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:
[94]
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:
[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)
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, 90]
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, 90]
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, 90]
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, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = True)
165
[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)
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, 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, 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, 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, 90]
Chris Piech, CS109
Four Prototypical Trajectories
Now with replace = False
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
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:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
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:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
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:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
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:
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
176
[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)
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:
[94]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
178
[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)
179
[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)
180
[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)
181
[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)
182
[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)
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]
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, 90]
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, 90]
Chris Piech, CS109
np.random.choice(samples, K, replace = False)
186
[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)
187
[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)
188
[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)
189
[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
191
Bootstrap Algorithm (sample):
Chris Piech, CS109
Four Prototypical Trajectories
To the code!
Chris Piech, CS109
The Distribution of the Sampling Variance
193
Chris Piech, CS109
194
Bootstrap provides a way to calculate probabilities of statistics using code.
Chris Piech, CS109
195
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?
198
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
199
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
200
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
201
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
202
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
203
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
205
P value: 0.008
Observed diff = 0.7
Chris Piech, CS109
Every* Science Result needs a p-value!
206
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
208
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
209
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
210
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