1 of 210

Bootstrapping

Chris Gregg

CS109, Stanford University

Autumn, 2026

2 of 210

Today, we do science!

3 of 210

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

4 of 210

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

5 of 210

GPT-4 Tells about the Importance of Bootstrapping

5

Chris Piech, CS109

6 of 210

GPT-4 Tells about the Importance of Bootstrapping

6

Chris Piech, CS109

7 of 210

GPT-4 Tells about the Importance of Bootstrapping

7

Chris Piech, CS109

8 of 210

In other words.

8

Datascientists

He bongclouded from level 400 data scientist to a level 3000 in hours

Chris Piech, CS109

9 of 210

In other words.

9

Datascientists

He bongclouded from level 400 data scientist to a level 3000 in hours

(Computer science)

Chris Piech, CS109

10 of 210

In other words.

10

Datascientists

He bongclouded from level 400 data scientist to a level 3000 in hours

(Computer science)

Chris Piech, CS109

11 of 210

Where are we in CS109?

11

You are here

Chris Piech, CS109

12 of 210

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

13 of 210

Four Prototypical Trajectories

<announcements>

Chris Piech, CS109

14 of 210

Pset 5 is Out

14

You’ll need Monday’s lecture for some of the later problems.

Chris Piech, CS109

15 of 210

Due: Dec

2nd

Chris Piech, CS109

16 of 210

Four Prototypical Trajectories

<end>

Chris Piech, CS109

17 of 210

Four Prototypical Trajectories

<review>

Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021

18 of 210

Central Limit Theorem (Summation)

  •  

18

 

Chris Piech, CS109

19 of 210

Central Limit Theorem (Average)

  •  

19

 

Chris Piech, CS109

20 of 210

Four Prototypical Trajectories

</review>

Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021

21 of 210

Any Geoguessers Out there?

Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021

22 of 210

Chris Piech, Lisa Yan and Jerry Cain, CS109, 2021

23 of 210

Four Prototypical Trajectories

Happiness in Bhutan

Chris Piech, CS109

24 of 210

Motivating example

24

Chris Piech, CS109

25 of 210

Motivating example

25

Chris Piech, CS109

26 of 210

Motivating example

  • You want to know the true mean and variance of happiness in Bhutan.
    • But you can’t ask everyone.
    • You poll 200 random people.
    • Your data looks like this:��Happiness = {72, 85, 79, 91, 68, …, 71}�
    • The mean of all these numbers is 83.
  • Is this the true mean happiness of Bhutanese people?

26

Chris Piech, CS109

27 of 210

Population

27

Chris Piech, CS109

28 of 210

Sample

28

Chris Piech, CS109

29 of 210

Sample

29

Collect one (or more) numbers from each person

Chris Piech, CS109

30 of 210

Chris Piech, CS109

31 of 210

A sample, mathematically

31

 

Chris Piech, CS109

32 of 210

A sample, mathematically

32

 

 

Chris Piech, CS109

33 of 210

A sample, mathematically

33

 

 

 

Chris Piech, CS109

34 of 210

A sample, mathematically

34

 

 

 

 

Chris Piech, CS109

35 of 210

A sample, mathematically

35

 

 

 

 

 

Chris Piech, CS109

36 of 210

A sample, mathematically

36

 

 

 

 

 

 

 

Chris Piech, CS109

37 of 210

A sample, mathematically

37

 

 

 

 

 

 

 

2x

Chris Piech, CS109

38 of 210

A sample, mathematically

38

 

 

 

 

 

 

 

 

2x

Chris Piech, CS109

39 of 210

A sample, mathematically

39

 

 

 

 

 

 

 

 

 

2x

Chris Piech, CS109

40 of 210

A sample, mathematically

40

 

 

 

 

 

 

 

 

 

 

2x

Chris Piech, CS109

41 of 210

A single sample

  •  

41

A happy�person

(+ 1 kitten)

Chris Piech, CS109

42 of 210

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

43 of 210

Four Prototypical Trajectories

