Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 45 / 3 / v / Solution

Integrating the acceptance probability over the joint-prior proposal givesThe mean number of independent proposal trials per acceptance is $1/m_k$, by the geometric distribution. To make the acceptance rate explicit for an arbitrary specified prior, define the segregating-site likelihood under the neutral coalescent by ${\ell }_k(\theta )=E_T[a_k(\theta ,T)]$. ThenFor the last identity, $W=L/2$ is the sum of independent exponential variables with rates $1,\dots ,n-1$; combine their Laplace transforms with the conditional Poisson probability generating function. If an explicit mass is wanted, $W$ also has density $(n-1)e^{-w}(1-e^{-w}{)}^{n-2}$: it is the maximum of $n-1$ independent unit exponential variables, whose successive spacings have exactly these exponential rates. Expanding $(1-e^{-w}{)}^{n-2}$ and integrating the Poisson mass givesUse ${\theta }^0=1$ for $k=0$. The positive integral or generating-function expression may be numerically preferable to this alternating sum.

A sharper rejection envelope improves the algorithm without changing its proposal. For $k>0$, maximize the Poisson mass over $\lambda =\theta L/2$:It increases until $\lambda =k$ and decreases afterwards, so its maximum is $M_k=e^{-k}{k}^k/k!$. For $k=0$, the maximum is $M_0=1$. Replace the acceptance rule by $U\le a_k(\theta ,T)/M_k$. This is bounded by one, and its accepted density is unchanged because the factor $1/M_k$ cancels on normalization. ThusFor $k>0$ it is strictly more efficient, with improvement factor $1/M_k\sim \sqrt{2\pi k}$ by Stirling's formula. For $k=0$ this envelope improvement gives no increase. Evaluating the Poisson mass and using a uniform draw also avoids generating a Poisson count only to discard it. A proposal concentrated near the posterior can improve efficiency further, but then its density and a valid rejection bound must be included.