Chernoff Lower Tail Bound

Problem

Multiplicative Chernoff bound for the lower tail of a sum of independent Bernoulli(p) variables. For X ~ Binomial(n, p) and 0 < delta < 1, P(X <= (1 - delta) * n * p) <= exp(-n * p * delta^2 / 2). Return 0.0 for invalid parameters and 1.0 when n * p is 0.

Hint

The lower-tail exponent only needs delta^2 instead of the full log term.

Test cases

case 1

in: [10,0.5,0.5]

expected: 0.5352614285189903

case 2

in: [100,0.5,0.1]

expected: 0.7788007830714049

case 3

in: [0,0.5,0.5]

expected: 1

case 4

in: [10,0.5,0]

expected: 0

case 5

in: [100,0.2,0.5]

expected: 0.0820849986238988

Starter codePython

import math


def chernoff_lower_tail_bound(n, p, delta):
    # Your code here
    pass

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