In this problem, our goal is to prove the Chernoff-Hoeffding inequality step by step. The Chernoff-Hoeffding inequality says: if we have n independent random variables X1, . . . , Xn s.t. ai Xi bi, and let Sn = Pn i=1 Xi, then for any t > 0, we have P(|Sn E[Sn]| t) 2 exp 2t2 Pn i=1(bi ai)2 . (a) Show that for any a < b, we have 1 ba (bea aeb) exp 2(ba)2 8 . (b) Let Yi = Xi E[Xi]. Show that for any , we have E[eYi ] exp 2(biai)2 8 . (c) Use the Markov inequality to finish the proof