Past exam of the simulation and statistical programming course of the University of Oxford / 2021 / 2 / a / iii

Write $t=1-\rho \in (0,1)$. The target Poisson distribution and proposal geometric distribution have probability mass functions $p_k=e^{-\lambda }{\lambda }^k/k!$ and $q_k=(1-t)t^k$. Their ratio isThe successive ratio $R_{k+1}/R_k=\lambda /[t(k+1)]$ shows that a maximizing integer is $m=\lfloor \lambda /t\rfloor$, with a tie at $m-1$ when $\lambda /t$ is an integer. Thus the tight envelope isFor any fixed $t$, draw $Y\sim \mathrm{Geom}(1-t)$ using (ii)'s inversion formula with this new parameter, and draw an independent $U$ from the uniform distribution on $(0,1)$. Accept whenotherwise restart. The acceptance probability is $1/M(t)$ and the expected number of proposals is $M(t)$.

To minimize that expected count, set $K=\lceil \lambda \rceil$. The exact answer isHere is a proof that includes the changes of maximizing integer. Each $\log R_k(t)$ is a convex function of $t$, since its second derivative is $(1-t{)}^{-2}+k/t^2>0$. Their pointwise maximum $\log M(t)$ is also a convex function. When $m$ is fixed its derivative isIf $K-1<\lambda \le K^2/(K+1)$, take $t_{\ast }=\lambda /K$, where $m$ changes from $K$ on the left to $K-1$ on the right. The left derivative is nonpositive because $\lambda \le K^2/(K+1)$; the right derivative is nonnegative because $\lambda \ge K-1$. This is a minimum. If $K^2/(K+1)<\lambda \le K$, take $t_{\ast }=K/(K+1)$. There $K<\lambda /t_{\ast }\le K+1$ and the active branch has $m=K$ except for the endpoint tie; its derivative vanishes. Convexity again proves the global minimum. The formulas agree at the boundary.

For a fully specified optimal algorithm, compute $K,t_{\ast },{\rho }_{\ast }$ and $m_{\ast }=\lfloor \lambda /t_{\ast }\rfloor$ once, then use the preceding acceptance test with $t=t_{\ast }$ and $m=m_{\ast }$. At an integer tie either maximizing integer gives the same test. In code, factorials can be evaluated through the logarithm of the gamma function:and acceptance is $\log U\le \min (0,\log a_Y)$. This avoids overflowing factorials.

The optimum minimizes expected trials, the usual idealization of time when each proposal and test has constant cost. Actual runtime also depends on the implementation of discrete inversion and factorial evaluation. Simply minimizing an upper bound for $M(t)$ would not necessarily give the exact optimum above; see optimal geometric envelope for a Poisson distribution.