A (i.e. r > 0.5) we can bound the probability that B will remain majority in S(rS > 0.5) by taking: d = 1 − 1/(2r): This bound is of course not tight at all. For example, when r = 0.5 we get a trivial bound Prob > 0. Proofs Multiplicative form Following the conditions of the multiplicative Chernoff bound, let be independent Bernoulli random variables, whose sum is , each having probability pi of being equal to 1. For a Bernoulli variable: So, using () with for any and where , If we simply set so that for , we can substitute and find This proves the result desired. Chernoff–Hoeffding theorem (additive form) Let . Taking in (), we obtain: Now, knowing that , we have Therefore, we can easily compute the infimum, using calculus: Setting the equation to zero and solving, we have so that Thus, As , we see that , so our bound is satisfied on . Having solved for , we can plug back into the equations above to find that We now have our desired result, that To complete the proof for the symmetric case, we simply define the random variable , apply the same proof, and plug it into our bound. See also Bernstein inequalities Concentration inequality − a summary of tail-bounds on random variables. Cramér's theorem Entropic value at risk Hoeffding's inequality Matrix Chernoff bound Moment generating function References Further reading Probabilistic inequalities