Deviation from the Mean · Chernoff Inequality (Optional)

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

This is easy to compute in Python.

from scipy.special import comb

n = 60
bad = sum(comb(n, k, exact=True) for k in range(n + 1)
          if k <= n // 4 or k >= 3 * n // 4)
print(bad / 2 ** n)

0.00013451408092849532

As seen, the probability equals \(0.000134\dotsc\), while Chebyshev's inequality gives a rough upper bound of \(0.066666\dotsc\).