Bernstein Bound Value

Problem

Bernstein's inequality for a sum with variance proxy variance and terms bounded by bound: P(|S| >= t) <= 2 * exp(-t^2 / (2 * (variance + bound * t / 3))). Return the bound capped at 1.0, and 1.0 for t <= 0, variance < 0 or bound <= 0.

Hint

The denominator blends the variance proxy with the range term bound * t / 3.

Test cases

case 1

in: [2,1,1]

expected: 0.602388423824404

case 2

in: [5,4,2]

expected: 0.3637100575365

case 3

in: [1,1,1]

expected: 1

case 4

in: [0,1,1]

expected: 1

case 5

in: [3,2,0.5]

expected: 0.33059777644317306

Starter codePython

import math


def bernstein_bound(t, variance, bound):
    # Your code here
    pass

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