;-------------------------------------------------------------------------------------------------
; ---  Hoeffding Inequality (Hoeffding Bound) for estimator of parameter theta                 ---
;
;      X1, X2, ... , Xn are iid (independent identical distributed) random variables with values 
;      in the interval [a,b] and expectation parameter theta. 
;      With the sample-based estimator theta-estimator = (x1 + x2 + ... + xn)/n 
;      the probability that its deviation |theta-estimator - theta| is greater than epsilon 
;      is smaller than the Hoeffding bound 2*exp(- (2*n*eps^2)/(b-a)^2):
;
;                                                               2*n*eps^2                                                          
;          P(|theta-estimator - theta| >= epsilon) <= 2 * exp(- --------- ) = p_bound
;                                                               (b - a)^2
;
; ---  Hoeffding-Inverse computes for given epsilon and p-bound the required sample number n   ---
;
;                                     (b - a)^2
;                              n >= - --------- * (ln(p_bound) - ln(2))
;                                      2*eps^2
;
; PCM 2014/08/02
;-------------------------------------------------------------------------------------------------

(define (hoeffd n a b eps)
  (* 2 (exp (/ (* -2.0 n (* eps eps))(* (- b a)(- b a))))))

(define (hoeffd-inv a b eps p_bound)
  (round (- (/ (* (- b a)(- b a)(- (log p_bound) (log 2.0))) (* 2.0 eps eps)))))

;-------------------------------------------------------------------------------------------------

(let* ((run01 (display "n=    1.000, eps = 0.01,  bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd    1000 0 1 0.01) "----"))
       (run02 (display "n=   10.000, eps = 0.01,  bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd   10000 0 1 0.01) "-------------"))
       (run03 (display "n=   20.000, eps = 0.01,  bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd   20000 0 1 0.01) "-------------"))
       (run04 (display "n=   20.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <="                        
                       (hoeffd   20000 0 1 0.001)"-------------"))
       (run05 (display "n=   30.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd   30000 0 1 0.001)"-------------"))
       (run06 (display "n=   40.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd   40000 0 1 0.001)"-------------"))
       (run07 (display "n=  100.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd  100000 0 1 0.001)"-------------"))
       (run08 (display "n=  200.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd  200000 0 1 0.001)"-------------"))
       (run09 (display "n=  500.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd  500000 0 1 0.001)"-------------"))
       (run10 (display "n=1.000.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd 1000000 0 1 0.001)"-------------"))
       (run11 (display "n=2.000.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd 2000000 0 1 0.001)"-------------"))
       (run12 (display "n=3.000.000, eps = 0.001, bound = "
                       "P(|theta-estimator - theta| >= epsilon) <=" 
                       (hoeffd 3000000 0 1 0.001)"-------------")))
  (display "PCM 2014/08/02" "====================================================================="))

(let* ((run01 (display "for [a, b] = [0, 1], eps = 0.01 and p = 0.05 the lower bound for n = " 
                       (hoeffd-inv 0 1 0.01 0.05) "-------------"))
       (run02 (display "for [a, b] = [0, 1], eps = 0.001 and p = 0.05 the lower bound for n = " 
                       (hoeffd-inv 0 1 0.001 0.05) "-------------"))
       (run03 (display "for [a, b] = [0, 1], eps = 0.01 and p = 0.10 the lower bound for n = " 
                       (hoeffd-inv 0 1 0.01 0.10) "-------------"))
       (run04 (display "for [a, b] = [0, 1], eps = 0.001 and p = 0.10 the lower bound for n = " 
                       (hoeffd-inv 0 1 0.001 0.10) "-------------"))
       (run05 (display "for [a, b] = [0, 2], eps = 0.01 and p = 0.05 the lower bound for n = " 
                       (hoeffd-inv 0 2 0.01 0.05) "-------------"))
       (run06 (display "for [a, b] = [0, 2], eps = 0.001 and p = 0.05 the lower bound for n = " 
                       (hoeffd-inv 0 2 0.001 0.05) "-------------"))
       (run07 (display "for [a, b] = [0, 2], eps = 0.01 and p = 0.10 the lower bound for n = " 
                       (hoeffd-inv 0 2 0.01 0.10) "-------------"))
       (run08 (display "for [a, b] = [0, 2], eps = 0.001 and p = 0.10 the lower bound for n = " 
                       (hoeffd-inv 0 2 0.001 0.10) "-------------"))
       )
  (display "PCM 2014/08/02" "====================================================================="))
;-------------------------------------------------------------------------------------------------