Description
1. There are three biased coins, named A, B, and C, with unknown biases designated,
respectively, pA, pB, and pC. You are allowed N tosses and you have to maximise the
total number of heads in the N tosses. If you you knew the p, then the best thing
to do would be to toss the coin with the highest p, say p
∗
, and obtain an expected
reward of N p∗ heads. Since you do not know the p, let us explore two algorithms
to use in maximising the expected reward. Evaluate for the following choices of the
ps. (i) pA = 0.2, pB = 0.4, pC = 0.7 (ii) pA = 0.45, pB = 0.5, pC = 0.58. We will use
N = 20, 100, 1000, 5000.
(a) Algorithm A: Fix N1 < N and toss each coin N1/3 times. Let nA, nB, and
nC be the number of heads obtained for coins A, B, and C. For the remaining
N − N1 toss the one with the highest n. The issue here is what is the best
N1. If N1 is small then, intuitively, the wrong coin may be chosen with higher
probability (this will be made more precise later in the course). If N1 is large
then there is not enough time to use the more reliable information collected in
the first N1 times. Let R(N1) be the expected number of heads in the N tosses
for a choice of N1. Of course, this also depends on the p and N.
Peform the following computation experiment. For each of the eight cases,
simulate the above algorithm for every N1 < N 1000 times and find the sample average for R(N1) and determine the best N1. List these values. Also find the number of times the correct coin was chosen at the end of the N1 tosses for the best N1. (b) Algorithm B: We will use Hoeffding’s inequality as follows. After k tosses let nA(k), nB(k), and nC(k) be the number of times coins A, B, and C were used and let kA(k), kB(k), and kC(k) be the number of times the corresponding coins tossed heads; nA(k) + nB(k) + nC(k) = k. Consider coin A. Although we do not know pA, we can use nA(k) and kA(k) in Hoeffding’s inequality to determine at any time k, we can obtain an upper bound on pA with a reasonable amount of confidence. Denote this upper bound by UCBA(k). Specifically, use Hoeffding’s inequality to calculate UCBA(k) = kA(k) nA(k) + XA such that Pr(pA ≤ UCBA|nA, kA) ≥ (1 − α). Similarly, calculate UCBB(k) and UCBC(k). For the (k+1)-th toss choose the coin with the highest UCB(k). If there is a tie, break it randomly. This is an elementary learning algorithm where you adaptively learn to use the best coin. This algorithm also has many nice properties that a more full fledged course will explore in detail. Implement this algorithm. For each of the eight cases, run a simulation program 1 that executes the algorithm 1000 times and find the sample averages for the number of heads in N tosses and the number of times the correct coin was used. Also plot the sample average of kA(k)/k, kB(k)/k and kC(k)/ as a function of k for N = 5000. Submit the results for α = 0.1, 0.05 and α = 0.01 and the values p and N as in the previous algorithm. 2. A diagnostic laboratory has received 200 tubes for testing for Covid19. Before beginning testing, they would like to estimate how many of the 200 tubes are positive. The lab technician takes 10 test tubes randomly from the 200 and tests them individually. Assume that the test is perfect, which means that a tube always tests positive if it is positive, and negative otherwise. Let P OS ∈ {0, 1, 2, . . . , 200} be the random variable that describes the total number of positive tubes in the batch. Let n ∈ {0, 1, 2, . . . , 10} be the random variable that describes the number of positive tubes detected from the 10 tubes. (a) How will the technician estimate P OS from measured value of n? Write a program to compute the expected values E(P OS | n = k) for k = 0, 1, 2, 3, 4. (b) The technician finds that 2 of the 10 tubes are positive. She wants to know how reliable is the expected value as a measure of the number of positives. Write a program to compute the probability Pr(P OS > E(P OS) + 1 | k = 2) that the
number of positives is greater than the expected value by more than 1.
(c) Repeat the previous two parts if the total number of tubes were 400 instead of
200 and the total number of tubes tested is 20 instead of 10.
(d) Discuss how the confidence of inference changes from the first case to the second
case. Why has it changed? Is it because of the increase in total number of tubes,
or the increase in number of tubes sampled, or something else?
Make any reasonable assumption that you think you may need.
2
