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 [ ]: