COMP9020 23T1
Week 10
Expected Values, Course Review
Textbook (R & W) - Ch. 9, Sec. 9.2-9.4
Problem set week 10
1
Random Variables
Definition
An (integer) random variable is a function from Ω to Z.
In other words, it associates a number value with every outcome.
Random variables are often denoted by X ,Y ,Z , . . .
2
Example
Random variable Xs
def
= sum of rolling two dice
Ω = {(1, 1), (1, 2), . . . , (6, 6)}
Xs((1, 1)) = 2 Xs((1, 2)) = 3 = Xs((2, 1)) . . .
Example
9.3.3 Buy one lottery ticket for $1. The only prize is $1M.
Ω = {win, lose} XL(win) = $999, 999 XL(lose) = −$1
3
Expectation
Definition
The expected value (often called “expectation” or “average”) of
a random variable X is
E (X ) =
∑
k∈Z
P(X = k) · k
4
Example
The expected sum when rolling two dice is
E (Xs) =
1
36
· 2 + 2
36
· 3 + . . .+ 6
36
· 7 + . . .+ 1
36
· 12 = 7
Example
9.3.3 Buy one lottery ticket for $1. The only prize is $1M. Each
ticket has probability 6 · 10−7 of winning.
E (XL) = 6 · 10−7 · $999, 999 + (1− 6 · 10−7) · −$1 = −$0.4
NB
Expectation is a truly universal concept; it is the basis of all
decision making, of estimating gains and losses, in all actions
under risk. Historically, a rudimentary concept of expected value
arose long before the notion of probability.
5
Theorem (linearity of expected value)
E (X + Y ) = E (X ) + E (Y )
E (c · X ) = c · E (X )
Example
The expected sum when rolling two dice can be computed as
E (Xs) = E (X1) + E (X2) = 3.5 + 3.5 = 7
since E (Xi ) =
1
6 · 1 + 16 · 2 + . . .+ 16 · 6, for each die Xi
6
Example
E (Sn), where Sn
def
= |no. of heads in n tosses|
‘hard way’
E (Sn) =
∑n
k=0 P(Sn = k) · k =
∑n
k=0
1
2n
(n
k
) · k
since there are
(n
k
)
sequences of n tosses with k heads,
and each sequence has the probability 12n
= 12n
∑n
k=1
n
k
(n−1
k−1
)
k = n2n
∑n−1
k=0
(n−1
k
)
= n2n · 2n−1 = n2
using the ‘binomial identity’
∑n
k=0
(n
k
)
= 2n
‘easy way’
E (Sn) = E (S
1
1 + . . .+ S
n
1 ) =
∑
i=1...n E (S
i
1) = nE (S1) = n · 12
Note: Sn
def
= |heads in n tosses| while each S i1 def= |heads in 1 toss|
7
Example
E (Sn), where Sn
def
= |no. of heads in n tosses|
‘hard way’
E (Sn) =
∑n
k=0 P(Sn = k) · k =
∑n
k=0
1
2n
(n
k
) · k
since there are
(n
k
)
sequences of n tosses with k heads,
and each sequence has the probability 12n
= 12n
∑n
k=1
n
k
(n−1
k−1
)
k = n2n
∑n−1
k=0
(n−1
k
)
= n2n · 2n−1 = n2
using the ‘binomial identity’
∑n
k=0
(n
k
)
= 2n
‘easy way’
E (Sn) = E (S
1
1 + . . .+ S
n
1 ) =
∑
i=1...n E (S
i
1) = nE (S1) = n · 12
Note: Sn
def
= |heads in n tosses| while each S i1 def= |heads in 1 toss|
8
Example
E (Sn), where Sn
def
= |no. of heads in n tosses|
‘hard way’
E (Sn) =
∑n
k=0 P(Sn = k) · k =
∑n
k=0
1
2n
(n
k
) · k
since there are
(n
k
)
sequences of n tosses with k heads,
and each sequence has the probability 12n
= 12n
∑n
k=1
n
k
(n−1
k−1
)
k = n2n
∑n−1
k=0
(n−1
k
)
= n2n · 2n−1 = n2
using the ‘binomial identity’
∑n
k=0
(n
k
)
= 2n
‘easy way’
E (Sn) = E (S
1
1 + . . .+ S
n
1 ) =
∑
i=1...n E (S
i
1) = nE (S1) = n · 12
Note: Sn
def
= |heads in n tosses| while each S i1 def= |heads in 1 toss|
9
NB
If X1,X2, . . . ,Xn are independent, identically distributed random
variables, then E (X1 + X2 + . . .+ Xn) happens to be the same as
E (nX1), but these are very different random variables.
10
Example
You face a quiz consisting of six true/false questions, and your
plan is to guess the answer to each question (randomly, with
probability 0.5 of being right). There are no negative marks, and
answering four or more questions correctly suffices to pass.
What is the probability of passing and what is the expected score?
To pass you would need four, five or six correct guesses. Therefore,
p(pass) =
(6
4
)
+
(6
5
)
+
(6
6
)
64
=
15 + 6 + 1
64
≈ 34%
The expected score from a single question is 0.5, as there is no
penalty for errors. For six questions the expected value is 6 ·0.5 = 3
11
Example
You face a quiz consisting of six true/false questions, and your
plan is to guess the answer to each question (randomly, with
probability 0.5 of being right). There are no negative marks, and
answering four or more questions correctly suffices to pass.
What is the probability of passing and what is the expected score?
To pass you would need four, five or six correct guesses. Therefore,
p(pass) =
(6
4
)
+
(6
5
)
+
(6
6
)
64
=
15 + 6 + 1
64
≈ 34%
The expected score from a single question is 0.5, as there is no
penalty for errors. For six questions the expected value is 6 ·0.5 = 3
12
Exercise
9.3.7
An urn has m + n = 10 marbles, m ≥ 0 red and n ≥ 0 blue.
7 marbles selected at random without replacement.
What is the expected number of red marbles drawn?(m
0
)(n
7
)(10
7
) · 0 + (m1)(n6)(10
7
) · 1 + (m2)(n5)(10
7
) · 2 + . . .+ (m7)(n0)(10
7
) · 7
e.g. (5
2
)(5
5
)(10
7
) · 2 + (53)(54)(10
7
) · 3 + (54)(53)(10
7
) · 4 + (55)(52)(10
7
) · 5
=
10
120
· 2 + 50
120
· 3 + 50
120
· 4 + 10
120
· 5 = 420
120
= 3.5
13
Exercise
9.3.7
An urn has m + n = 10 marbles, m ≥ 0 red and n ≥ 0 blue.
7 marbles selected at random without replacement.
What is the expected number of red marbles drawn?(m
0
)(n
7
)(10
7
) · 0 + (m1)(n6)(10
7
) · 1 + (m2)(n5)(10
7
) · 2 + . . .+ (m7)(n0)(10
7
) · 7
e.g. (5
2
)(5
5
)(10
7
) · 2 + (53)(54)(10
7
) · 3 + (54)(53)(10
7
) · 4 + (55)(52)(10
7
) · 5
=
10
120
· 2 + 50
120
· 3 + 50
120
· 4 + 10
120
· 5 = 420
120
= 3.5
14
Example
Find the average waiting time for the first head, with no upper
bound on the ‘duration’ (one allows for all possible sequences of
tosses, regardless of how many times tails occur initially).
A = E (Xw ) =
∑∞
k=1 k · P(Xw = k) =
∑∞
k=1 k
1
2k
= 1
21
+ 2
22
+ 3
23
+ . . .
This can be evaluated by breaking the sum into a sequence of
geometric progressions
1
2
+
2
22
+
3
23
+ . . .
=
(
1
2
+
1
22
+
1
23
+ . . .
)
+
(
1
22
+
1
23
+ . . .
)
+
(
1
23
+ . . .
)
+ . . .
= 1 +
1
2
+
1
22
+ . . . = 2
15
Example
Find the average waiting time for the first head, with no upper
bound on the ‘duration’ (one allows for all possible sequences of
tosses, regardless of how many times tails occur initially).
A = E (Xw ) =
∑∞
k=1 k · P(Xw = k) =
∑∞
k=1 k
1
2k
= 1
21
+ 2
22
+ 3
23
+ . . .
This can be evaluated by breaking the sum into a sequence of
geometric progressions
1
2
+
2
22
+
3
23
+ . . .
=
(
1
2
+
1
22
+
1
23
+ . . .
)
+
(
1
22
+
1
23
+ . . .
)
+
(
1
23
+ . . .
)
+ . . .
= 1 +
1
2
+
1
22
+ . . . = 2
16
There is also a recursive ‘trick’ for solving the sum
A =
∞∑
k=1
k
2k
=
∞∑
k=1
k − 1
2k
+
∞∑
k=1
1
2k
=
1
2
∞∑
k=1
k − 1
2k−1
+ 1 =
1
2
A + 1
Now A = A2 + 1 and A = 2
NB
A much simpler but equally valid argument is that you expect ‘half’
a head in 1 toss, so you ought to get a ‘whole’ head in 2 tosses.
17
Theorem
The average number of trials needed to see an event with
probability p is A = 1p .
Proof: A =
∞∑
k=1
k · p · (1− p)k−1
=
∞∑
k=1
(k − 1) · p · (1− p)k−1 + p ·
∞∑
k=0
(1− p)k
=
∞∑
k=1
k · p · (1− p)k + p · 1
p
= (1− p) · A + 1
Exercise
9.4.12 A die is rolled until the first 4 appears. What is the
expected waiting time?
P(roll 4) = 16 hence E (no. of rolls until first 4) = 6
18
Theorem
The average number of trials needed to see an event with
probability p is A = 1p .
Proof: A =
∞∑
k=1
k · p · (1− p)k−1
=
∞∑
k=1
(k − 1) · p · (1− p)k−1 + p ·
∞∑
k=0
(1− p)k
=
∞∑
k=1
k · p · (1− p)k + p · 1
p
= (1− p) · A + 1
Exercise
9.4.12 A die is rolled until the first 4 appears. What is the
expected waiting time?
P(roll 4) = 16 hence E (no. of rolls until first 4) = 6
19
Example
To find an object X in an unsorted list L of elements, one needs to
search linearly through L. Let the probability of X ∈ L be p, hence
there is 1− p likelihood of X being absent altogether. Find the
expected number of comparison operations.
If the element is in the list, then the number of comparisons
averages to 1n (1 + . . .+ n); if absent we need n comparisons.
The first case has probability p, the second 1− p. Combining
these we find
En = p
1 + . . .+ n
n
+ (1−p)n = pn + 1
2
+ (1−p)n = (1− p
2
)n+
p
2
As one would expect, increasing p leads to a lower expected
number En.
20
Example
To find an object X in an unsorted list L of elements, one needs to
search linearly through L. Let the probability of X ∈ L be p, hence
there is 1− p likelihood of X being absent altogether. Find the
expected number of comparison operations.
If the element is in the list, then the number of comparisons
averages to 1n (1 + . . .+ n); if absent we need n comparisons.
The first case has probability p, the second 1− p. Combining
these we find
En = p
1 + . . .+ n
n
+ (1−p)n = pn + 1
2
+ (1−p)n = (1− p
2
)n+
p
2
As one would expect, increasing p leads to a lower expected
number En.
21
One may expect that this would indicate a practical rule — that
high probability of success might lead to a high expected value.
Unfortunately this is not the case in a great many practical
situations.
Many lottery advertisements claim that buying more tickets leads
to better expected results — and indeed, obviously you will have
more potentially winning tickets. However, the expected value
decreases when the number of tickets is increased.
As an example, let us consider a punter placing bets on a roulette
(outcomes: 0, 1 . . . 36). Tired of losing, he decides to place $1 on
24 ‘ordinary’ numbers a1 < a2 < . . . < a24, selected from among 1
to 36.
His probability of winning is high indeed — 2437 ≈ 65%; he scores
on any of his choices, and loses only on the remaining thirteen
numbers.
22
But what about his performance?
If one of his numbers comes up, say ai , he wins $35 from the
bet on that number and loses $23 from the bets on the
remaining numbers, thus collecting $12.
This happens with probability p = 2437 .
With probability q = 1337 none of his numbers appears, leading
to loss of $24.
The expected result
p · $12− q · $24 = $1224
37
− $2413
37
= −$24
37
≈ −65¢
23
Many so-called ’winning systems’ that purport to offer a winning
strategy do something akin — they provide a scheme for frequent
relatively moderate wins, but at the cost of an occasional very big
loss.
It turns out (it is a formal theorem) that there can be no system
that converts an ‘unfair’ game into a ’fair’ one. In the language of
decision theory, ‘unfair’ denotes a game whose individual bets have
negative expectation.
It can be easily checked that any individual bets on roulette, on
lottery tickets or on just about any commercially offered game
have negative expected value.
24
Standard Deviation and Variance
Definition
For random variable X with expected value (or: mean) µ = E (X ),
the standard deviation of X is
σ =
√
E ((X − µ)2)
and the variance of X is
σ2
Standard deviation and variance measure how spread out the
values of a random variable are. The smaller σ2 the more confident
we can be that X (ω) is close to E (X ), for a randomly selected ω.
NB
The variance can be calculated as E ((X − µ)2) = E (X 2)− µ2
25
Example
Random variable Xd
def
= value of a rolled die
µ = E (Xd) = 3.5
E (X 2d ) =
1
6
· 1 + 1
6
· 4 + 1
6
· 9 + 1
6
· 16 + 1
6
· 25 + 1
6
· 36 = 91
6
Hence, σ2 = E (X 2d )− µ2 =
35
12
⇒ σ ≈ 1.71
26
Exercise
9.5.10 (supp) Two independent experiments are performed.
P(1st experiment succeeds) = 0.7
P(2nd experiment succeeds) = 0.2
Random variable X counts the number of successful experiments.
(a) Expected value of X? E (X ) = 0.7 + 0.2 = 0.9
(b) Probability of exactly one success? 0.7 · 0.8 + 0.3 · 0.2 = 0.62
(c) Probability of at most one success? (b)+0.3 · 0.8 = 0.86
(e) Variance of X? σ2 = (0.62 · 1 + 0.14 · 4)− 0.92 = 0.37
27
Exercise
9.5.10 (supp) Two independent experiments are performed.
P(1st experiment succeeds) = 0.7
P(2nd experiment succeeds) = 0.2
Random variable X counts the number of successful experiments.
(a) Expected value of X? E (X ) = 0.7 + 0.2 = 0.9
(b) Probability of exactly one success? 0.7 · 0.8 + 0.3 · 0.2 = 0.62
(c) Probability of at most one success? (b)+0.3 · 0.8 = 0.86
(e) Variance of X? σ2 = (0.62 · 1 + 0.14 · 4)− 0.92 = 0.37
28
Cumulative Distribution Functions
Definition
The cumulative distribution function cdfX : Z −→ R of an
integer random variable X is defined as
cdfX (y) 7→
∑
k≤y
P(X = k)
cdfX (y) collects the probabilities P(X ) for all values up to y
Example
Cumulative distribution function for sum of 2 dice
0 1 2 3 4 5 6 7 8 9 10 11 12
0
0.5
1
29
Example: Binomial Distributions
Definition
Binomial random variables count the number of ‘successes’ in n
independent experiments with probability p for each experiment.
P(X = k) =
(
n
k
)
pk(1− p)n−k
cdfB(y) 7→
∑
k≤y
(
n
k
)
pk(1− p)n−k
Theorem
If X is a binomially distributed random variable based on n and p,
then E (X ) = n · p with variance σ2 = n · p · (1− p)
30
Example: Binomial Distributions
Definition
Binomial random variables count the number of ‘successes’ in n
independent experiments with probability p for each experiment.
P(X = k) =
(
n
k
)
pk(1− p)n−k
cdfB(y) 7→
∑
k≤y
(
n
k
)
pk(1− p)n−k
Theorem
If X is a binomially distributed random variable based on n and p,
then E (X ) = n · p with variance σ2 = n · p · (1− p)
31
Example (binomial distribution)
No. of heads in 5 coin tosses
0 1 2 3 4 5 6
0
0.4
cdf for no. of heads in 5 coin tosses
0 1 2 3 4 5
0
0.5
1
32
Exercise
9.4.10 An experiment is repeated 30,000 times with probability of
success 14 each time.
(a) Expected number of successes? E (X ) = 30, 000 · 14 = 7500
(b) Standard deviation? σ =
√
30, 000 · 14 · 34 = 75
33
Exercise
9.4.10 An experiment is repeated 30,000 times with probability of
success 14 each time.
(a) Expected number of successes? E (X ) = 30, 000 · 14 = 7500
(b) Standard deviation? σ =
√
30, 000 · 14 · 34 = 75
34
Normal Distribution
Fact
For large n, binomial distributions can be approximated by normal
distributions (a.k.a. Gaussian distributions) with mean µ = n · p
and variance σ2 = n · p · (1− p)
0 1 2 3 4 5 6
0
0.4
µ = 2.5
σ2 = 1.25
1√
2σ2pi
· e− (x−µ)
2
2σ2
35
Summary
Random variables X
Expected value E (X )
Mean µ, cdf, standard deviation σ, variance σ2
Coming up . . .
Exam
Holidays
36
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
number-, set-, relation- and graph theory
logic and proofs, recursion and induction
order of growth of functions
combinatorics and probability
In CS/CE these are used to:
formalise problem specifications and requirements
develop abstract solutions (algorithms)
analyse and prove properties of your programs
Examples:
The University Course Timetabling Problem (→ PDF)
COMP9801 (Extended Design and Analysis of Algorithms)
37
Course Review
COMP9024 – Data Structures and Algorithms (23T3)
Concept Used for
logic and proofs correctness of algorithms
properties of relations reachability in graphs
graphs shortest path problems
trees search trees
O (big-Oh) efficiency of algorithms & data structures
alphabets and words string algorithms
probability, expectation randomised algorithms
NB
“universitas” (Lat.) = sum of all things, a whole
By acquiring knowledge and enhancing your problem-solving skills,
you’re preparing yourself for the future
38
Course Review
COMP9024 – Data Structures and Algorithms (23T3)
Concept Used for
logic and proofs correctness of algorithms
properties of relations reachability in graphs
graphs shortest path problems
trees search trees
O (big-Oh) efficiency of algorithms & data structures
alphabets and words string algorithms
probability, expectation randomised algorithms
NB
“universitas” (Lat.) = sum of all things, a whole
By acquiring knowledge and enhancing your problem-solving skills,
you’re preparing yourself for the future
39
Assessment Summary
1 quizzes — max. mark 14
2 mid-term assignment — max. mark 26
3 final exam — max. mark 60
NB
QuizMark = max { quizzes, ExamMark * 1460 }
MidtermMark = max { mid-term, ExamMark * 2660 }
NB
To pass the course, the sum of your marks
Sum = QuizMark + MidtermMark + ExamMark
must be 50 or higher and your ExamMark must be 25 or higher.
40
Check your marks with classrun; Example:
FinalExam: 45/60
MidtermAsst: 19.5/26
Quiz: 11.3/14
Sum: 75.8
midterm: 17/26
quizzes: 11.3/14
Note: max{17, 45 * 2660} = 19.5
41
Final Exam
Goal: to check whether you are a competent computer scientist.
Requires you to demonstrate:
understanding of mathematical concepts
ability to apply these concepts and explain how they work
Lectures, study of problem sets and quizzes have built you up to
this point.
Prac Exams on course webpage (→ Practice exams)
42
Final Exam
2 hour (+10 mins reading time) online test
Wednesday, 3 May between 1:00pm and 3:15pm local time
NB
You must start the exam between 1:00pm and 1:05pm in order to
get the full 130 minutes (= 2 hours 10 mins)
Format:
Covers all of the contents of this course
8 numerical/short answer/multiple-choice (with ≥ 1 correct),
each worth 4 marks
4 open questions, each worth 7 marks
Maximum marks: 4*8 + 28 = 60
43
If you
. . . are uncertain about how to interpret a question
. . . are unsure about how to answer a question
. . . find a question too difficult
⇒ do answer to the best of your understanding
⇒ do focus on the questions that you find easier
⇒ do not agonise about a question or your answer after you’ve
submitted
44
Revision Strategy
Re-read lecture slides
Read the corresponding chapters in the book (R & W)
Review/solve problem sets
Solve more problems from the book
Attempt prac exams (paper-based) on course webpage
NB
Applying mathematical concepts to solve problems is a skill that
improves with practice
45
Fit To Sit
If you attend an exam
you declare that you are “fit to do so”
it is your only chance to pass (i.e. no second chances)
If during an exam you are unwell and can’t continue
stop working, take note of the time
immediately apply for Special Consideration
NB
If you experience a technical issue:
Take screenshots of as many of the following as possible:
error messages, screen not loading, timestamped speed tests,
power outage maps
If issue was severe, apply for Special Consideration after
conclusion of exam. Attach screenshots.
46
Assessment
Assessment is about determining how well you understand the
syllabus of this course.
If you can’t demonstrate your understanding, you don’t pass.
In particular, I can’t pass people just because ...
please, please, ... my family/friends will be ashamed of me
please, please, ... I tried really hard in this course
please, please, ... I’ll be excluded if I fail COMP9020
please, please, ... this is my final course to graduate
etc. etc.
(Failure is a fact of life. For example, my scientific papers or project
proposals get rejected sometimes too)
47
Assessment (cont’d)
Of course, assessment isn’t a “one-way street” ...
I get to assess you in the final exam
you get to assess me in UNSW’s MyExperience Evaluation
go to https://myexperience.unsw.edu.au/
login using zID@ad.unsw.edu.au and your zPass
Response rate (as of Monday): < 50%
Please fill it out ...
give me some feedback on how you might like the course to
run in the future
even if that is “Exactly the same. It was perfect this time.”
48
So What Was The Real Point?
The aim was for you to become a better computer scientist
more confident in your own ability to use formal methods
with a set of mathematical tools to draw on
able to choose the right tool and analyse/justify your choices
ultimately, enjoying solving problems in computer science
49
Finally
T h a t ’ s A l l F o l k s
Good Luck with the exam
and with your future computing studies