Rejection Sampling Acceptance Probability

Problem

Discrete rejection sampling draws from proposal and accepts with probability target[x] / (M * proposal[x]) where M = max(target[x] / proposal[x]) over proposal[x] > 0. The overall acceptance probability is 1 / M. Return 1 / M, or 0.0 when a target atom has no proposal mass or the inputs are invalid.

Hint

The average acceptance rate is the reciprocal of the maximum importance weight.

Test cases

case 1

in: [[0.2,0.3,0.5],[0.3333333333333333,0.3333333333333333,0.3333333333333333]]

expected: 0.6666666666666666

case 2

in: [[0.5,0.5],[0.9,0.1]]

expected: 0.2

case 3

in: [[1],[1]]

expected: 1

case 4

in: [[0.5,0.5],[0,1]]

expected: 0

Starter codePython

def rejection_sampling_acceptance(target, proposal):
    # Your code here
    pass

4 test cases · run your code against them in the editor