Side quest: sample variance

Chris Piech, CS109

44 of 210

Estimating the population variance

44

 

Chris Piech, CS109

45 of 210

Estimating the population variance

  •  

45

 

Chris Piech, CS109

46 of 210

Estimating the population variance

  •  

46

 

population�variance

Chris Piech, CS109

47 of 210

Estimating the population variance

  •  

47

 

population�variance

population mean

Chris Piech, CS109

48 of 210

Estimating the population variance

  •  

48

 

population�variance

population mean

Chris Piech, CS109

49 of 210

Estimating the population variance

  •  

49

 

population�variance

population mean

sample�variance

Chris Piech, CS109

50 of 210

Estimating the population variance

  •  

50

 

population�variance

population mean

sample�variance

Chris Piech, CS109

51 of 210

Estimating the population variance

  •  

51

 

population�variance

population mean

sample�variance

sample mean

Chris Piech, CS109

52 of 210

 

52

 

population�variance

population mean

 

Chris Piech, CS109

53 of 210

 

53

0�Happiness

 

population�variance

population mean

 

150

 

Chris Piech, CS109

54 of 210

 

54

0�Happiness

 

 

population�variance

population mean

 

 

150

Chris Piech, CS109

55 of 210

 

55

0�Happiness

 

 

population�variance

population mean

 

 

150

 

Chris Piech, CS109

56 of 210

 

56

0�Happiness

 

 

population�variance

population mean

 

 

150

 

Chris Piech, CS109

57 of 210

 

57

0�Happiness

 

 

population�variance

population mean

 

 

150

 

Chris Piech, CS109

58 of 210

 

58

0�Happiness

 

 

population�variance

population mean

 

 

150

 

Chris Piech, CS109

59 of 210

 

59

 

0�Happiness

 

 

population�variance

population mean

 

 

150

 

Chris Piech, CS109

60 of 210

 

60

sample�variance

sample mean

 

 

population�variance

population mean

 

Chris Piech, CS109

61 of 210

 

61

sample�variance

sample mean

 

 

population�variance

population mean

 

0�Happiness

 

 

150

Chris Piech, CS109

62 of 210

 

62

 

population�variance

sample�variance

population mean

sample mean

 

 

0�Happiness

 

 

150

Chris Piech, CS109

63 of 210

 

63

 

population�variance

sample�variance

population mean

sample mean

 

 

0�Happiness

 

 

 

150

Chris Piech, CS109

64 of 210

 

64

150

0�Happiness

 

 

population�variance

sample�variance

population mean

sample mean

 

 

 

 

Chris Piech, CS109

65 of 210

 

65

150

0�Happiness

 

 

population�variance

sample�variance

population mean

sample mean

 

 

 

 

 

Chris Piech, CS109

66 of 210

 

66

150

0�Happiness

 

 

population�variance

sample�variance

population mean

sample mean

 

 

 

 

 

Chris Piech, CS109

67 of 210

 

67

150

0�Happiness

 

 

population�variance

sample�variance

population mean

sample mean

 

 

 

 

 

Chris Piech, CS109

68 of 210

 

68

150

0�Happiness

 

 

population�variance

sample�variance

population mean

sample mean

 

 

 

 

 

Chris Piech, CS109

69 of 210

 

69

This formula will always underestimate the variance…

150

0�Happiness

 

 

population�variance

sample�variance

population mean

sample mean

 

 

 

 

 

Chris Piech, CS109

70 of 210

Four Prototypical Trajectories

Ahhh! We are always underestimating!

What should we do?

Chris Piech, CS109

71 of 210

Estimating the population variance

71

 

Bug!

Chris Piech, CS109

72 of 210

Estimating the population variance

  •  

72

 

Bug!

Chris Piech, CS109

73 of 210

Estimating the population variance

  •  

73

 

population�variance

Bug!

Chris Piech, CS109

74 of 210

Estimating the population variance

  •  

74

 

population�variance

population mean

Bug!

