UC Berkeley EECS 126 Probability and Random Processes | Homework 12 & 13 + Discussions 7–13 Complete Solutions | All 9 Assignments Merged | Step-by-Step Worked Answers | Electrical Engineering & Computer Science Study Guide

UC Berkeley
Department of Electrical Engineering and Computer Sciences
EECS 126: Probability and Random Processes
Homework 12
Spring 2025
1. Maximum Likelihood Estimation for the Binary Symmetric Channel
You are testing a digital link that corresponds to a BSC with some error probability ε ∈ [0, 0.5].
a. Suppose that you observe an input bit X and an output bit Y . Calculate the MLE of ε,
which is the value of ε ∈ [0, 0.5] maximizing the probability you observe the given data.
Here, since the observation is (X, Y ), we want to find

εMLE = argmax Pε (X = x, Y = y).
ε∈[0,0.5]


b. You are now told that the inputs X1 , . . . , Xn are i.i.d. Bernoulli(0.6) bits. Suppose that
you observe n outputs Y1 , . . . , Yn . Calculate the MLE of ϵ.

Solution:
a. Let Pε denote the probability distribution of X and Y when the error probability of the
BSC is ε. For (x, y) ∈ {0, 1}2 ,
 
εMLE = argmax Pε (X = x, Y = y) = argmax ε1{x̸=y} (1 − ε)1{x=y} .
ε∈[0,0.5] ε∈[0,0.5]

If x ̸= y, then εMLE = 0.5 maximizes the likelihood; otherwise, εMLE = 0.
b. Note that every use of the channel is independent. Given n outputs, εMLE maximizes
n
Y
Pε (Y1 = y1 , . . . , Yn = yn ) = Pε (Yi = yi )
i=1
Yn
= [(0.6(1 − ε) + 0.4ε) 1yi =1 + (0.4(1 − ε) + 0.6ε) 1yi =0 ]
i=1
Yn
= (0.6 − 0.2ε)yi (0.4 + 0.2ε)1−yi
i=1
Pn Pn
yi
= (0.6 − 0.2ε) (0.4 + 0.2ε)n− i=1 yi .
i=1



We find that the likelihood only depends on t = ni=1 yi . We can then find the maximizer
P
as εMLE = 3 − 5t
n from differentiating the log-likelihood:

−0.2t 0.2(n − t) t(ε + 2) + (n − t)(ε − 3)
+ = = 0.
0.6 − 0.2ε 0.4 + 0.2ε (ε − 3)(ε + 2)

If εMLE falls outside of the interval [0, 0.5], then we clip it to 0 or 0.5, whichever endpoint
is closer to the maximizer.


1

,2. Poisson Process MAP
Customers arrive to a store according to a Poisson process with rate 1. The store manager
learns of a rumor that one of the employees is sending every other customer to the rival store,
so that deterministically, every odd-numbered customer 1, 3, 5, . . . is sent away.
Let X = 1 be the hypothesis that the rumor is true and X = 0 the rumor is false, assuming
that both hypotheses are equally likely. Suppose a customer arrives to the store at time 0.
After that, the manager observes T1 , . . . , Tn , where Ti is the time of the ith subsequent sale,
i = 1, . . . , n. Derive the MAP rule to determine whether the rumor was true or not.

Solution: Note that both hypotheses are a priori equally likely, so the MAP rule is equivalent
to the MLE rule. Also note that the interarrival times τi are independent whether conditioned
on X = 1 or on X = 0. The density of an interarrival interval given X = 1 is Erlang of order
2, so for 0 ≤ t1 < · · · < tn ,
n
Y n
Y
fT1 ,...,Tn |X (t1 , . . . , tn | 1) = (ti − ti−1 )e−(ti −ti−1 ) = e−tn (ti − ti−1 ).
i=1 i=1

The density of an interarrival interval given X = 0 is Exponential, so

fT1 ,...,Tn |X (t1 , . . . , tn | 0) = e−tn .

Taking the logarithm of both expressions, we see that the MAP is to declare X = 1 whenever
n
X
ln(Ti − Ti−1 ) ≥ 0.
i=1




2

,3. Laplace Prior and ℓ1 -Regularization
Suppose you draw n i.i.d. data points (x1 , y1 ), . . . , (xn , yn ), where the true relationship is given
by Y = W X + ε for ε ∼ N (0, σ 2 ). In other words, Y has a linear dependence on X with
additive Gaussian noise. Further suppose that W has a Laplace prior distribution
1 −|w|/β
fW (w) = e .
2β

