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

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