Chris Piech, CS109

75 of 210

Estimating the population variance

  •  

75

 

population�variance

population mean

Bug!

Chris Piech, CS109

76 of 210

Estimating the population variance

  •  

76

 

population�variance

population mean

sample�variance

Bug!

Chris Piech, CS109

77 of 210

Estimating the population variance

  •  

77

 

population�variance

population mean

sample�variance

sample mean

Bug!

Chris Piech, CS109

78 of 210

Estimating the population variance

  •  

78

 

population�variance

population mean

sample�variance

sample mean

Chris Piech, CS109

79 of 210

 

79

 

(just for reference)

 

 

 

 

 

 

 

 

 

 

 

 

 

Chris Piech, CS109

80 of 210

Four Prototypical Trajectories

End Side Quest

Chris Piech, CS109

81 of 210

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

82 of 210

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

83 of 210

Sample mean by the CLT

83

 

Chris Piech, CS109

84 of 210

Sample mean by the CLT

84

 

 

Chris Piech, CS109

85 of 210

Sample mean by the CLT

85

 

 

 

Chris Piech, CS109

86 of 210

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

87 of 210

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

88 of 210

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

89 of 210

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

90 of 210

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

91 of 210

Hypothetical – You have the underlying distribution!

91

What is the std of the sample variance, calculated from 200 people?

Chris Piech, CS109

92 of 210

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

93 of 210

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

94 of 210

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

95 of 210

Four Prototypical Trajectories

[suspense]

Chris Piech, CS109

96 of 210

Four Prototypical Trajectories

Bootstrap:

Probability for Computer Scientists

Chris Piech, CS109

97 of 210

Four Prototypical Trajectories

Bootstraping allows you to:

  • Know the distribution of statistics
  • Calculate p values
  • Using computers
  • You totally could have invented it

Chris Piech, CS109

98 of 210

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

99 of 210

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

100 of 210

Four Prototypical Trajectories

Here comes the award winning idea….

Chris Piech, CS109

101 of 210

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

102 of 210

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

103 of 210

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

104 of 210

Bootstrapping Assumption

104

The underlying distribution

The sample distribution

(aka the histogram of your data)

Chris Piech, CS109

105 of 210

Algorithm

105

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the stat on the resample

You now have a distribution of your stat

​

Chris Piech, CS109

106 of 210

Bootstrapping of Variance

106

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the variance on the resample

You now have a distribution of your variances

​

Chris Piech, CS109

107 of 210

Bootstrapping of Variance

107

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

108 of 210

Bootstrapping of Variance

108

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

109 of 210

Bootstrapping of Variance

109

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

110 of 210

Bootstrapping of Variance

110

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

111 of 210

Bootstrapping of Variance

111

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Happiness

PMF

0

83

104

61

Chris Piech, CS109

112 of 210

Bootstrapping of Variance

112

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Happiness

PMF

0

83

104

61

Chris Piech, CS109

113 of 210

Bootstrapping of Variance

113

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the vars on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

114 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the vars on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

115 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

116 of 210

Bootstrapping of Variance

116

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Happiness

PMF

0

83

104

61

Vars = [472.7]

Chris Piech, CS109

117 of 210

Bootstrapping of Variance

117

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Happiness

PMF

0

83

104

61

Vars = [472.7]

Chris Piech, CS109

118 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

119 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

120 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the var on the resample

You now have a distribution of your vars

​

Chris Piech, CS109

121 of 210

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

122 of 210

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

123 of 210

Four Prototypical Trajectories

Validation with Sample Mean

Chris Piech, CS109

124 of 210

Bootstrapping of Means (we could do this with CLT)

124

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

125 of 210

Bootstrapping of Means

125

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

126 of 210

Bootstrapping of Means

126

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

127 of 210

Bootstrapping of Means

127

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

128 of 210

Bootstrapping of Means

128

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

129 of 210

Bootstrapping of Means

129

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

130 of 210

Bootstrapping of Means

130

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

131 of 210

Bootstrapping of Means

131

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

132 of 210

Bootstrapping of Means

132

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Happiness

PMF

0

83

104

61

Chris Piech, CS109

133 of 210

Bootstrapping of Means

133

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Happiness

PMF

0

83

104

61

Chris Piech, CS109

134 of 210

Bootstrapping of Means

134

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

135 of 210

Bootstrapping of Means

135

Happiness

PMF

0

83

104

61

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

136 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

137 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

138 of 210

Bootstrapping of Means

138

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Happiness

PMF

0

83

104

61

Means = [82.7]

Chris Piech, CS109

139 of 210

Bootstrapping of Means

139

Bootstrap Algorithm (sample):

Estimate the PMF using the sample

Repeat 10,000 times:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Happiness

PMF

0

83

104

61

Means = [82.7]

Chris Piech, CS109

140 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

141 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

142 of 210

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:

    • Draw len(sample) new samples from PMF
    • Recalculate the mean on the resample

You now have a distribution of your means

​

Chris Piech, CS109

143 of 210

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

144 of 210

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

145 of 210

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

146 of 210

Four Prototypical Trajectories

Contrast with Central Limit Theorem

Chris Piech, CS109

147 of 210

Four Prototypical Trajectories

Ok Good!

Chris Piech, CS109

148 of 210

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

149 of 210

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

150 of 210

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

151 of 210

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

152 of 210

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

153 of 210

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

154 of 210

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

155 of 210

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

156 of 210

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

157 of 210

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

158 of 210

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

159 of 210

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

160 of 210

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

161 of 210

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

162 of 210

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

163 of 210

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

164 of 210

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

165 of 210

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

166 of 210

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

167 of 210

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

168 of 210

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

169 of 210

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

170 of 210

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

171 of 210

Four Prototypical Trajectories

Now with replace = False

Chris Piech, CS109

172 of 210

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

173 of 210

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

174 of 210

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

175 of 210

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

176 of 210

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

177 of 210

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

178 of 210

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

179 of 210

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

180 of 210

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

181 of 210

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

182 of 210

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

183 of 210

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

184 of 210

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

185 of 210

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

186 of 210

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

187 of 210

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

188 of 210

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

189 of 210

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

190 of 210

OG Bootstrapping

Bootstrap Algorithm (sample):

  1. Estimate the PMF using the sample
  2. Repeat 10,000 times:
    1. Resample len(sample) from PMF
    2. Recalculate the stat on the resample
  3. You now have a distribution of your stat

​

Chris Piech, CS109

191 of 210

Bootstrapping in Practice

191

Bootstrap Algorithm (sample):

  1. Repeat 10,000 times:
    1. Choose len(sample) elems from sample, with replacement
    2. Recalculate the stat on the resample
  2. You now have a distribution of your stat

​

Chris Piech, CS109

192 of 210

Four Prototypical Trajectories

To the code!

Chris Piech, CS109

193 of 210

The Distribution of the Sampling Variance

193

Chris Piech, CS109

194 of 210

194

Bootstrap provides a way to calculate probabilities of statistics using code.

Chris Piech, CS109

195 of 210

195

Bradley Efron

Still a professor at Stanford

Won a National Science Medal

Invented bootstrapping in 1979

Chris Piech, CS109

196 of 210

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

197 of 210

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

198 of 210

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

199 of 210

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

200 of 210

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

201 of 210

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

202 of 210

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

203 of 210

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

204 of 210

Four Prototypical Trajectories

To the code!

Chris Piech, CS109

205 of 210

Distribution of Mean Diffs under Null Hypothesis

205

P value: 0.008

Observed diff = 0.7

Chris Piech, CS109

206 of 210

Every* Science Result needs a p-value!

206

P value: 0.008

Observed diff = 0.7

* almost

Chris Piech, CS109

207 of 210

Four Prototypical Trajectories

Food For Thought

(if extra time)

Chris Piech, CS109

208 of 210

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

209 of 210

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

210 of 210

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