Rejection sampling of a complex distribution including bound and proposal distribution refinement

A non-transitory storage medium storing instructions executable by an electronic processing device to perform a method including performing iterative rejection sampling of a domain in accordance with a target distribution p wherein the domain is partitioned into a partition comprising partition elements Yi each having an associated selection probability πi and an associated normalized proposal distribution qYi that is normalized over the partition element Yi and an associated bound QYi=BYi qYi where BYi is a nonnegative scaling factor, wherein at least one iteration of the iterative rejection sampling is performed by:

• selecting a partition element Ysel of the partition in accordance with the selection probabilities πi,
• obtaining a sample x of the domain in the selected partition element Ysel in accordance with the normalized proposal distribution qYsel associated with the selected partition element Ysel, and
• accepting or rejecting the sample x based on an acceptance criterion
• u
• ≤
• 
• p
• 
• Q
• Y
• sel
• 
• (
• x
• )
• wherein (i) accepting the sample comprises adding the sample to a set of accepted samples and (ii) rejecting the sample comprises replacing the selected partition element Ysel with split partition elements Aj, j=1, . . . , N where N≧2 and Ysel=∪j=1NAj.

An apparatus comprising:

• an electronic processing device configured to:
• partition a domain into one or more partition elements Yi each having an associated selection probability πi and an associated normalized proposal distribution qYi that is normalized over the partition element Yi and an associated bound QYi=BYi qYi where BYi is a nonnegative scaling factor;
• iteratively sample the domain in accordance with a target distribution p wherein each iteration includes selecting a partition element Ysel in accordance with the selection probabilities πi, acquiring a sample x from the domain within the selected partition element Ysel in accordance with the normalized proposal distribution qYsel associated with the selected partition element Ysel, and accepting or rejecting the acquired sample x based on the target distribution p and the bound QYsel=BYsel qYsel associated with the selected partition element Ysel;
• and
• during the iterative sampling, replace a partition element Yr with split partition elements Aj, j=1, . . . , N where N≧2 and Yr=∪j=1NAj, the iterative sampling continuing after the replacement.