Write . The two multivariate normal distribution probability density functions have ratioHere is the Euclidean norm. Consequently the smallest rejection sampling envelope constant, and its acceptance probability, areThe supremum is attained at ; hence no smaller constant can dominate the ratio. Draw and an independent from the uniform distribution on . Accept whenotherwise repeat with fresh independent random variables. One can generate using a random vector with independent standard normal distribution coordinates.
For any measurable set , the joint acceptance probability is . Dividing by proves that the returned random vector has probability density function . The number of proposals has a geometric distribution on the positive integers, with expected value . When , every proposal is accepted.
For the new integrand, and , independently of dimension. Chebyshev's inequality therefore yieldsA sufficient positive integer sample count isThe ceiling function ensures that the bound is at most , so the strict-error event in the question has probability at least . The required number of accepted draws is independent of ; their expected proposal count is .
Write . The target Poisson distribution and proposal geometric distribution have probability mass functions and . Their ratio isThe successive ratio shows that a maximizing integer is , with a tie at when is an integer. Thus the tight envelope isFor any fixed , draw using (ii)'s inversion formula with this new parameter, and draw an independent from the uniform distribution on . Accept whenotherwise restart. The acceptance probability is and the expected number of proposals is .
To minimize that expected count, set . The exact answer isHere is a proof that includes the changes of maximizing integer. Each is a convex function of , since its second derivative is . Their pointwise maximum is also a convex function. When is fixed its derivative isIf , take , where changes from on the left to on the right. The left derivative is nonpositive because ; the right derivative is nonnegative because . This is a minimum. If , take . There and the active branch has 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 and once, then use the preceding acceptance test with and . 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 . 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 would not necessarily give the exact optimum above; see optimal geometric envelope for a Poisson distribution.
Integrating the conditional distribution against the exponential distribution probability density function gives, for integer ,Here the gamma function identity evaluates the integral. Henceon . Put and . The geometric series gives . Its generalized inverse, the quantile function, isThis is the smallest nonnegative integer for which ; dividing by reverses the inequality. Draw from the uniform distribution on and use this formula. The commonly used expression has the same probability distribution, but differs from the exact generalized inverse when is precisely a jump value of the cumulative distribution function. Such values have probability zero for an ideal continuous uniform draw.
Define . Given , the direct-return branch has probability , while the fallback branch distributes its remaining mass uniformly over . The law of total probability therefore gives, for integer ,The summation includes : a failed direct-return test can still return through the discrete uniform distribution draw. There is no rejection loop and no additional normalization. Summing the displayed probability mass function over gives . At , for example, at every ; it does not become one. This is an instance of the accept-or-fallback mixture identity.
