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

Writing $s_i=2x_i-1$, the edge term rewards neighboring computers having the same infection state, as in a ferromagnetic Ising model, while $-\frac{1}{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 isConsequently the posterior distribution isThis 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

The posterior mean of the number infected isRun sum-product belief propagation on the tree to compute every exact one-vertex posterior marginal. Summing their probabilities of state one gives the requested mean. Messages have fixed size and every directed edge is processed once, so the exact computation costs

After the sum-product messages have been computed, draw exact independent posterior configurations by sampling a root from its marginal and then sampling each child from its conditional distribution given its parent. For sample $m$, setThen $\hat{q}$ is unbiased andTaking $N=1000$ attains the required bound. Message computation costs $O(|V|)$ and each exact sample costs $O(|V|)$, so with the prescribed fixed number of samples the overall cost is