Bilkent University Spring 2022
MATH 255 - Probability and Statistics
Final Exam Solutions
Problem 1) Let
( (
θe−θx if x ≥ 0 αe−αθ if θ ≥ 0
fX|Θ (x|θ) = and fΘ (θ) =
0 if x < 0 0 if θ < 0
Find the MAP and LMS estimates of θ for a single observation X = x.
R∞ R∞
Hint: For exponential random variables, we have 0 λe−λx dx = 1 and 0 x2 λe−λx dx = 2
λ2
.
We can first find the posterior distribution (2pt):
fX|Θ (x|θ)fΘ (θ)
fΘ|X (θ|x) =
fX (x)
αθe−(α+x)θ
= R∞ −(α+x)θ dθ
0 αθe
αθe−(α+x)θ
= α
(α+x)2
= (α + x)2 θe−(α+x)θ .
Then, the MAP estimate is the peak of the posterior (1pt):
θbMAP (x) = arg max{log fX|Θ (x|θ) + log fΘ (θ)}
θ
= arg max{−θx + log θ − αθ + log α}.
θ
1
Taking the derivative and setting it to zero yields that −x + θ − α = 0. This implies that (1pt)
1
θbMAP (x) = .
α+x
On the other hand, the LMS estimate is the conditional expectation of the posterior (1pt):
θbLMS (x) = EΘ|X [Θ|X = x]
Z ∞
= θfΘ|X (θ|x)dθ
Z0 ∞
= θ(α + x)2 θe−(α+x)θ dθ
0
Z ∞
= (α + x) θ2 · (α + x)e−(α+x)θ dθ
|0 {z }
2nd moment of exponential distribution
2
= (α + x) · .
(α + x)2
1 09-25-2025 13:36:16 GMT -05:00
This study source was downloaded by 100000899606396 from CourseHero.com on
https://www.coursehero.com/file/184862012/final-solutions-Spring-2022pdf/
, Therefore, we have (1pt)
2
θbLMS (x) = .
α+x
Problem 2) Erdös-Rényi graph is one of the simplest models for social networks. In this
graph, vertices and edges, respectively, correspond to users and the (undirected) connectivity
between them. Specifically, each edge has a fixed probability of being present or absent,
independently of the other edges. We can represent a graph through an adjacency matrix X
with binary entries. The ith row and the jth column entry, denoted by Xij , indicates an edge
connecting nodes i and j. The following figure illustrates an example of Erdös-Rényi graph
and the associated adjacency matrix.
User 1
User 1 User 2 User 3 User 4
User 1 0 1 1 0
User 2
User 2 1 0 1 0
User 4
User 3 1 1 0 1
User 4 0 0 1 0
User 3
Since the presence and absence of an edge is binary and random, we can model Xij for
each (i, j) and i 6= j as a Bernoulli random variable
Xij ∼ Ber(p),
with a success probability p. In other words, for i 6= j, Xij = 1 with probability p and Xij = 0
with probability 1 − p. Furthermore, Xii = 0 for all i.
Suppose that we are given a realization of the adjacency matrix for an Erdös-Rényi graph
with n vertices.
Hint: Each edge can be present or absent, independently of the other edges, but Xij = Xji for all i, j.
The problem is not much different from an i.i.d. sequence of Bernoulli random variables!
(a) (4pt) Find the log-likelihood function of p.
Notice that Xij = Xji for all i, j and Xii = 0 for all i. Hence, we can focus on the triangle
Pn−1 Pn
∆ := {(i, j) : i ∈ [1, n − 1] and j ∈ [i + 1, n]}. Given the realization, let cx := i=1 j=i+1 xi,j
denote the number of successes in the indices in ∆ since xij = 1 if it succeeds. Correspondingly,
Pn−1 Pn
dx := i=1 j=i+1 (1 − xi,j ) denotes the number of failures in the indices in ∆ since xij = 0, and
therefore, (1 − xij ) = 1 if it fails. Then, the likelihood function of p is given by (2pt)
fX (x; p) = pcx (1 − p)dx .
2 09-25-2025 13:36:16 GMT -05:00
This study source was downloaded by 100000899606396 from CourseHero.com on
https://www.coursehero.com/file/184862012/final-solutions-Spring-2022pdf/
MATH 255 - Probability and Statistics
Final Exam Solutions
Problem 1) Let
( (
θe−θx if x ≥ 0 αe−αθ if θ ≥ 0
fX|Θ (x|θ) = and fΘ (θ) =
0 if x < 0 0 if θ < 0
Find the MAP and LMS estimates of θ for a single observation X = x.
R∞ R∞
Hint: For exponential random variables, we have 0 λe−λx dx = 1 and 0 x2 λe−λx dx = 2
λ2
.
We can first find the posterior distribution (2pt):
fX|Θ (x|θ)fΘ (θ)
fΘ|X (θ|x) =
fX (x)
αθe−(α+x)θ
= R∞ −(α+x)θ dθ
0 αθe
αθe−(α+x)θ
= α
(α+x)2
= (α + x)2 θe−(α+x)θ .
Then, the MAP estimate is the peak of the posterior (1pt):
θbMAP (x) = arg max{log fX|Θ (x|θ) + log fΘ (θ)}
θ
= arg max{−θx + log θ − αθ + log α}.
θ
1
Taking the derivative and setting it to zero yields that −x + θ − α = 0. This implies that (1pt)
1
θbMAP (x) = .
α+x
On the other hand, the LMS estimate is the conditional expectation of the posterior (1pt):
θbLMS (x) = EΘ|X [Θ|X = x]
Z ∞
= θfΘ|X (θ|x)dθ
Z0 ∞
= θ(α + x)2 θe−(α+x)θ dθ
0
Z ∞
= (α + x) θ2 · (α + x)e−(α+x)θ dθ
|0 {z }
2nd moment of exponential distribution
2
= (α + x) · .
(α + x)2
1 09-25-2025 13:36:16 GMT -05:00
This study source was downloaded by 100000899606396 from CourseHero.com on
https://www.coursehero.com/file/184862012/final-solutions-Spring-2022pdf/
, Therefore, we have (1pt)
2
θbLMS (x) = .
α+x
Problem 2) Erdös-Rényi graph is one of the simplest models for social networks. In this
graph, vertices and edges, respectively, correspond to users and the (undirected) connectivity
between them. Specifically, each edge has a fixed probability of being present or absent,
independently of the other edges. We can represent a graph through an adjacency matrix X
with binary entries. The ith row and the jth column entry, denoted by Xij , indicates an edge
connecting nodes i and j. The following figure illustrates an example of Erdös-Rényi graph
and the associated adjacency matrix.
User 1
User 1 User 2 User 3 User 4
User 1 0 1 1 0
User 2
User 2 1 0 1 0
User 4
User 3 1 1 0 1
User 4 0 0 1 0
User 3
Since the presence and absence of an edge is binary and random, we can model Xij for
each (i, j) and i 6= j as a Bernoulli random variable
Xij ∼ Ber(p),
with a success probability p. In other words, for i 6= j, Xij = 1 with probability p and Xij = 0
with probability 1 − p. Furthermore, Xii = 0 for all i.
Suppose that we are given a realization of the adjacency matrix for an Erdös-Rényi graph
with n vertices.
Hint: Each edge can be present or absent, independently of the other edges, but Xij = Xji for all i, j.
The problem is not much different from an i.i.d. sequence of Bernoulli random variables!
(a) (4pt) Find the log-likelihood function of p.
Notice that Xij = Xji for all i, j and Xii = 0 for all i. Hence, we can focus on the triangle
Pn−1 Pn
∆ := {(i, j) : i ∈ [1, n − 1] and j ∈ [i + 1, n]}. Given the realization, let cx := i=1 j=i+1 xi,j
denote the number of successes in the indices in ∆ since xij = 1 if it succeeds. Correspondingly,
Pn−1 Pn
dx := i=1 j=i+1 (1 − xi,j ) denotes the number of failures in the indices in ∆ since xij = 0, and
therefore, (1 − xij ) = 1 if it fails. Then, the likelihood function of p is given by (2pt)
fX (x; p) = pcx (1 − p)dx .
2 09-25-2025 13:36:16 GMT -05:00
This study source was downloaded by 100000899606396 from CourseHero.com on
https://www.coursehero.com/file/184862012/final-solutions-Spring-2022pdf/
