Algorithmic Analysis
Chris Gregg
CS109, Stanford University
Autumn 2026
Learning Goals
4
Def: Law of Total Expectation
Def: Conditional Expectation
Four Prototypical Trajectories
<review>
Expectation
6
All the values that X can take on
The probability that X takes on that value
Limitation of Expectation
7
X = time to complete the medical diagnosis problem (in seconds)
Summarize the distribution in one number
Expectation of a Sum
E[X + Y] = E[X] + E[Y]
Generalized:
Holds regardless of dependency between Xi’s
8
Expectation of a Function
9
Law of unconscious statistician
So for example…
Four Prototypical Trajectories
End Review
11
Four practice examples to warm us up
Bool was Cool
12
Bool was Cool
13
Bool was Cool
14
Bool was Cool
15
Bernoulli aka Indicator Random Variables were studied extensively by George Boole
Bool was Cool
16
Boole died of being too cool
Bernoulli aka Indicator Random Variables were studied extensively by George Boole
Differential Privacy
18
Aims to provide means to maximize the accuracy of probabilistic queries while minimizing the probability of identifying its records.
Differential Privacy
19
Aims to provide means to maximize the accuracy of probabilistic queries while minimizing the probability of identifying its records.
Cynthia Dwork
Differential Privacy
20
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
100 independent values X1 … X100 where Xi ~ Bern(p)
What is returned
Differential Privacy
21
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
100 independent values X1 … X100 where Xi ~ Bern(p)
What is returned
Differential Privacy
22
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
What is E[Yi]?
100 independent values X1 … X100 where Xi ~ Bern(p)
What is returned
Differential Privacy
23
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
What is E[Yi]?
100 independent values X1 … X100 where Xi ~ Bern(p)
What is returned
Differential Privacy
24
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
What is E[Yi]?
100 independent values X1 … X100 where Xi ~ Bern(p)
What is returned
Differential Privacy
25
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
What is E[Yi]?
100 independent values X1 … X100 where Xi ~ Bern(p)
What is returned
Differential Privacy
26
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
Let
100 independent values X1 … X100 where Xi ~ Bern(p)
What is E[Z]?
What is returned
Differential Privacy
27
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
Let
100 independent values X1 … X100 where Xi ~ Bern(p)
What is E[Z]?
What is returned
Differential Privacy
28
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
Let
100 independent values X1 … X100 where Xi ~ Bern(p)
What is E[Z]?
What is returned
Differential Privacy
29
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
Let
100 independent values X1 … X100 where Xi ~ Bern(p)
What is E[Z]?
What is returned
Differential Privacy
30
# Maximize accuracy, while preserving privacy.
def calculateYi(Xi):
obfuscate = True if random.randint(0, 1) else False
if obfuscate:
return random.randint(0, 1)
else:
return Xi
Let
How do you estimate p?
Challenge: What is the probability that our estimate is good?
100 independent values X1 … X100 where Xi ~ Bern(p)
What is returned
Differential Privacy
31
Professor at Stanford
Story which continues to unfold…
What is Amazon?
32
Cape Town, 2006
What is Amazon?
34
* 74% of Amazons Profits
**More profitable than Amazon’s North
America commerce operations
https://www.fool.com/investing/2022/07/07/aws-chief-says-amazons-most-profitable-segment-is/
Computer Cluster Utilization
35
Computer Cluster Utilization
36
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
37
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
38
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
39
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
40
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
41
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
42
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
43
Since X is an expectation, can you express it as a sum?
Computer Cluster Utilization
44
Since X is an expectation, can you express it as a sum?
When stuck, brainstorm about random variables
Toy Collection
48
Toy Collection
49
Toy Collection
50
Toy Collection
51
Toy Collection
Can you express X as a sum of other random variables?
52
Toy Collection
53
Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.
X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]
Toy Collection
54
Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.
After i successes, the probability of the next success is p = (n – i) / n
X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]
Xi ~ Geo( p = (n – i) / n)
E[Xi] = 1 / p = n / (n – i)
Toy Collection
55
Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.
After i successes, the probability of the next success is p = (n – i) / n
X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]
Xi ~ Geo( p = (n – i) / n)
E[Xi] = 1 / p = n / (n – i)
Toy Collection
56
Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.
After i successes, the probability of the next success is p = (n – i) / n
X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]
Xi ~ Geo( p = (n – i) / n)
E[Xi] = 1 / p = n / (n – i)
(i = 0 to n-1)
Toy Collection
57
Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.
After i successes, the probability of the next success is p = (n – i) / n
X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]
Xi ~ Geo( p = (n – i) / n)
E[Xi] = 1 / p = n / (n – i)
(i = 0 to n-1)
Toy Collection
58
Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.
After i successes, the probability of the next success is p = (n – i) / n
X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]
Xi ~ Geo( p = (n – i) / n)
E[Xi] = 1 / p = n / (n – i)
(i = 0 to n-1)
Approches log(n)
Toy Collection
59
Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.
After i successes, the probability of the next success is p = (n – i) / n
X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]
Xi ~ Geo( p = (n – i) / n)
E[Xi] = 1 / p = n / (n – i)
(i = 0 to n-1)
Approches log(n)
60
Four Prototypical Trajectories
Conditional Expectation
Conditional Expectation
62
Analogously, continuous random variables:
Conditional Expectation
63
Conditional Expectation
64
Conditional Expectation
65
Conditional Expectation
66
Conditional Expectation
67
Four Prototypical Trajectories
Conditional Expectation as a Function
Conditional Expectation
69
Conditional Expectation
70
E[X|Y=y]
Conditional Expectation
71
E[X|Y=y]
This is a function with Y as input
Conditional Expectation
72
E[X|Y=y]
Conditional Expectation
73
E[X|Y=y]
Conditional Expectation
74
E[X|Y=y]
Conditional Expectation
75
E[X|Y=y]
Conditional Expectation
76
E[X|Y=y]
Conditional Expectation
77
E[X|Y=y]
Conditional Expectation
78
Doesn’t make sense. Take expectation of random variables, not events
This is a number:
This is a function of y:
Expectation
79
X = favorite number
Y = year in school
Expectation
80
X = favorite number
Y = year in school
Expectation
81
X = favorite number
Y = year in school
E[X] = 0 * 0.05 + … + 9 * 0.10 = 5.38
Conditional Expectation
82
E[ X | Y ] ?
X = favorite number
Y = year in school
Conditional Expectation
83
E[ X | Y ] ?
Year in school, Y = y | E[ X | Y = y ] |
2 | 5.5 |
3 | 5.8 |
4 | 6.0 |
5 | 4.7 |
X = favorite number
Y = year in school
Conditional Expectation
84
E[X | Y] ?
Year in school, Y = y | E[X | Y = y] |
2 | 5.5 |
3 | 5.8 |
4 | 6.0 |
5 | 4.7 |
X = favorite number
Y = year in school
Conditional Expectation
85
X = units in fall quarter
Y = year in school
E[X | Y] ?
Four Prototypical Trajectories
Want to see something cool?
What the heck does this give you?
87
Law of Total Expectation
88
Def of E[X|Y]
Law of Total Expectation
89
Def of E[X|Y]
Chain rule!
Law of Total Expectation
90
Def of E[X|Y]
Chain rule!
I switch the order of the sums
Law of Total Expectation
91
Def of E[X|Y]
Chain rule!
I switch the order of the sums
Move that x outside the y sum
Law of Total Expectation
92
Def of E[X|Y]
Chain rule!
I switch the order of the sums
Move that x outside the y sum
Marginalization
Law of Total Expectation
93
Def of E[X|Y]
Chain rule!
I switch the order of the sums
Move that x outside the y sum
Marginalization
Def of E[X]
Four Prototypical Trajectories
Law of Total Expectation
Law of Total Expectation
95
For any discrete random variable X and any discrete random variable Y
Recall the Law of Total Probability
96
(The Streaming Part)
How long does this code take to run?
97
Netflix streams millions of hours of videos per day. They REALLY care about the speed of the following code:
How long does this line of code take? Say 512 MB movie.
database.get_movie(movie_name)
How long does this code take to run?
98
database.get_movie(movie_name)
Millisecond Latency
99
Its in Palo Alto
database.get_movie(movie_name)
Minute Latency
100
I have the file
Many Minutes Latency
101
私はファイルを持っています
Are we done?
102
5mins across the world!!!!!!
103
I have the file
104
I have the file
2 hours
Four Prototypical Trajectories
Expected Run Time
Expected runtime
106
Location, l | E[Runtime | Location = l] | P(Location = l) |
Palo Alto | 0.3s | 0.10 |
SoCal | 1.6s | 0.50 |
Japan | 300.0s | 0.37 |
Space | 7200.0s | 0.03 |
Let Location (L for short) be the location where the movie file is stored
What is the expected runtime of
database.get_movie(movie_name)
Expected runtime
107
Location, l | E[Runtime | Location = l] | P(Location = l) |
Palo Alto | 0.3s | 0.10 |
SoCal | 1.6s | 0.50 |
Japan | 300.0s | 0.37 |
Space | 7200.0s | 0.03 |
Let Location (L for short) be the location where the movie file is stored
What is the expected runtime of
database.get_movie(movie_name)
Using the Law of Total Expectation
Expected runtime
108
Location, l | E[Runtime | Location = l] | P(Location = l) |
Palo Alto | 0.3s | 0.10 |
SoCal | 1.6s | 0.50 |
Japan | 300.0s | 0.37 |
Space | 7200.0s | 0.03 |
Let Location (L for short) be the location where the movie file is stored
What is the expected runtime of
database.get_movie(movie_name)
Using the Law of Total Expectation
Four Prototypical Trajectories
Analyze Recursive Code
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
110
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
111
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
112
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
113
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
114
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
115
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
116
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
117
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
118
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
119
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
120
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
121
Let Y = value returned by Recurse(). What is E[Y]?
Analyzing Recursive Code
int Recurse() {
int x = randomInt(1, 3); // Equally likely values
if (x == 1) return 3;
else if (x == 2) return (5 + Recurse());
else return (7 + Recurse());
}
122
Let Y = value returned by Recurse(). What is E[Y]?
123
Four Prototypical Trajectories
If we have time…
125
Your company has one job opening for a software engineer.
You have n candidates. But you have to say yes/no immediately after each interview!
Proposed algorithm: reject the first k and accept the next one who is better than all of them.
What’s the best value of k?
Hiring an Engineer
Aka The Secretary Problem
Aka The Optimal Stopping Problem
Aka The Marriage Problem
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
127
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
i
k
128
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
i
k
129
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
i
k
130
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
i
k
131
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
i
k
Hint: where is the best among the first i – 1 candidates?
132
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
i
k
Hint: where is the best among the first i – 1 candidates?
Here?
133
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
What is the
i
k
Hint: where is the best among the first i – 1 candidates?
Here?
134
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
i
k
Hint: where is the best among the first i – 1 candidates?
135
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
136
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
137
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
By the law of total expectation
138
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
By the law of total expectation
139
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
By the law of total expectation
140
n candidates, must say yes/no immediately after each interview.
Reject the first k, accept the next who is better than all of them.
What’s the best value of k?
B: event that you hire the best engineer
X: position of the best engineer on the interview schedule
Hiring and Engineer
By the law of total expectation
Fun fact. Optimized when:
Uncertainty Theory
141
Beta Distributions
Adding Random Vars
Central Limit Theorem
Sampling
Algorithmic Analysis
Thompson Sampling
Bootstrapping
Information Theory
As requested by CS faculty
Where are we in CS109?
142
On Friday…
Chris Piech, CS109