Random Search Budget

Problem

Compute the number of random samples needed to hit a target with a given confidence.

Return ceil(log(1 - target_conf) / log(1 - hit_prob)). Return 1 when hit_prob >= 1 and 0 when hit_prob or target_conf is not positive.

Hint

Each sample independently misses with probability 1 - hit_prob.

case 1

in: [0.01,0.95]

expected: 299

case 2

in: [0.1,0.9]

expected: 22

case 3

in: [1,0.9]

expected: 1

case 4

in: [0.5,0.5]

expected: 1

Starter codePython

def random_search_budget(hit_prob, target_conf):
    # Your code here
    pass

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