Central Limit Theorem

Chris Gregg

CS109, Stanford University

Summer 2026

Uncertainty Theory

2

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

Independent Random Variables

3

Recall the comma means “and”

Chris Piech, CS109

Independent Random Variables

4

Recall the comma means “and”

Because they are independent, “and” becomes multiplication

Chris Piech, CS109

Four Prototypical Trajectories

New Definition

Chris Piech, CS109

• Consider n random variables X₁, X₂, ... X_n
• X_i are all independently and identically distributed (I.I.D.)
• All have the same PMF (if discrete) or PDF (if continuous)
• All have the same expectation
• All have the same variance

6

IID Random Variables

IID

iid

Quick check

7

Chris Piech, CS109

Quick check

8

Chris Piech, CS109

Quick check

9

Chris Piech, CS109

Quick check

10

Chris Piech, CS109

Quick check

11

Chris Piech, CS109

Four Prototypical Trajectories

What happens when you add random variables?

Four Prototypical Trajectories

Why should you care?

Zero Sum Games

How do you model zero sum games?

What is the probability that the Warriors win?

15

Motivating Idea: Zero Sum Games

How it works:

• Each team has an “ELO” score S, calculated based on their past performance.
• Each game, the team has ability A ~ N(S, 200²)
• The team with the higher sampled ability wins.

1797

1555

ability

p

Arpad Elo

16

Motivating Idea: Zero Sum Games

How do we do this???

Sum of Two Die?

17

17

Value dice 1

Value dice 2

Each outcome

S = {

}

Roll two 6-sided dice. What is P(sum = 7)?

Chris Piech, CS109

Sum of Two Die = 7?

18

18

S = {

}

E = in blue

Value dice 1

Value dice 2

Each outcome

Roll two 6-sided dice. What is P(sum = 7)?

Chris Piech, CS109

Sum of Two Die = 7?

19

19

S = {

}

E = in blue

Value dice 1

Value dice 2

Each outcome

Roll two 6-sided dice. What is P(sum = 7)?

Chris Piech, CS109

Sum of Two Die = 7?

20

20

S = {

}

E = in blue

Value dice 1

Value dice 2

Each outcome

Roll two 6-sided dice. What is P(sum = 7)?

Chris Piech, CS109

Sum of Two Die = 10?

21

21

Value dice 1

Value dice 2

Each outcome

S = {

}

Roll two 6-sided dice. What is P(sum = 10)?

E = in blue

Chris Piech, CS109

Sum of Two Die = 10?

22

22

Value dice 1

Value dice 2

Each outcome

S = {

}

Roll two 6-sided dice. What is P(sum = 10)?

E = in blue

Chris Piech, CS109

Four Prototypical Trajectories

End Review

24

Sum of Two Dice

X_i is the outcome of dice roll i

25

Sum of Two Dice

X_i is the outcome of dice roll i

X_i s are iid

26

Sum of Three Dice

X_i is the outcome of dice roll i

X_i s are iid

27

Sum of One Dice

This is the PMF of the sum of one dice

28

Sum of One Dice

This is the PMF of the sum of one dice

29

This is the PMF of the sum of two dice

Why is there more mass in the middle?

Sum of Two Dice

30

This is the PMF of the sum of two dice

Why is there more mass in the middle?

Sum of Two Dice

31

This is the PMF of the sum of three dice

Why is there more mass in the middle?

Sum of Three Dice

32

This is the PMF of the sum of three dice

Why is there more mass in the middle?

Sum of Three Dice

Four Prototypical Trajectories

Sum of 50 dice?

Insight to Convolution

34

Imagine a game

where each player independently scores between 0 and 100 points:

​

Let X be the amount of points you score.

Let Y be the amount of points your opponent scores.

Let’s say you know P(X = x) and P(Y = y).

​

What is the probability of a tie?

Note: these could be any distribution! As long as you know the PMFs

Chris Piech, CS109

