MediumProbabilitypr-117

Azuma Bound Value

Problem

Azuma's inequality bounds the deviations of a martingale with bounded differences c_i:

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

Return the bound capped at 1.0, and 1.0 for t <= 0 or a nonpositive sum of squares.

Hint

The denominator uses twice the sum of squared difference bounds.

case 1

in: [4,1]

expected: 0.0006709252558050237

case 2

in: [10,5]

expected: 0.00009079985952496971

case 3

in: [2,4]

expected: 1

case 4

in: [0,1]

expected: 1

Starter codePython

import math


def azuma_bound(t, sum_c_squares):
    # Your code here
    pass

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