Hoeffding's inequality

The bound is distribution-free, which is its point; it is vacuous until the deviation exceeds (b - a) sqrt(log 2 / (2n)), and that threshold is reported so the caller can see when the bound starts to say anything.

Usage

Hffdsg(a, b, n, t)

Arguments

a

Lower end of the support.

b

Upper end of the support, greater than a.

n

Sample size, at least one.

t

Non-negative deviation.

Value

List with estimate (bound capped at 1), bound, one_sided, informative, t_min, n, method.

Details

Formula: P(|mean - E mean| >= t) <= 2 exp(-2 n t^2 / (b - a)^2).

References

Hoeffding (1963), Probability inequalities for sums of bounded random variables, JASA 58(301):13-30, Theorem 2. doi:10.1080/01621459.1963.10500830

Examples

Hffdsg(a = 0, b = 1, n = 100, t = 0.1)
#> $estimate
#> [1] 0.2706706
#> 
#> $bound
#> [1] 0.2706706
#> 
#> $one_sided
#> [1] 0.1353353
#> 
#> $informative
#> [1] 1
#> 
#> $t_min
#> [1] 0.0588705
#> 
#> $n
#> [1] 100
#> 
#> $method
#> [1] "2 exp(-2 n t^2 / (b - a)^2), Hoeffding (1963) Theorem 2"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"