= Solution
Integrating the acceptance <probability> over the joint-prior proposal gives
$$
\boxed{\alpha=E_g[a_k(\theta,T)]=m_k=P_{\mathrm{prior}}(S=k).}
$$
The <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)]$. Then
$$
m_k=\int_0^\infty\pi(\theta)\ell_k(\theta)\,d\theta,\qquad \sum_{k\ge0}\ell_k(\theta)z^k=\prod_{i=1}^{n-1}\frac{i}{i+\theta(1-z)}.
$$
For the last identity, $W=L/2$ is the sum of independent exponential variables with rates $1,\ldots,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 gives
$$
\ell_k(\theta)=(n-1)\theta^k\sum_{r=0}^{n-2}\frac{(-1)^r\binom{n-2}{r}}{(\theta+r+1)^{k+1}}.
$$
Use $\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$:
$$
\frac{d}{d\lambda}\log\!\left(\frac{e^{-\lambda}\lambda^k}{k!}\right)=-1+\frac{k}{\lambda}.
$$
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. Thus
$$
\boxed{\alpha_{\mathrm{improved}}=\frac{m_k}{M_k},\qquad M_k=\frac{e^{-k}k^k}{k!}\ (k>0),\quad M_0=1.}
$$
For $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.
Back to article page
