How to find upper bound of a probability?

Question

We roll a fair die 50 times and count the number of 2’s. Give an upper bound for the probability that the count of 2’s stays below 7. How can I approach this problem?

Answer 1

Let $X_i, i=1,2..50$ be a set of independent random variables with success probability $1/6$ (1 if 2 comes). Define $S = \sum_{i = 1}^{50}X_i$. You want to bound, $P(S \leq 7)$. One thing you can do is using Chebyshev's Inequality or the more tight Chernoff Bound. The idea is that, $P(S \leq a) = P(e^{-tS } \geq e^{-ta}) \leq\frac{ E[e^{-tS}]}{e^{-ta}}, t > 0$ by Markov's inequality. You then simply minimize over the parameter t by differentiating the bound and equation to 0. This employs the additive structure of your problem since exponentiation acts nicely to addition. In Chebyshev's inequality, you only look at the second moment and assume nothing about the others, while in Chernoff's bound you are effectively looking at higher moments so you will get tighter bounds.