Insight to Convolution

35

Imagine a game

where each player independently scores between 0 and 100 points:

​

Let X be the amount of points you score.

Let Y be the amount of points your opponent scores.

Let’s say you know P(X = x) and P(Y = y).

​

What is the probability of a tie?

Note: these could be any distribution! As long as you know the PMFs

Chris Piech, CS109

Insight to Convolution

36

Imagine a game

where each player independently scores between 0 and 100 points:

​

Let X be the amount of points you score.

Let Y be the amount of points your opponent scores.

Let’s say you know P(X = x) and P(Y = y).

​

What is the probability of a tie?

Note: these could be any distribution! As long as you know the PMFs

Chris Piech, CS109

Insight to Convolution

37

Imagine a game

where each player independently scores between 0 and 100 points:

​

Let X be the amount of points you score.

Let Y be the amount of points your opponent scores.

Let’s say you know P(X = x) and P(Y = y).

​

What is the probability sum = 10?

Chris Piech, CS109

38

In English: What is the probability that

X + Y = n?

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

39

In English: What is the probability that

X + Y = n?

…

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

40

In English: What is the probability that

X + Y = n?

…

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

41

In English: What is the probability that

X + Y = n?

…

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

42

In English: What is the probability that

X + Y = n?

…

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

43

In English: What is the probability that

X + Y = n?

…

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

44

In English: What is the probability that

X + Y = n?

…

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

45

In English: What is the probability that

X + Y = n?

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

46

Since this is the OR of mutually exclusive events

In English: What is the probability that

X + Y = n?

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

47

If the random variables are independent

Since this is the OR of mutually exclusive events

In English: What is the probability that

X + Y = n?

What is the PMF for X + Y,

Consider the case where X and Y are discrete and non-negative

Wildlife Disease Outbreak

48

Researchers are tracking a contagious disease in two distinct animal populations.

​

Population A has Bin(n = 5, p = 0.1) infections

Population B has Bin(n = 8, p = 0.5) infections.

​

Find the exact probability distribution of total infections across A and B.

Sometimes the PMF is zero

k

P(A + B = k)

def main():

for k in range(0, 5+8+1):

pr_k = get_prob_sum(k)

print(f"{k},{pr_k}")

�def get_prob_sum(k):

A = stats.binom(5, 0.1)

B = stats.binom(8, 0.5)

pr = 0

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

pr += A.pmf(i) * B.pmf(k-i)

return pr

Chris Piech, CS109

49

Discrete Vs Continuous

Discrete

Continuous

Infinity is necessary when the values can be negative

Four Prototypical Trajectories

Convolution: The fanciest way to say “adding random variables”

​

Four Prototypical Trajectories

Side Quest

Sometimes Adding is Easy:

• Let X and Y be independent binomials with the same value for p:
• X ~ Bin(n₁, p) and Y ~ Bin(n₂, p)

52

Sum of Independent Binomials

• Let X and Y be independent binomials with the same value for p:
• X ~ Bin(n₁, p) and Y ~ Bin(n₂, p)
• X + Y ~ Bin(n₁ + n₂, p)

​

53

Sum of Independent Binomials

• Let X and Y be independent binomials with the same value for p:
• X ~ Bin(n₁, p) and Y ~ Bin(n₂, p)
• X + Y ~ Bin(n₁ + n₂, p)

​

• Intuition:
• X has n₁ trials and Y has n₂ trials
• Each trial has same “success” probability p
• Define Z to be n₁ + n₂ trials, each with success prob. p
• Z ~ Bin(n₁ + n₂, p), and also Z = X + Y

54

Sum of Independent Binomials

• Let X and Y be independent random variables
• X ~ Poi(λ₁) and Y ~ Poi(λ₂)
• X + Y ~ Poi(λ₁ + λ₂)

​

55

Sum of Independent Poissons

