Visualization of law of large numbers

import numpy as np
import matplotlib.pyplot as plt
import scipy.stats as stats
import numpy.matlib

p = 0.5
Nset = np.round(np.logspace(2,5,100)).astype(int)
x = np.zeros((1000,Nset.size))
for i in range(Nset.size):
  N = Nset[i]
  x[:,i] = stats.binom.rvs(N, p, size=1000)/N

Nset_grid = np.matlib.repmat(Nset, 1000, 1)
plt.semilogx(Nset_grid, x,'ko');
plt.semilogx(Nset, p + 3*np.sqrt((p*(1-p))/Nset), 'r', linewidth=6)
plt.semilogx(Nset, p - 3*np.sqrt((p*(1-p))/Nset), 'r', linewidth=6)

[<matplotlib.lines.Line2D at 0x7fa13d09b8d0>]

Chernoff Bound for average of i.i.d. Gaussian

import numpy as np
import matplotlib.pyplot as plt
import scipy.stats as stats
import numpy.matlib

# Gaussian
mu = 0
sigma = 1

epsilon = 0.1
Nset = np.round(np.logspace(1,3.9,100)).astype(int)
x = np.zeros((10000,Nset.size))
prob_exact  = np.zeros(100)
prob_chebyshev = np.zeros(100)
prob_chernoff  = np.zeros(100)
for i in range(Nset.size):
  N = Nset[i]
  prob_exact[i]     = 1-stats.norm.cdf(np.sqrt(N)*epsilon/sigma)
  prob_chebyshev[i] = sigma**2 /(N* (epsilon**2) )
  prob_chernoff[i]  = np.exp(-N*epsilon**2/(2*(sigma**2)))

plt.loglog(Nset, prob_exact,'x')
plt.loglog(Nset, prob_chebyshev)
plt.loglog(Nset, prob_chernoff)

[<matplotlib.lines.Line2D at 0x7fa13d326c10>]

Chebyshev Bound for average of i.i.d. Bernoulli

import numpy as np
import matplotlib.pyplot as plt
import scipy.stats as stats
import numpy.matlib

# Sum of Bernoulli = Binomial
p = 0.5
epsilon = 0.01
Nset = np.round(np.logspace(2,5,100)).astype(int)
x = np.zeros((10000,Nset.size))
prob_simulate  = np.zeros(100)
prob_chebyshev = np.zeros(100)
prob_hoeffding = np.zeros(100)
for i in range(Nset.size):
  N = Nset[i]
  x[:,i] = stats.binom.rvs(N, p, size=10000)/N
  prob_simulate[i]  = np.mean((np.abs(x[:,i]-p)>epsilon).astype(float))
  prob_chebyshev[i] = p*(1-p)/(N* (epsilon**2) )

plt.loglog(Nset, prob_simulate,'x')
plt.loglog(Nset, prob_chebyshev)

[<matplotlib.lines.Line2D at 0x7fa13ecc7090>]

Hoeffding Bound for average of i.i.d. Bernoulli

import numpy as np
import matplotlib.pyplot as plt
import scipy.stats as stats
import numpy.matlib

# Sum of Bernoulli = Binomial
p = 0.5
epsilon = 0.01
Nset = np.round(np.logspace(2,5,100)).astype(int)
x = np.zeros((10000,Nset.size))
prob_simulate  = np.zeros(100)
prob_chebyshev = np.zeros(100)
prob_hoeffding = np.zeros(100)
for i in range(Nset.size):
  N = Nset[i]
  x[:,i] = stats.binom.rvs(N, p, size=10000)/N
  prob_simulate[i]  = np.mean((np.abs(x[:,i]-p)>epsilon).astype(float))
  prob_hoeffding[i] = 2*np.exp(-2*N*epsilon**2)

plt.loglog(Nset, prob_simulate,'x')
plt.loglog(Nset, prob_hoeffding)

[<matplotlib.lines.Line2D at 0x7fa13e0c2f90>]

%%shell
jupyter nbconvert --to html /content/ECE595_lecture15.ipynb