L17: Random Variables

▪ Reading: Rosen 7.4

1
 Random Variables
▪ Definition
A random variable is a function from the sample space
of an experiment to the set of real numbers, i.e., a
random variable assigns a real number to each
possible outcome.
▪ Note: This function is not random!
▪ Example
Suppose that a coin is flipped three times. Let 𝑋(𝑡) be
the random variable that equals the number of heads
that appear when 𝑡 is the outcome. Then 𝑋(𝑡) is the
function where:
𝑋(𝐻𝐻𝐻) = 3, 𝑋(𝑇𝑇𝑇) = 0,
𝑋(𝐻𝐻𝑇) = 𝑋(𝐻𝑇𝐻) = 𝑋(𝑇𝐻𝐻) = 2,
𝑋(𝑇𝑇𝐻) = 𝑋(𝑇𝐻𝑇) = 𝑋(𝐻𝑇𝑇) = 1.
2
 Distribution of a Random Variable
▪ Definition
The distribution of a random variable 𝑋 on a sample
space 𝑆 is the set of pairs (𝑟, 𝑝(𝑋 = 𝑟)) for all 𝑟 ∈ 𝑋(𝑆),
where 𝑝(𝑋 = 𝑟) is the probability that 𝑋 takes the value
𝑟, i.e., 𝑝 𝑋 = 𝑟 = σ𝑠∈𝑆,𝑋 𝑠 =𝑟 𝑝(𝑠)
▪ Example
Continuing with the previous example, we have
𝑝 𝑋 = 3 = 1/8
𝑝 𝑋 = 2 = 3/8
𝑝 𝑋 = 1 = 3/8
𝑝 𝑋 = 0 = 1/8

3
 Bernoulli Trials
▪ Definition:
Each performance of an experiment with two possible
outcomes is called a Bernoulli trial. The two possible
outcomes are generally referred to as success and
failure.
▪ Example:
A coin is biased so that the probability of heads is 2/3.
What is the probability that exactly four heads occur
when the coin is flipped seven times?
▪ Solution:
2 4 1 3
𝐶 7,4
3 3

4
 Binomial Distribution
▪ Theorem
Let 𝑋 be the number of successes in n independent
Bernoulli trials, with probability of success p and
probability of failure q = 1 − p. Then
𝑝(𝑋 = 𝑘) = 𝑏(𝑘: 𝑛, 𝑝) = 𝐶 𝑛, 𝑘 𝑝𝑘 𝑞 𝑛−𝑘
▪ Definition:
𝑋 follows the binomial distribution with parameters 𝑛
and 𝑝, and 𝑏(𝑘: 𝑛, 𝑝) is the pmf.
▪ Check (from the binomial theorem)
𝑛
𝑛 𝑘 𝑛−𝑘 𝑛
෍ 𝑝 𝑞 = 𝑝+𝑞 =1
𝑘
𝑘=0

5
 Binomial Distribution
▪ Question
What is Pr 10 ≤ 𝑋 ≤ 20 ?
▪ Solution
20 𝑛 𝑘 𝑛−𝑘
σ𝑘=10 𝑝 𝑞 ,
𝑘
which, unfortunately, has no closed form.
▪ For large 𝑛, and 𝑝 not too
close to 0 or 1, the normal
distribution approximates
binomial distribution well.
▪ A special case of the
central limit theorem.
▪ The Galton Board
6
 Continuous Probability Distribution
▪ Defined over a domain of real numbers
▪ Characterized by a probability density function (pdf)
▪ Example: The pdf of a normal (Gaussian) distribution
𝑥−𝜇 2
1 −
is 𝑓 𝑥 = 𝑒 2𝜎2 .
2𝜎 2 𝜋

▪ Remark: 𝑓(𝑥) does not represent a probability!

𝑏
▪ The probability of an interval: Pr 𝑎 ≤ 𝑋 ≤ 𝑏 = ‫𝑓 𝑎׬‬ 𝑥 𝑑𝑥
7
 Infinite Sample Space
▪ Example
Experiment: Flip a fair coin until it turns up heads.
Let random variable 𝑋 = the number of flips.
1/2

1/4
1/8
1/16
…
1 2 3 4 5
1 1 1
▪ Verify σ∞
𝑥=1 𝑝(𝑋 = 𝑥) = + + + ⋯ = 1
2 4 8
▪ The probability of the event that we get 3 or more
1 1 1
flips = 𝑝 𝑋 = 3 + 𝑝 𝑋 = 4 + ⋯ = + + ⋯ = .
8 16 4

