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()