Chernoff Bound - Sum of Repeated Random Variable

Let:

• 𝑆 = 𝑋₁ + 𝑋₂ + … + 𝑋_𝑛
• 𝐄[𝑋_𝑖] = 𝑝
• 𝑆 = 𝑋₁ + 𝑋₂ + … + 𝑋_𝑛
• 𝐄[𝑆] = 𝑛𝑝 # because expectation is linear

Chernoff Bound states:

• $\mathbf{P}(S>𝜇+𝛿n)\le {𝜀}^{-2n{𝛿}^2}$
• $\mathbf{P}(S<𝜇-𝛿n)\le {𝜀}^{-2n{𝛿}^2}$

Thus:

• $\mathbf{P}(|S-𝜇|>𝛿n)\le 2{𝜀}^{-2n{𝛿}^2}$