• Let X and Y be independent random variables
• X ~ N(μ₁, σ₁²) and Y ~ N(μ₂, σ₂²)
• X + Y ~ N(μ₁ + μ₂, σ₁² + σ₂²)

​

• Generally, have n independent random variables X_i ~ N(μ_i, σ_i²) for i = 1, 2, ..., n:

​

​

56

Sum of Independent Normals

• Let X and Y be independent random variables
• X ~ N(μ₁, σ₁²) and Y ~ N(μ₂, σ₂²)
• X + Y ~ N(μ₁ + μ₂, σ₁² + σ₂²)

​

• Generally, have n independent random variables X_i ~ N(μ_i, σ_i²) for i = 1, 2, ..., n:

​

​

57

Sum of Independent Normals

58

Linear Transform

Thinking of Y as a linear transform

Thinking of Y as the sum of independent normals

59

Linear Transform

Thinking of Y as a linear transform

Thinking of Y as the sum of independent normals

60

Linear Transform

Thinking of Y as a linear transform

Thinking of Y as the sum of independent normals

61

Linear Transform

Thinking of Y as a linear transform

Thinking of Y as the sum of independent normals

62

Linear Transform

Thinking of Y as a linear transform

Thinking of Y as the sum of independent normals

63

Linear Transform

X is not independent of X

Thinking of Y as a linear transform

Thinking of Y as the sum of independent normals

64

Zero Sum Games

How do you model zero sum games?

What is the probability that the Warriors win?

Gaussian Sampling and ELO ratings

65

Gaussian Sampling and ELO ratings

66

What is the probability that the Warriors win?

How do you model zero-sum games?

Gaussian Sampling and ELO ratings

67

Gaussian Sampling and ELO ratings

68

Gaussian Sampling and ELO ratings

69

Gaussian Sampling and ELO ratings

70

Gaussian Sampling and ELO ratings

71

Gaussian Sampling and ELO ratings

72

Arpad Elo

Gaussian Sampling and ELO ratings

73

Arpad Elo

Gaussian Sampling and ELO ratings

74

Arpad Elo

Probability of Winning a Game

75

Probability of Winning a Game

76

Probability of Winning a Game

77

Probability of Winning a Game

78

79

Virus Infections Revisited

• Say you are working with the WHO to plan a response to a the initial conditions of a virus:
• Two exposed groups
• P1: 50 people, each independently infected with p = 0.1
• P2: 100 people, each independently infected with p = 0.4
• Question: Probability of more than 40 infections?

80

Virus Infections Revisited

• Say you are working with the WHO to plan a response to a the initial conditions of a virus:
• Two exposed groups
• P1: 50 people, each independently infected with p = 0.1
• P2: 100 people, each independently infected with p = 0.4
• A = # infected in P1 A ~ Bin(50, 0.1) ≈ X ~ N(5, 4.5)
• B = # infected in P2 B ~ Bin(100, 0.4) ≈ Y ~ N(40, 24)
• What is P(≥ 40 people infected)?
• P(A + B ≥ 40) ≈ P(X + Y ≥ 39.5)
• X + Y = W ~ N(5 + 40 = 45, 4.5 + 24 = 28.5)

81

Virus Infections Revisited

• Say you are working with the WHO to plan a response to a the initial conditions of a virus:
• Two exposed groups
• P1: 50 people, each independently infected with p = 0.1
• P2: 100 people, each independently infected with p = 0.4
• A = # infected in P1 A ~ Bin(50, 0.1) ≈ X ~ N(5, 4.5)
• B = # infected in P2 B ~ Bin(100, 0.4) ≈ Y ~ N(40, 24)
• What is P(≥ 40 people infected)?
• P(A + B ≥ 40) ≈ P(X + Y ≥ 39.5)
• X + Y = W ~ N(5 + 40 = 45, 4.5 + 24 = 28.5)

82

Virus Infections Revisited

Four Prototypical Trajectories

End Side Quest

Sometimes Adding is Easy:

84

