McDiarmid Bound

Problem

McDiarmid's inequality bounds deviations of a function of independent variables whose i-th coordinate changes the value by at most c_i:

P(|f - E[f]| >= t) <= 2 * exp(-2 t^2 / sum(c_i^2)).

Return the bound capped at 1.0, and 1.0 when t <= 0 or no positive c_i are given.

Hint

This generalizes Hoeffding to functions with bounded differences.

case 1

in: [1,[1,1]]

expected: 0.7357588823428847

case 2

in: [2,[1,1]]

expected: 0.03663127777746836

case 3

in: [0.1,[1]]

expected: 1

case 4

in: [1,[]]

expected: 1

Starter codePython

import math


def mcdiarmid_bound(t, c_values):
    # Your code here
    pass

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