Run a computer simulation for flipping $1000$ virtual fair coins. Flip each coin independently $10$ times. Focus on $3$ coins as follows: $c_1$ is the first coin flipped, $c_{rand}$ is a coin chosen randomly from the $1000$, and $c_{min}$ is the coin which had the minimum frequency of heads (pick the earlier one in case of a tie). Let $\nu$, $\nu_{rand}$, and $\nu_{min}$ be the fraction of heads obtained for the $3$ respective coins out of the $10$ tosses.
Run the experiment $100000$ times in order to get a full distribution of $\nu_1$, $\nu_{rand}$, and $\nu_{min}$ (note that $c_{min}$ and $c_{rand}$ will change from run to run).
The average value of $\nu_{min}$ is closest to:
Which coin(s) has a distribution of $\nu$ that satisfies the (single-bin) Hoeffding Inequality?
In [5]:
import numpy as np
import math
HEADS = 1
TAILS = 0
EPSILON = .4 # large tolerance because sample size is small
E_OUT = .5 # law of large numbers
N_COINS = 1000
N_FLIPS = 10
N_RUNS = 100000
hoeffding_bound = 2 * np.exp(-2 * EPSILON**2 * N_FLIPS)
print('hoeffding bound = ', hoeffding_bound)
In [6]:
def run():
flips = np.random.randint(2, size = (N_COINS, N_FLIPS))
c1 = flips[0]
c_rand = flips[np.random.randint(N_COINS)]
heads_count = np.count_nonzero(flips, axis=1)
c_min = flips[np.argmin(heads_count)]
v1 = c1.sum() / N_FLIPS
v_rand = c_rand.sum() / N_FLIPS
v_min = c_min.sum() / N_FLIPS
return np.array([v1, v_rand, v_min])
In [8]:
v = np.array([run() for _ in range(N_RUNS)])
print('Average values = ', np.mean(v, axis=0))
print('Look at the last value for answer to Q1.\n')
func = lambda x: math.fabs(x - E_OUT) > EPSILON
func = np.vectorize(func)
print(np.mean(func(v), axis=0))
print('Q2 = ' ,np.mean(func(v), axis=0) <= hoeffding_bound)
In [ ]: