Azuma-Hoeffding for a martingale with bounded differences

\(P(|X_n - X_0| \ge t) \le 2\exp(-t^2 / (2 n c^2))\). It assumes nothing beyond the step size, which is why it applies to processes with no independence at all – and why it is conservative for those that do.

Usage

morie_azuma_bound(n, c, t)

Arguments

n

Steps.

c

Bound on each difference.

t

Deviation.

Value

A list with bound, typical_deviation, deviations_out.

References

Azuma K (1967) Tohoku Math J 19(3):357-367.

Examples

morie_azuma_bound(100, 1, 30)
#> $bound
#> [1] 0.02221799
#> 
#> $vacuous
#> [1] FALSE
#> 
#> $typical_deviation
#> [1] 10
#> 
#> $deviations_out
#> [1] 3
#> 
#> $n
#> [1] 100
#> 
#> $method
#> [1] "Azuma-Hoeffding inequality (Azuma 1967)"
#>