Question

PROBABILITY QUESTION

A fair coin is tossed n times. S_n is the # of heads after tossed. Show that P(S_n ≥ 3n/4) ≤ e ^-n/8 .

Answer 1

E[Sn] = n/2 and Var[Sn] = n * (1/2) * (1-1/2) = n/4

For a large n, we can use Normal approximation to Binomial distribution and Sn ~ N(n/2, n/4)

--- (1)

where Z ~ N(0, 1)

Now,

Let x = t + y, then,  

where we know that

Thus,

---(2)

From (1) and (2)