Description
In this exercise, we consider a variation of the card game seen in class. We consider a vector ⃗s ∈ {−1, +1}
n
where the elements si are i.i.d sampled uniformly on {−1, +1}. We now consider a graph G = (V, E) where
the nodes V are V = {1, …, n} and for 1 ⩽ i < j ⩽ n, the edge (i, j) is in E with probability pe > 0.
We now define the observations matrix matrix Y such that Yi,i = 0 and for i ̸= j, Yi,j = 0 if (i, j) ̸∈ E.
For (i, j) ∈ E, we take
(
Yi,j = sisj with probability 1 − ρ
Yi,j = −sisj with probability ρ
(1)
For some 1 ⩾ ρ ⩾ 0. The edges E will be stored as a n × n matrix such that Eij = 1 if and only if the
edge (i, j) is present in the graph. Note that for all i, (i, i) ̸∈ E. The goal of this exercise is to compare the
performance of the Bayes-optimal estimator and the estimator returned by PCA.
Question 1 (1 pt) Implement the function generate data that takes as argument the parameters n, ρ
and pe and returns an instance ⃗s, Y, E of the problem.
Question 2 (1 pt) Implement the function run pca that returns the eigenvector ⃗sP CA of Y that corresponds to its highest-eigenvalue.
Question 3 (2 pt) Explicit the posterior distribution
P(⃗s|Y, ρ) ∝ P(⃗s)P(Y |⃗s, ρ) (2)
and show that it can be written
P(⃗s|Y, ρ) ∝
Y
i
1(si = ±1) (1 − ρ)
P
i<j 1(yi,j=sisj )
ρ
P
i<j 1(yi,j=−sisj )
(3)
Question 4 (4 pt) We consider the following Metropolis-Hastings scheme that runs for T iterations:
1. At t = 1, sample ⃗s1
from P(⃗s).
2. At each iteration t, pick an index i uniformly in [1, n]
3. Define ˜⃗s = (s
t
1
, …, st
i−1
, −s
t
i
, st
i+1, sn) and compute the ratio η =
P (⃗s˜|Y )
P (⃗st|Y )
. With probability min(1, η),
define ⃗st+1 = ˜⃗s, otherwise define ⃗st+1 = ⃗st
1
Implement the function log ratio posterior that returns log
P (⃗s˜|Y )
P (⃗s|Y )
given ⃗s and with ˜⃗s defined as
above. Use it to implement the function run mcmc that runs Metropolis-Hastings for T iterations and returns
a list (⃗st
)
T
t=1.
Question 5 (3 pt) Once we have the list of iterations (⃗st
)
T
t=1 we can build an approximation ⃗sBO of the
Bayes-optimal estimator. Recall that the Bayes-optimal estimator that maximizes the overlap
Q(
ˆ⃗s) = |
1
n
⃗s ·
ˆ⃗s| (4)
is equal to
⃗sBO
i = arg max
s=±1
P(si = s|Y, ρ) (5)
Take n ⩾ 500, pe = 4/n. For ρ ∈ [0.1, 0.4], run Metropolis-Hastings and plot Q(⃗st
) as a function of
time. Use these plots to estimate the thermalization time Ttherm of Metropolis-Hastings as a function of ρ.
Additionally, plot Q(⃗sBO) as a function of ρ ∈ [0.1, 0.4].
Relate the behaviour of Q(⃗sBO) with the behaviour of Ttherm. In particular, do you notice a phase
transition for Q(⃗sBO) at some ρ ?
Question 6 (3 pt) Take n ⩾ 500, ρ = 0.25. For pe ∈ [
2/n,
6/n], compute and plot the overlaps Q(⃗sBO)
and Q(⃗sP CA) as a function of pe. Compare the performance of the two estimators.
