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$, set
$$
I_m=\mathbf1\left\{\sum_{i\in V}X_i^{(m)}>2|V_2|\right\},
\qquad
\widehat q=\frac1N\sum_{m=1}^NI_m.
$$
Then $\widehat q$ is unbiased and
$$
\operatorname{Var}(\widehat q)=\frac{q(1-q)}N.
$$
Taking $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
$$
\boxed{O(|V|).}
$$


Solution

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

 Solution

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