 Optimal geometric envelope for a Poisson distribution

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 isSuccessive 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_{\ast }=\min \{\lambda /K,K/(K+1)\}$, and the success parameter is ${\rho }_{\ast }=1-t_{\ast }$. For $K-1<\lambda \le K^2/(K+1)$, $t_{\ast }=\lambda /K$ is a branch boundary; the left and right derivatives are nonpositive and nonnegative respectively. For $K^2/(K+1)<\lambda \le K$, the active branch has a zero derivative at $t_{\ast }=K/(K+1)$, including a tie at the upper endpoint. Convexity proves global optimality. The minimum expected proposal count is $M(t_{\ast })$; no claim about machine-specific instruction costs is implied.