In [1]:

###########################################################################

#  Hoeffding's Inequality hdg: (n, eps, a, b) --> p

#

#     P(|theta-hat - theta| >= eps) <= 2*exp(- (2*n*eps^2)/(b - a)^2)

#

#     n = samples size (= number of random experiments)

#     eps = tolerated deviation |theta-hat - theta|

#     a = lower bound of variable's value range (0 if Bernoulli variable)

#     b = upper bound of variable's value range (1 if Bernoulli variable)

#

#  PCM 2014/08/02

###########################################################################

 

function hdg(n, eps, a, b)

    2exp(- (2n*eps^2)/(b - a)^2)

end

Out[1]:

hdg (generic function with 1 method)

In [2]:

hdg(10000, 0.01, 0, 1)

Out[2]:

0.2706705664732254

In [3]:

hdg(20000, 0.01, 0, 1)

Out[3]:

0.03663127777746836

In [4]:

hdg(2000000, 0.001, 0, 1)

Out[4]:

0.03663127777746836

In [5]:

###########################################################################

#  Inverse Hoeffding's Inequality ihdg: (eps, p, a, b) --> p

#

#     n >= - (((b - a)^2)/(2*eps^2))*(ln p - ln 2)

#

#     n = samples size (= number of random experiments)

#     eps = tolerated deviation |theta-hat - theta|

#     a = lower bound of variable's value range (0 if Bernoulli variable)

#     b = upper bound of variable's value range (1 if Bernoulli variable)

#

#  PCM 2014/08/02

###########################################################################

 

function ihdg(eps, p, a, b)

    -(((b -a)^2)/(2eps^2))*(log(p) - log(2))

end

 

Out[5]:

ihdg (generic function with 1 method)

In [6]:

ihdg(0.01, 0.10, 0, 1)

Out[6]:

14978.661367769955

In [7]:

ihdg(0.001, 0.10, 0, 1)

Out[7]:

1.4978661367769954e6

In [ ]: