The posterior mean of the number infected is
$$
\mathbb E\left[\sum_{i\in V}X_i\,middle|\,V_2\right]
=\sum_{i\in V}\mathbb P(X_i=1\mid V_2).
$$
Run <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
$$
\boxed{O(|V|).}
$$

Solution

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

 Solution

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