Exercise 1.10 Here is an experiment that illustrates the difference between a single bin and multiple bins. Run a computer simulation for flipping 1,000 fair coins. Flip each coin independently 10 times. Let's focus on 3 coins as follows: ci is the first coin flipped; Crand is a coin you choose at random; Cmin is the coin that had the minimum frequency of heads (pick the earlier one in case of a tie). Let vi, Vrand and Vmin be the fraction of heads you obtain for the respective three coins. (a) What is u for the three coins selected? (b) Repeat this entire experiment a large number of times (e.g., 100,000 runs of the entire experiment) to get several instances of vi, Vrand and Vmin and plot the histograms of the distributions of vi, Vrand and Vmin. Notice that which coins end up being Crand and Cmin may differ from one run to another. (c) Using (b), plot estimates for P[|v-ul > e) as a function of e, together with the Hoeffding bound 2e-2eN (on the same graph). (d) Which coins obey the Hoeffding bound, and which ones do not? Ex- plain why. (e) Relate part (d) to the multiple bins in Figure 1.10. Exercise 1.10 Here is an experiment that illustrates the difference between a single bin and multiple bins. Run a computer simulation for flipping 1,000 fair coins. Flip each coin independently 10 times. Let's focus on 3 coins as follows: ci is the first coin flipped; Crand is a coin you choose at random; Cmin is the coin that had the minimum frequency of heads (pick the earlier one in case of a tie). Let vi, Vrand and Vmin be the fraction of heads you obtain for the respective three coins. (a) What is u for the three coins selected? (b) Repeat this entire experiment a large number of times (e.g., 100,000 runs of the entire experiment) to get several instances of vi, Vrand and Vmin and plot the histograms of the distributions of vi, Vrand and Vmin. Notice that which coins end up being Crand and Cmin may differ from one run to another. (c) Using (b), plot estimates for P[|v-ul > e) as a function of e, together with the Hoeffding bound 2e-2eN (on the same graph). (d) Which coins obey the Hoeffding bound, and which ones do not? Ex- plain why. (e) Relate part (d) to the multiple bins in Figure 1.10