Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 216 (Bayesian Modelling and Computation)

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

Given the current state $x=(x_1,\dots ,x_d)$, a Random-scan Gibbs sampler chooses $I$ uniformly from $\{1,\dots ,d\}$, leaves $x_{-I}$ unchanged, and samples the new coordinate from the complete conditional distributionIts transition kernel isand it leaves $\pi$ invariant.

Because $f$ is a continuous bijection $\mathbb{R}\to \mathbb{R}$, it is a Borel isomorphism. Conditional on $X_{-i}=x_{-i}$, the $i$th coordinate of $F(X)$ has the pushforward of $\pi (d{x}_i\mid x_{-i})$ under $f$. Therefore applying one $K$-update and then $F$ has exactly the same law as applying one $Q$-update to $F(x)$, using the same random coordinate.

Formally, for every Borel set $A$,Composition preserves this conjugacy, so induction on $t$ givesHence

Total variation is invariant under a measurable bijection with measurable inverse. Using part (b),Every $z\in {\mathbb{R}}^d$ equals $F(x)$ for a unique $x$, so

PutThe normalizing identityshows thatis a probability measure. If $x$ and $y$ differ only in coordinate $i$, the transition density from $x$ to $y$ is $p(x,i)\mu (y_i\mid x_{-i})/S(x)$. Thereforewhich is symmetric in $x_i,y_i$. Thus detailed balance holds and the Tempered Gibbs sampler is $\pi$-reversible.

The summand intended in the question is $d,h(X(t))/S(X(t))$. Under stationarity,Moreover $S(x)\ge d{c}_1$, so the summand is bounded by $1/c_1$. A stationary geometrically ergodic Markov chain satisfies the Markov-chain law of large numbers; hencealmost surely, and therefore in probability. In particular,

Let $\theta =(\beta ,\pi )$ and regard $X_U$ as the latent variable. At iteration $t$, the E-step formsThe M-step updatesThis is the expectation-maximization algorithm for the posterior objective: including $\log p(\theta )$ in the complete-data log density makes the maximizer a maximum a posteriori estimate rather than a maximum-likelihood estimate.

Let $U_i=\{j:(i,j)\notin O\}$ and let $x_{i,O}$ denote the observed entries in row $i$. Conditional on the parameters, different rows of the missing design are independent, while the missing entries within one row are coupled by its Gaussian response. For $z\in \{0,1{\}}^{U_i}$,Normalizing this expression over the $2^{|U_i|}$ configurations and multiplying over rows gives the full conditional distribution of $X_U$.

Ignoring constants, the complete-data log posterior isTake conditional expectations under $({\beta }^{(t)},{\pi }^{(t)})$. DefineCompleting the square givesFor $v\ne 0$,so $A$ is positive definite. Exact rowwise expectations require summing over $2^{|U_i|}$ states. Thus the cost is exponential in the largest number of missing covariates in one row, more precisely ${\sum }_i{2}^{|U_i|}$ times a polynomial factor for accumulating first and second moments.

Positive definiteness makes the quadratic term uniquely maximal atFor each $j$, maximize the concave function $r_j\log {\pi }_j+q_j\log (1-{\pi }_j)$. Its interior critical point isThe same formula gives the appropriate boundary value when $r_j=0$ or $q_j=0$.

Introduce $Z_{ij}\in \{0,1\}$, where $Z_{ij}=1$ means that the observation came from the structural-zero component. Conditional on the parameters,Given $Z$, the nonstructural observations are independent Poisson variables. Using shape-rate parameterization and the stated unit-rate priors, the remaining Gibbs updates areAlternating these four standard-distribution updates defines the requested Gibbs sampler for the Zero-inflated Poisson distribution posterior.

Letbe the Hamiltonian. The Hamiltonian Monte Carlo proposal is accepted with the Metropolis–Hastings acceptance probabilityThe leapfrog map is volume preserving and reversible after momentum reversal, so no proposal-density Jacobian appears.

For $U(x)=x^{T}x/2$, one leapfrog step isTherefore $L$ steps givewhich is a linear transformation.

For fixed $L$, expansion of the matrix in part (b) givesHence its largest eigenvalue is $1+O({\epsilon }^3)$. With $z=(x(0),p(0))$ and $z^{\prime }=M_{\epsilon }^{L}z$,For each fixed starting state, or uniformly on any bounded set of starting states, this impliesUsing $e^{-u}\ge 1-u$ for $u\ge 0$ in the acceptance formula givesfor sufficiently small $\epsilon$. The constant necessarily depends on a bound for $\Vert z\Vert$: a uniform pointwise constant over all of ${\mathbb{R}}^{2d}$ would be impossible because the energy error is quadratic in the starting state.