= Optimal geometric envelope for a Poisson distribution
{title2=$\rho_*=\max\{1-\lambda/K,1/(K+1)\},\quad K=\lceil\lambda\rceil$}
For a <Poisson distribution> target of mean $\lambda>0$ and a <geometric distribution> proposal with <probability mass function> $q_k=(1-t)t^k$ on the nonnegative integers, the tight <rejection sampling> envelope is
$$
M(t)=\frac{e^{-\lambda}}{1-t}\frac{(\lambda/t)^m}{m!},\qquad m=\lfloor\lambda/t\rfloor.
$$
Successive target-to-proposal ratios have ratio $\lambda/[t(k+1)]$, proving this maximizing index. The function $\log M(t)$ is the maximum of the <convex functions> $-\lambda-\log(1-t)+k\log(\lambda/t)-\log(k!)$. Within a branch its <derivative> is $(1-t)^{-1}-m/t$.
Writing $K=\lceil\lambda\rceil$, the optimum is $t_*=\min\{\lambda/K,K/(K+1)\}$, and the success parameter is $\rho_*=1-t_*$. For $K-1<\lambda\leq K^2/(K+1)$, $t_* =\lambda/K$ is a branch boundary; the left and right <derivatives> are nonpositive and nonnegative respectively. For $K^2/(K+1)<\lambda\leq K$, the active branch has a zero <derivative> at $t_*=K/(K+1)$, including a tie at the upper endpoint. Convexity proves global optimality. The minimum expected proposal count is $M(t_*)$; no claim about machine-specific instruction costs is implied.
Back to article page
