We will prove a generalization of the Chernoff bound to random variables lying in [0, 1],...

 

Transcribed Image Text:

We will prove a generalization of the Chernoff bound to random variables lying in [0, 1], rather than just {0, 1}. Throughout, let exp(x) denote e*. 1. Let Y be a random variable that takes values in the interval [0, 1]. Prove that for t > 0, E[exp(tY)] 1+E[Y] (e* -1). Hint: First show that exp(ty) <1+y(et -1) for all y = [0, 1]. It might be helpful to plot these two functions to compare them before trying to give a formal proof. 2. Let X1, Xn be independent random variables that take values in the interval [0, 1]. Let ie[n] X and =E[X]. Prove that for 0 < < 1, = Pr[X (16)] = Pr[exp(tx) exp(t(1 + 6))] Hint: Use Markov's inequality. 3. Prove that Pr[X (1+8)] exp(8/3). E[exp(tx)] exp(t(1+6)) Hint: Consider setting t = ln(1+8) and using part one of the question. You may use the fact that (1+6) 1+8 > ed+82/3 and that for any x 0, (1+x) e. You may also want to recall that for independent random variables Y, Z, E[YZ]=E[Y] E[Z]. We will prove a generalization of the Chernoff bound to random variables lying in [0, 1], rather than just {0, 1}. Throughout, let exp(x) denote e*. 1. Let Y be a random variable that takes values in the interval [0, 1]. Prove that for t > 0, E[exp(tY)] 1+E[Y] (e* -1). Hint: First show that exp(ty) <1+y(et -1) for all y = [0, 1]. It might be helpful to plot these two functions to compare them before trying to give a formal proof. 2. Let X1, Xn be independent random variables that take values in the interval [0, 1]. Let ie[n] X and =E[X]. Prove that for 0 < < 1, = Pr[X (16)] = Pr[exp(tx) exp(t(1 + 6))] Hint: Use Markov's inequality. 3. Prove that Pr[X (1+8)] exp(8/3). E[exp(tx)] exp(t(1+6)) Hint: Consider setting t = ln(1+8) and using part one of the question. You may use the fact that (1+6) 1+8 > ed+82/3 and that for any x 0, (1+x) e. You may also want to recall that for independent random variables Y, Z, E[YZ]=E[Y] E[Z].