Hoeffding Bound Value

Problem

Hoeffding's inequality bounds the deviation of the mean of n independent variables confined to [a, b]: P(|mean - E[mean]| >= t) <= 2 * exp(-2 * n * t^2 / (b - a)^2). Return the bound capped at 1.0, and 1.0 for n <= 0, t <= 0 or b <= a.

Hint

The range width (b - a) enters squared in the denominator.

Test cases

case 1

in: [100,0.1,0,1]

expected: 0.2706705664732254

case 2

in: [25,0.2,0,1]

expected: 0.2706705664732254

case 3

in: [50,0.3,0,1]

expected: 0.0002468196081733591

case 4

in: [10,0.1,0,1]

expected: 1

case 5

in: [10,0,0,1]

expected: 1

Starter codePython

import math


def hoeffding_bound(n, t, a, b):
    # Your code here
    pass

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