Show that finding the MAP estimate of W given the data points {(xi , yi )}ni=1 is equivalent to
minimizing the cost function
n
X
J(w) = (yi − wxi )2 + λ |w| .
i=1

(You should determine what λ is.) This is interpreted as a one-dimensional ℓ1 -regularized
least-squares criterion, also known as LASSO.

Solution: The likelihood of W is

L(w | (x1 , y1 ), . . . , (xn , yn )) ∝ L((x1 , y1 ), . . . , (xn , yn ) | W = w) · fW (w)
n
Y
= fW (w) L((xi , yi ) | W = w)
i=1

as the data points are conditionally independent given W ;
n
1 −|w|/β Y 1 2 2
= e √ e−(yi −wxi ) /(2σ )
2β 2πσ i=1

as the likelihood of (xi , yi ) given W = w is the density of εi ∼ N (0, σ 2 ) evaluated at yi − wxi ;
n
2 /(2σ 2 )
Y
∝ e−|w|/β e−(yi −wxi ) ,
i=1

discarding constant factors that do not depend on the data points or w. We wish to maximize
this expression w.r.t. w, but we find it more convenient to work with the log-likelihood
n
1 X 1
ℓ(w | (x1 , y1 ), . . . , (xn , yn )) = − 2
(yi − wxi )2 − |w| .
2σ β
i=1

We wish to maximize the log-likelihood, which is equivalent to minimizing the cost function
n
X
J(w) = (yi − wxi )2 + λ |w|
i=1

with λ = 2σ 2 /β.




3

, 4. Bayesian Estimation of Exponential Distribution
We have seen the MLE (non-Bayesian perspective) and MAP estimation (Bayesian perspective).
In this problem, we will introduce the fully Bayesian approach to statistical estimation.
Suppose that X is Exponential with unknown rate Λ. As a Bayesian practitioner, you have a
prior belief that the random variable Λ is equally likely to be λ1 or λ2 .
Now, you collect one sample X1 from X.
a. Find the posterior distribution P(Λ = λ1 | X1 = x1 ).
b. If we were using the MLE or MAP rule, we would choose a single value λ for Λ, sometimes
called a point estimate. This amounts to saying X has Exponential distribution with rate
λ. In the Bayesian approach, we will instead keep the full information of the posterior
distribution of Λ, and we compute the distribution of X as
X
fX (x) = fX|Λ (x | λ) · P(Λ = λ | X1 = x1 ).
λ∈{λ1 ,λ2 }

Note that we do not necessarily have an Exponential distribution for X anymore. Compute
fX (x) in closed form.
c. From the previous part, you may have guessed that the fully Bayesian approach is often
computationally intractable, which is one of the main reasons why point estimates are
common in practice. Supposing that λ1 > λ2 , compute the MAP estimate for Λ, and
calculate fX (x) again using the MAP rule.

Solution:
a. The prior distribution is P(Λ = λ1 ) = P(Λ = λ2 ) = 12 , and the likelihood of the data is

fX1 |Λ (x1 | λ) = λe−λx1 ,

so by Bayes’ rule, the posterior distribution is
1 −λ1 x1
2 λ1 e λ1 e−λ1 x1
P(Λ = λ1 | X1 = x1 ) = = .
1
2 λ1 e
−λ1 x1 + 1 λ e−λ2 x1
2 2
λ1 e−λ1 x1 + λ2 e−λ2 x1

b. By the previous part, we have
λ21 e−λ1 (x+x1 ) + λ22 e−λ2 (x+x1 )
fX (x) = .
λ1 e−λ1 x1 + λ2 e−λ2 x1

c. The MAP rule says to choose the value of λ that maximizes the posterior probability
P(Λ = λ | X1 = x1 ), i.e. choose λ1 if λ1 e−λ1 x1 > λ2 e−λ2 x1 , in which case X is Exponential
with rate λ1 . When λ1 > λ2 ,
   
ln(λ1 /λ2 ) ln(λ1 /λ2 )
MAP(Λ | X1 ) = λ1 1 X1 < + λ2 1 X1 > .
λ1 − λ2 λ1 − λ2

λ1 e−λ1 x if X1 < ln(λ1 /λ2 )
λ1 −λ2
fX (x) =
λ e−λ2 x if X > ln(λ1 /λ2 ) .
2 1 λ1 −λ2



4