Problem 1. Let {X₁₁ be an i.i.d. sequence of Bernoulli variables with parameter α = (0, 1], and consider the binomial random variable ZË = Σ¦±1 ×₁. The goal of this exercise is to prove, for any 8 (0, α), a sharp upper bound on the tail probability P(Zn ≤8n). (a) Show that P(Zл ≤dn) ≤enD(8//x), where the quantity б 1-8 1- D(8||x) := 8 log + (1-8) log | is the Kullback-Leibler divergence between the Bernoulli distributions with parameters & and a respectively. (b) Show that the bound from part (a) is strictly better than the Hoeffding bound for all 8 € (0,α).

Fig: 1