Question

A coin is equally likely to be either Biys or Ba/s. To figure out the bias, we toss the coin 99 times and declare By/s if the number of heads is less than 49.5 and B2/3 otherwise. Bound the error probability using the Chernoff bound derived in lecture video (in its final form, after simplifcation)

Answer 1

A coin is equally likely to be either B1/3 or B2/3. To figure out the bias, the coin is tossed 99 times and declare B2 if the number of heads is less than 49.5 and B2/3 otherwise. Let X;=1 if heads appear in a toss and X; = 0 if tails appear. 99 Let X = x; be a random variable denoting number of heads in 99 coin tossing trials. If X < 49.5, then X - Bernoulli (1/3), and if X 2 49.5, then X - Bernoulli(2/3). Therefore, the expected number of heads for X to be from Bag is, u=zx99 = 66 The Chernoff bounds are obtained as follows: Upper tail:P(X (1+) se 2+8, for all >>. Lower tail:P(x =(1-5) se 2, for all 0<<1. Therefore, for lower tail find the value of S as follows: (1-8u = 49.5 =(1-5)66= 49.5 = 8=1-405 66 =S=0.25 The error probability lower bound using Chernoff bound is as follows: 0.252x66 P(X < 49.5) se 2 = 2-2.0625 = P(X < 49.5) <0.1271