8
 Geometric Distribution
▪ Theorem
Let 𝑋 be the number of independent Bernoulli trials
until success and the probability of success is p. Then
𝑝(𝑋 = 𝑘) = (1 − 𝑝)𝑘−1 𝑝
▪ Note: 𝑋 follows a geometric distribution
▪ Check: σ∞ 𝑖=0(1 − 𝑝) 𝑖𝑝 = 1

▪ Example:
Experiment: Roll 2 dice, probability of seeing a sum of
6 is 5/36. Let random variable X be number of trials
until getting a sum of 6.
31 5
▪ 𝑝 X = 3 = ( )2 ( )
36 36

9
 Expected Value
▪ Definition
The expected value (or expectation or mean) of a
random variable 𝑋 is
𝐸 𝑋 = ෍ 𝑝 𝑠 𝑋(𝑠)
𝑥∈𝑆
▪ Example
Let X be the number that comes up when a fair dice is
rolled. What is the expected value of X?
▪ Solution
The random variable 𝑋 takes the values 1, 2, 3, 4, 5,
or 6. Each has probability 1/6. It follows that

10
 Expected Value
▪ Recall 𝑝 𝑋 = 𝑟 = σ𝑠∈𝑆,𝑋 𝑠 =𝑟 𝑝(𝑠)
▪ Theorem
𝐸 𝑋 = ෍ 𝑝 𝑋=𝑟 𝑟
𝑟∈𝑋(𝑆)
▪ Example: Flip a coin twice. X is number of heads
𝑠 𝑋 𝑠 𝑝(𝑠)
HH 2 1/4 𝐸 𝑋 = ෍ 𝑝 𝑠 𝑋(𝑠)
TH 1 1/4 𝑥∈𝑆
1 1 1 1
= 2 +4 1 +4 1 +4 0 =1
HT 1 1/4 4

TT 0 1/4
𝑟 𝑝(𝑠)
2 1/4 𝐸 𝑋 = σ𝑟∈𝑋(𝑆) 𝑝 𝑋 = 𝑟 𝑟
1 1/2 =
1
2 +
1
1 +
1
0 =1
4 2 4
0 1/4 11
 Expected Value
▪ Recall 𝑝 𝑋 = 𝑟 = σ𝑠∈𝑆,𝑋 𝑠 =𝑟 𝑝(𝑠)
▪ Theorem
𝐸 𝑋 = ෍ 𝑝 𝑋=𝑟 𝑟
𝑟∈𝑋(𝑆)
▪ Example
Suppose that a coin is flipped three times. Let 𝑋(𝑡) be
the random variable that equals the number of heads
that appear when 𝑡 is the outcome. We know that
𝑝 𝑋 = 3 = 1/8
𝑝 𝑋 = 2 = 3/8
𝑝 𝑋 = 1 = 3/8
𝑝 𝑋 = 0 = 1/8
1 3 3 1
So 𝐸 𝑋 = ⋅ 3 + ⋅ 2 + ⋅ 1 + ⋅ 0 = 1.5
8 8 8 8
12
 Example: Binomial Distribution
▪ Recall that a random variable 𝑋 with the binomial
distribution with parameter 𝑛 and 𝑝, 𝑞 has
𝑝(𝑋 = 𝑘) = 𝐶 𝑛, 𝑘 𝑝𝑘 𝑞 𝑛−𝑘
▪ We can derive its expectation through a rather
complicated sequence of derivations:
𝐸 𝑋 = 𝑛𝑝

13
 Linearity of Expectations
▪ Theorem
If 𝑋𝑖 , 𝑖 = 1, 2, … , 𝑛 are random variables on S, and if a
and b are real numbers, then
▪ 𝐸(𝑋1 + 𝑋2 + ⋯ + 𝑋𝑛 ) = 𝐸(𝑋1 ) + 𝐸(𝑋2 ) + ⋯ + 𝐸(𝑋𝑛 )
▪ 𝐸(𝑎𝑋 + 𝑏) = 𝑎𝐸(𝑋) + 𝑏
▪ Proof

14
Proof (cnt’d)

15
 Example: Binomial Distribution
▪ 𝑋 is the number of successes in 𝑛 independent
Bernoulli trials, with success probability 𝑝 on each trial
▪ 𝑋 = 𝑋1 + 𝑋2 + ⋯ + 𝑋𝑛 ,
where 𝑋𝑖 = 1 if 𝑖th trial is successful and 0 otherwise
These 𝑋𝑖 ’s are called indicator random variables
▪ 𝐸 𝑋𝑖 = 𝑝 ⋅ 1 + 1 − 𝑝 ⋅ 0 = 𝑝
▪ 𝐸 𝑋 = 𝐸 𝑋1 + ⋯ + 𝑋𝑛 = 𝐸 𝑋1 + ⋯ + 𝐸 𝑋𝑛 = 𝑛𝑝

16
 Example: the Hatcheck Problem
▪ Question
A new employee started a job checking hats, but
forgot to put the claim check numbers on the hats. So,
the n customers just receive a random hat from those
remaining. What is the expected number of hat
returned correctly?
▪ Solution
Let X be the random variable that equals the number
of people who receive the correct hat. We can write
𝑋 = 𝑋1 + 𝑋2 + ∙∙∙ + 𝑋𝑛 ,
where 𝑋𝑖 = 1 if the 𝑖th person receives the correct hat
and 0 otherwise. (Note that they are not independent.)
𝐸 𝑋𝑖 = 1/𝑛.
𝐸 𝑋 = 𝐸 𝑋1 + ⋯ + 𝑋𝑛 = 𝐸 𝑋1 + ⋯ + 𝐸 𝑋𝑛 = 1
17
Example: Hiring Problem

Hire-Assistant(𝑛):
randomly permute all 𝑛 candiates
𝑏𝑒𝑠𝑡 ← 0
for 𝑖 ← 1 to 𝑛
interview candidate 𝑖
if candidate 𝑖 is better than 𝑏𝑒𝑠𝑡 then
fire 𝑏𝑒𝑠𝑡
hire candidate 𝑖
𝑏𝑒𝑠𝑡 ← 𝑖

▪ Questions: What’s the expected number of hires?

18
 Hiring Problem: Solution
▪ Let 𝑋𝑖 = 1 if you hire candidate 𝑖 and 0 otherwise.
▪ Let 𝑋 = number of hires = 𝑋1 + ⋯ + 𝑋𝑛 .
▪ 𝐸(𝑋𝑖 ) = 𝑝(𝑋𝑖 = 1) = 1/𝑖.
▪ Among the first 𝑖 candidates, the best has
probability 1/𝑖 to be placed at the 𝑖th position.
1 1 1
▪ 𝐸(𝑋) = 𝐸(𝑋1 ) + ⋯ + 𝐸(𝑋𝑛 ) = 1 + + ⋯+ + =
2 𝑛−1 𝑛
Θ(log 𝑛) .

19
 Example: Balls and Bins
▪ Question
Throw 𝑚 balls into 𝑛 bins randomly. How many boxes
will be empty in expectation?
▪ Solution
▪ Let 𝑋𝑖 = 1 if box 𝑖 is empty, and 0 otherwise.
▪ Let 𝑋 = number of empty boxes = 𝑋1 + ⋯ + 𝑋𝑛 .
1 𝑚
▪ 𝐸(𝑋𝑖 ) = 𝑝(𝑋𝑖 = 1) = 1 − .
𝑛
1 𝑚
▪ 𝐸 𝑋 = 𝐸 𝑋1 + ⋯ + 𝐸 𝑋𝑛 = 𝑛 1 −
𝑛
1 𝑛 𝑛
▪ If throwing 𝑛 balls into 𝑛 bins, 𝑛 1 − ≈ for
𝑛 𝑒
large 𝑛
20
 Average-case Analysis of Algorithms
