Azuma-Hoeffding concentration bound for martingales

Formula: P(M_n - M_0 >= t) <= exp(-t^2 / (2 sum_i c_i^2))

Usage

Azuma(c, t)

Arguments

c

See Usage.

t

See Usage.

Value

List with bound (one-sided), bound_two_sided, sum_c2, t, n.

References

Azuma (1967), Weighted sums of certain dependent random variables, Tohoku Mathematical Journal 19:357-367; Hoeffding (1963), JASA 58:13-30. Neither is held locally; the inequality is stated in this exact form in every standard reference consulted.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Azuma(V, V)
#> $bound
#> [1] 0.9975520 0.9902440 0.9781827 0.9615433 0.9405650 0.9155454 0.8868335
#> [8] 0.8548214
#> 
#> $bound_two_sided
#> [1] 1
#> 
#> $sum_c2
#> [1] 204
#> 
#> $t
#> [1] 1 2 3 4 5 6 7 8
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Azuma-Hoeffding bound"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"