= Solution
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|).}
$$
Back to article page