▪ Definition
Let 𝑋 be the random variable representing the running
time (i.e., # of instructions) of an algorithm, when the
input is drawn from a certain distribution (usually,
uniform). Then the average-case running time of the
algorithm is 𝐸(𝑋).

21
 Example: Linear Search
procedure linear search(x:integer,
a1, a2, …,an: distinct integers)
i := 1
while (i ≤ n and x ≠ ai)
i := i + 1
if i ≤ n then location := i
else location := 0
return location
▪ Assume that 𝑥 is one of the 𝑎𝑖 ’s with equal probability
▪ For asymptotic analysis, it’s enough to count the
number of iterations, denoted as 𝑋
1 1 1 𝑛+1
▪ 𝐸 𝑋 = ⋅1+ ⋅2 +⋯+ ⋅𝑛 = = Θ(𝑛)
𝑛 𝑛 𝑛 2
22
Example: Insertion Sort
Insertion-Sort(𝐴):
for 𝑗 ← 2 to 𝑛 do
𝑘𝑒𝑦 ← 𝐴[𝑗]
𝑖 ←𝑗−1
while 𝑖 ≥ 1 and 𝐴[𝑖] > 𝑘𝑒𝑦 do
𝐴[𝑖 + 1] ← 𝐴[𝑖]
𝑖 ←𝑖−1
endwhile
𝐴 𝑖 + 1 ← 𝑘𝑒𝑦
endfor

sorted key unsorted

23
 Example: Insertion Sort
▪ Assumption: The input is a random permutation.
▪ For asymptotic analysis, it’s sufficient to count the total
number of iterations of the inner loop, denoted 𝑋
▪ 𝑋𝑖 : the # of iterations of the inner loop for inserting 𝑎𝑖
▪ 𝐸 𝑋 = 𝐸 𝑋1 + ⋯ + 𝑋𝑛 = 𝐸 𝑋1 + ⋯ + 𝐸 𝑋𝑛
▪ 𝑎𝑖 can be inserted into one of the first 𝑖 locations with equal
probability
▪ The first 𝑖 elements of a random permutation is a
random permutation of 𝑖 elements
▪ The rank of the last element in a random permutation is
one of 1, … , 𝑖 with equal probability
1 1 1 𝑖+1
▪ 𝐸 𝑋𝑖 = ⋅ 1 + ⋅ 2 + ⋯ + ⋅ 𝑖 =
𝑖 𝑖 𝑖 2
𝑖+1 𝑛2 +3𝑛−4
▪ 𝐸 𝑋 = σ𝑛𝑖=2 = = Θ(𝑛2 )
2 4
24
 Geometric Distribution
▪ Experiment: Flip a fair coin until it turns up heads.
Let random variable 𝑋 = the number of flips.
1/2

1/4
1/8
1/16
…
1 2 3 4 5

▪ General case: each coin turns up heads with prob. 𝑝

▪ Definition
A random variable X has geometric distribution with
parameter 𝑝 ≤ 1 if 𝑝 𝑋 = 𝑘 = 1 − 𝑝 𝑘−1 𝑝, 𝑘 = 1, 2, 3, … .
▪ Theorem: 𝐸 𝑋 = σ 𝑝 1 − 𝑝 𝑘−1 𝑘 = ⋯ =
1
𝑘=1 𝑝
25
 Example: Coupon Collector
▪ Question
Each box of cereal contains a coupon. There are 𝑛
different types of coupons. Assuming a box contains
each type of coupon equally likely, how many boxes
do you need to open to have at least one coupon of
each type?

26
 Coupon Collector: Solution
▪ Let 𝑋𝑖 = number of boxes you need to open between
having 𝑖 and 𝑖 + 1 distinct coupons (geometric
distribution)
▪ Let 𝑋 = number of boxes in total = 𝑋0 + 𝑋1 + ⋯ + 𝑋𝑛−1 .
𝑛−1 𝑛−1 𝑛
𝑛 1
𝐸 𝑋 = ෍ 𝐸 𝑋𝑖 = ෍ = 𝑛 ෍ = Θ(𝑛 log 𝑛)
𝑛−𝑖 𝑖
𝑖=0 𝑖=0 𝑖=1

geometric distribution with 𝑝 = (𝑛 − 𝑖)/𝑛

27
 Independent Random Variables
▪ Definition
The random variables X and Y on a sample space S are
independent if
𝑝 𝑋 = 𝑟1 𝑎𝑛𝑑 𝑌 = 𝑟2 = 𝑝 𝑋 = 𝑟1 ∙ 𝑝 𝑌 = 𝑟2
for all 𝑟1 , 𝑟2
▪ Theorem
If X and Y are independent variables on a sample
space S, then E(XY) = E(X)E(Y).
▪ Note
Linearity of expectation holds no matter the random
variables are independent or not.

28
 Example
▪ Let 𝑋 and 𝑌 be random variables that count the
number of heads and the number of tails when a fair
coin is flipped twice.
▪ Show that 𝑋 and 𝑌 are not independent.
▪ 𝑝 𝑋 = 2 𝑎𝑛𝑑 𝑌 = 2 = 0
▪ 𝑝 𝑋 = 2 = 1/4, 𝑝 𝑌 = 2 = 1/4
▪ Check
1 1
▪ 𝐸 𝑋𝑌 = 1 ⋅ =
2 2
▪ 𝐸 𝑋 =𝐸 𝑌 =1
▪ 𝐸 𝑋𝑌 ≠ 𝐸 𝑋 𝐸(𝑌)
▪ Check 𝐸 𝑋 + 𝑌 = 2 = 𝐸 𝑋 + 𝐸(𝑌)
29
 Proof
▪ From the definition of expected value and because X
and Y are independent random variables, it follows
that

30
 Variance and Standard Deviation
▪ Definition
Let 𝑋 be a random variable on the sample space 𝑆. The
variance of 𝑋, denoted by 𝑉(𝑋) is
2 2
𝑉 𝑋 =෍ 𝑋 𝑠 −𝐸 𝑋 𝑝(𝑠) = 𝐸 𝑋−𝐸 𝑋
𝑠∈𝑆
▪ Definition
The standard deviation of 𝑋, denoted by 𝜎(𝑋), is 𝑉(𝑋)
▪ Example
Bernoulli trial: 𝑋 = 1 with probability 𝑝, 0 otherwise
𝐸 𝑋 =𝑝
𝑉 𝑋 = 1 − 𝑝 2 𝑝 + 0 − 𝑝 2 ⋅ (1 − 𝑝) = (1 − 𝑝)𝑝

31
 Variance
▪ Theorem
𝑉 𝑋 = 𝐸 𝑋2 − 𝐸 𝑋 2

▪ Proof

▪ Corollary
𝑉 𝑎𝑋 = 𝑎2 𝑉(𝑋), for any real number 𝑎 ≥ 0.
32
 Example
▪ Question
What is the variance of a random variable 𝑋, where 𝑋 is
the number that comes up when a fair dice is rolled?
▪ Solution
1+2+3+4+5+6 7
▪ 𝐸 𝑋 = =
6 2
▪ Using the first definition:
2 2
1 − 3.5 + 2 − 3.5 + (3 − 3.5)2 +(4 − 3.5)2 +(5 − 3.5)2 +(6 − 3.5)2 35
𝑉 𝑋 = =
6 12
▪ Using the second definition:
1 2 + 22 + 32 + 42 + 52 + 62 91
2
𝐸 𝑋 = =
6 6
2
2 2
91 7 35
𝑉 𝑋 =𝐸 𝑋 −𝐸 𝑋 = − =
6 2 12
33
 Bienaymé’s Formula
▪ Theorem
If 𝑋 and 𝑌 are two independent random variables on a
sample space 𝑆, then
V(𝑋 + 𝑌) = 𝑉(𝑋) + 𝑉(𝑌)

Furthermore, if 𝑋𝑖 , 𝑖 = 1, 2, … , 𝑛, are pairwise

independent random variables on 𝑆, then
𝑉 𝑋1 + ⋯ + 𝑋𝑛 = 𝑉 𝑋1 + ⋯ + 𝑉 𝑋𝑛

34
 Proof of Bienaymé’s Formula

▪ The proof of the case with 𝑛 pairwise independent

random variables can be constructed by generalizing
the proof of the case for two random variables.

35
 Examples
▪ Question
𝑋 = the sum of numbers of two dice
What’s 𝑉 𝑋 ?
▪ Solution
Write 𝑋 = 𝑋1 + 𝑋2 , where 𝑋1 is the number on the first dice,
𝑋2 is the number on the second dice
35
We already know 𝑉 𝑋1 = 𝑉 𝑋2 =
12
35 35 35
So 𝑉 𝑋 = + = .
12 12 6
▪ Question
Given that 𝑋 follows the binomial distribution. What’s 𝑉 𝑋 ?
▪ Solution
Write 𝑋 = 𝑋1 + ⋯ + 𝑋𝑛 , where 𝑋𝑖 = 1 with prob. 𝑝
We already know 𝑉 𝑋𝑖 = 𝑝(1 − 𝑝)
So 𝑉 𝑋 = 𝑛𝑝(1 − 𝑝).
36
 Example
▪ Suppose we take a measurement by repeating the
same experiment many times. Each trial returns a
random measurement that is correct in expectation,
but with some deviation. More precisely, let 𝑋𝑖 be the
measurement from the 𝑖-th experiments we have
𝐸 𝑋𝑖 = 𝜇, 𝑉 𝑋𝑖 = 𝜎 2
If we repeat the experiments 𝑛 times independently,
and report the average 𝑌 = (𝑋1 + ⋯ + 𝑋𝑛 )/𝑛. What is
𝐸 𝑌 and 𝑉 𝑌 ?
▪ Solution
𝐸 𝑋1 + ⋯ + 𝐸 𝑋𝑛
𝐸 𝑌 = =𝜇
𝑛
𝑉 𝑋1 + ⋯ + 𝑉 𝑋𝑛 𝜎2
𝑉 𝑌 = 2
=
𝑛 𝑛
37