CON

We talked about sum of Binomial, Normal and Poisson…who’s missing from this party?

Uniform.

85

CON

• Let X and Y be independent random variables
• X ~ Uni(0, 1) and Y ~ Uni(0, 1) 🡪 f (x) = 1 for 0 ≤ x ≤ 1

86

Sum of Independent Uniforms

1

• Let X and Y be independent random variables
• X ~ Uni(0, 1) and Y ~ Uni(0, 1) 🡪 f (x) = 1 for 0 ≤ x ≤ 1

87

Sum of Independent Uniforms

1

1

• Let X and Y be independent random variables
• X ~ Uni(0, 1) and Y ~ Uni(0, 1) ➔ f (x) = 1 for 0 ≤ x ≤ 1

88

Sum of Independent Uniforms

1

1

For both X and Y

89

Chris Piech, CS109

90

a

0

1

2

Chris Piech, CS109

91

0

a

1

2

What if a = 0?

Chris Piech, CS109

92

0

a

1

2

Chris Piech, CS109

93

0

a

1

2

What if a = 0.5?

Chris Piech, CS109

94

0

a

1

2

Chris Piech, CS109

95

0

a

1

2

What if a = 1.5?

Chris Piech, CS109

96

0

a

1

2

Chris Piech, CS109

​

​

​

97

​

​

​

98

99

Four Prototypical Trajectories

Gotta care about summing more than two things….

Four Prototypical Trajectories

Sum of 100 uniforms???

101

Were talking about the sum of uniforms

Four Prototypical Trajectories

Sum of 100 poissons???

Next up: a beautiful result of probability theory!

103

Chris Piech, CS109

Next up: a beautiful result of probability theory!

104

Chris Piech, CS109

Central Limit Theorem

105

Chris Piech, CS109

Central Limit Theorem

106

Chris Piech, CS109

Central Limit Theorem

107

Chris Piech, CS109

Central Limit Theorem

108

Chris Piech, CS109

True happiness

109

Chris Piech, CS109

Sum of dice rolls

110

Chris Piech, CS109

Sum of dice rolls

111

Sum of 1�die roll

Chris Piech, CS109

Sum of dice rolls

112

Sum of 1�die roll

Sum of 2�dice rolls

Chris Piech, CS109

Sum of dice rolls

113

Sum of 1�die roll

Sum of 2�dice rolls

Sum of 3�dice rolls

Chris Piech, CS109

Sum of dice rolls

114

Sum of 1�die roll

Sum of 2�dice rolls

Sum of 3�dice rolls

How many ways�can you roll a total�of 3 vs 11?

Chris Piech, CS109

CLT explains a lot

115

Chris Piech, CS109

CLT explains a lot

116

Chris Piech, CS109

CLT explains a lot

117

Galton Board, by Sir Francis Galton�(1822-1911)

Chris Piech, CS109

CLT explains a lot

118

Chris Piech, CS109

CLT explains a lot

119

Chris Piech, CS109

CLT explains a lot

120

Proof:

Chris Piech, CS109

CLT explains a lot

121

Proof:

Chris Piech, CS109

CLT explains a lot

122

Proof:

Chris Piech, CS109

CLT explains a lot

123

Proof:

(substitute mean,�variance of Bernoulli)

Chris Piech, CS109

CLT explains a lot

124

Chris Piech, CS109

CLT explains a lot

125

Chris Piech, CS109

CLT explains a lot

126

Sample of�size 15,�sum values

Chris Piech, CS109

CLT explains a lot

127

Sample of�size 15,�sum values

Chris Piech, CS109

CLT explains a lot

128

Chris Piech, CS109

CLT explains a lot

129

Chris Piech, CS109

CLT explains a lot

130

Sample of�size 15,�average values

(sample mean)

Chris Piech, CS109

CLT explains a lot

131

Sample of�size 15,�average values

(sample mean)

Chris Piech, CS109

