# 7 Expectation and Concentration

## 7.1 Concentration inequalities

Let us compare the accuracy of some of the main concentration inequalities for the binomial distribution. We consider $$Y$$ binomial with parameters $$(n, p)$$ specified below, and compute the bounds given by Markov, Chebyshev, Bernstein, and Chernoff.

n = 30
p = 0.2
mu = n*p # mean
sigma = sqrt(n*p*(1-p)) # standard deviation
y = ceiling(mu):n

Exact upper tail:

exact = pbinom(y-1, n, p, lower.tail = FALSE)

Markov’s upper bound:

markov = mu/y

Chebyshev’s upper bound:

chebyshev = 1/(1 + (y-mu)^2/sigma^2)

Bernstein’s upper bound:

bernstein = exp(- ((y-mu)^2/2)/(sigma^2 + (y-mu)/3))

Chernoff’s upper bound:

b = y/n
chernoff = exp(- n*(b*log(b/p) + (1-b)*log((1-b)/(1-p))))

par(mfrow = c(1, 2))
matplot(y, cbind(exact, markov, chebyshev, bernstein, chernoff), type = "b", lty = 1, lwd = 2, pch = 15, xlab = "", ylab = "upper tail")
legend("topright", legend = c("exact", "markov", "chebyshev", "bernstein", "chernoff"), , lty = 1, lwd = 2, pch = 15, col = 1:5)
matplot(y, -log(cbind(exact, markov, chebyshev, bernstein, chernoff)), type = "b", lty = 1, lwd = 2, pch = 15, xlab = "", ylab = "upper tail") # applying a log transformation to zoom in on the tails 