MediumProbabilitypr-131

Max Load Probability Bound

Problem

Union bound on the maximum load when balls are thrown independently and uniformly into bins:

P(max load >= k) <= bins * P(Binomial(balls, 1 / bins) >= k),

capped at 1.0. Return 1.0 for k <= 0, and 0.0 for invalid inputs or k > balls.

Hint

Apply the union bound over bins and condition on one bin.

case 1

in: [10,10,3]

expected: 0.7019082640000002

case 2

in: [100,100,10]

expected: 0.000007631587532260614

case 3

in: [10,10,0]

expected: 1

case 4

in: [5,10,6]

expected: 0

case 5

in: [5,0,2]

expected: 0

Starter codePython

import math


def max_load_probability_bound(balls, bins, k):
    # Your code here
    pass

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