Q1) When we toss a fair coin, we expect that we get roughly half-and-half Hs and Ts. Of course, this might not happen in general: the question is, how bad can the difference get ?

Consider a sequence of 2n coin tosses, and let X H be the number of heads and X T be the number of Ts in the resulting sequence. Obviously, EX H = EX T = n, and therefore E(X H - X T ) = 0. Show that for any ε > 0, there exists a constant c such that Pr[X H - X T > c√ n] ≤ ε Note the quantification: in general, c will be a function of ε.