Chebychev Hoeffding Interval Lecture3 ICFP 2019.py

From Werner KRAUTH

This is a simple Python2 program to check with which probability the confidence interval computed from the Hoeffding or Chebychev inequality actually contains the parameter theta of the Bernoulli distribution.

import math, random, pylab
##
## theta: parameter of the Bernouilli distribution
## n: number of samples
## p: p value, confidence interval
##
n = 4000
N_test = 10000
p = 0.05
n_bins = 100
x_values = []
y_values_c = []
y_values_h = []
for tt in range(1, n_bins):
    theta = tt / float(n_bins)
    x_values.append(theta)
    Cover_h = 0.0
    Cover_c = 0.0
    for iter in range(N_test):
        theta_hat = 0
        for i in range(n):
            Upsilon = random.random()
            if Upsilon < theta: theta_hat += 1.0 / n
        q_hat = 1 - theta_hat
        if abs(theta_hat - theta) <  math.sqrt(-math.log(p / 2.0)/ 2.0 / n):
            Cover_h += 1.0 / N_test
        if abs(theta_hat - theta) <  math.sqrt(1.0 / n / 2.0 / math.sqrt(p)):
            Cover_c += 1.0 / N_test
    y_values_c.append(Cover_c)
    y_values_h.append(Cover_h)
    print theta, p, Cover_h, Cover_c, 'theta, p, cover'
pylab.title('Binomial rv: Hoeffding, & Chebychev  intervals,  $n=$' + str(n))
pylab.ylabel('Coverage probability $95$ \% standard interval')
pylab.xlabel('Bernoulli probability  $ \\theta $')
pylab.plot(x_values, y_values_c, label = 'Chebychev')
pylab.plot(x_values, y_values_h, label = 'Hoeffding')
pylab.legend(loc='lower right')
pylab.savefig('HoeffdingChebychevInterval_p.png')
pylab.show()