Proof Outline of CLT

132

Proof:

(this proof is beyond the scope of CS109)

Chris Piech, CS109

Proof Outline of CLT

133

Proof:

(this proof is beyond the scope of CS109)

Chris Piech, CS109

Proof Outline of CLT

134

Proof:

(this proof is beyond the scope of CS109)

Chris Piech, CS109

Proof Outline of CLT

135

Proof:

(this proof is beyond the scope of CS109)

Chris Piech, CS109

For Proof, see one of the many videos on YouTube, e.g.,

136

Chris Piech, CS109

For Proof, See Video 2

137

http://youtube.com/watch?v=oPQ4mNcqY7k&t=33s

Chris Piech, CS109

CLT example

138

Chris Piech, CS109

139

Chris Piech, CS109

140

Chris Piech, CS109

141

PDF

Chris Piech, CS109

142

Exact

PDF

Chris Piech, CS109

143

Exact

PDF

CLT approximation

Chris Piech, CS109

144

Exact

PDF

CLT approximation

Chris Piech, CS109

145

Exact

PDF

CLT approximation

Chris Piech, CS109

146

Exact

PDF

CLT approximation

Chris Piech, CS109

147

Chris Piech, CS109

148

PDF

Chris Piech, CS109

149

Exact

PDF

Chris Piech, CS109

150

Exact

PDF

CLT approximation

Chris Piech, CS109

151

Exact

PDF

CLT approximation

Chris Piech, CS109

152

n=10:

Chris Piech, CS109

153

PDF

n=10:

Chris Piech, CS109

154

Exact

PDF

n=10:

Chris Piech, CS109

155

Exact

PDF

CLT approximation

n=10:

Chris Piech, CS109

156

Exact

PDF

CLT approximation

n=10:

Chris Piech, CS109

157

Chris Piech, CS109

158

PDF

PDF

PDF

Chris Piech, CS109

159

PDF

PDF

PDF

Chris Piech, CS109

160

The sum of independent, identically distributed variables:

where

Is normally distributed:

Piech, CS109, Stanford University

161

What about other functions?

Sum of iid? Normal

Average of iid?

Max of iid?

Piech, CS109, Stanford University

162

Demo

https://onlinestatbook.com/stat_sim/sampling_dist/

Average of iid?

Piech, CS109, Stanford University

​

�

It’s play time!

163

Piech, CS109, Stanford University

164

Sum of Dice

Piech, CS109, Stanford University

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45
• Roll!

​

• And now the truth (according to the CLT)…

165

Sum of Dice

Piech, CS109, Stanford University

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45
• Roll!

​

• And now the truth (according to the CLT)…

166

Sum of Dice

Piech, CS109, Stanford University

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

167

Sum of Dice

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

168

Sum of Dice

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

169

Sum of Dice

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

170

Sum of Dice

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

171

Sum of Dice

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

172

Sum of Dice

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

173

Sum of Dice

• You will roll 10 6-sided dice (X₁, X₂, …, X₁₀)
• X = total value of all 10 dice = X₁ + X₂ + … + X₁₀
• Win if: X ≤ 25 or X ≥ 45

​

• Recall CLT:

​

• Determine P(X ≤ 25 or X ≥ 45) using CLT:

​

​

​

​

174

Sum of Dice

175

I know of scarcely anything so apt to impress the imagination as the wonderful form of cosmic order expressed by the ”[Central limit theorem]". The law would have been personified by the Greeks and deified, if they had known of it. It reigns with serenity and in complete self-effacement, amidst the wildest confusion. The huger the mob, and the greater the apparent anarchy, the more perfect is its sway. It is the supreme law of Unreason. Whenever a large sample of chaotic elements are taken in hand and marshalled in the order of their magnitude, an unsuspected and most beautiful form of regularity proves to have been latent all along.

- Sir Francis Galton

-

Wonderful Form of Cosmic Order

Piech, CS109, Stanford University