Writing $s_i=2x_i-1$, the edge term rewards neighboring computers having the same infection state, as in a ferromagnetic <Ising model>, while $-\frac1{10}\sum_i x_i$ expresses a mild prior preference for the rarer uninfected state. Thus the prior encodes local transmission over the network without assuming independent infections.

The observation likelihood is
$$
L(x)=\prod_{i\in V_2}\frac14\mathbf1_{\{x_i=1\}}
\prod_{i\in V_1\setminus V_2}\left(\frac34\right)^{x_i}.
$$
Consequently the <posterior distribution> is
$$
p(x_V\mid V_2)
\propto
\exp\left[
\sum_{\{i,j\}\in E}(2x_i-1)(2x_j-1)
-\frac1{10}\sum_i x_i
\right]L(x).
$$
This remains a binary pairwise <Markov random field> on a tree. To find its <maximum a posteriori estimate>, run <max-product belief propagation>: send a two-entry message in each direction along every edge, then backtrack from the maximizing root state. Each message examines four state pairs, and the maximum degree is bounded, so the total cost is
$$
\boxed{O(|V|).}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 216 / 1 / a / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-216/1/a/solution