6.042/18.062J Mathematics for Computer Science
November 30, 2006
Tom Leighton and Ronitt Rubinfeld
Lecture Notes
Expected Value I
The expectation or expected value of a random variable is a single number that tells
you a lot about the behavior of the variable. Roughly, the expectation is the average value,
where each value is weighted according to the probability that it comes up. Formally, the
expected value (also known as the average or mean) of a random variable R defined on a
sample space S is:
Ex (R) =
∑
w∈S
R(w) Pr (w)
To appreciate its significance, suppose S is the set of students in a class, and we select a
student uniformly at random. Let R be the selected student’s exam score. Then Ex (R) is
just the class average— the first thing everyone want to know after getting their test back!
In the same way, expectation is usually the first thing one wants to determine about any
random variable.
Let’s work through an example. LetR be the number that comes up on a fair, six-sided
die. Then the expected value of R is:
Ex (R) =
6∑
k=1
k
(
1
6
)
= 1 · 1
6
+ 2 · 1
6
+ 3 · 1
6
+ 4 · 1
6
+ 5 · 1
6
+ 6 · 1
6
=
7
2
This calculation shows that the name “expected value” is a little misleading; the random
variable might never actually take on that value. You can’t roll a 31
2
on an ordinary die!
Also note that the mean of a random variable is not the same as the median. The
median is the midpoint of a distribution, i.e., the point x for which the random variable
is at most x a half of the time, and greater than x the other half of the time.
Definition 1. The median of R is x ∈ Range(R) such that Pr(R ≤ x) ≤ 1
2
and Pr(R > x) < 1
2
.
We note that sometimes the median of R is defined as the point for which Pr(R ≤ x) <
1
2
and Pr(R > x) ≤ 1
2
. For example, for a single roll of a 6-sided die, the median is 4. In
this class we will not focus much attention on the median, but rather we will focus on the
expected value, which is much more interesting and useful.
2
Expected Value I
1 Betting on Coins
Jessica, Angelina, and Arvind