method of moments for concentration

The method of moments is a generalization of Chebyshev’s inequality (basic inequalities:Chebyshev’s inequality). Notice that by Markov’s inequality, we have

$$\mathbb{P}(|X-\mu |\ge \lambda )=\mathbb{P}(|X-\mu {|}^k\ge {\lambda }^k)\le \frac{\mathbb{E}[|X-\mu {|}^k]}{{\lambda }^k}.$$

Since this holds for all $k$, we can minimize the right hand side over all $k$, i.e.,

$$\mathbb{P}(|X-\mu |\ge \lambda )\le \underset{k\in \mathbb{N}}{\inf }\frac{\mathbb{E}|X-\mu {|}^k}{{\lambda }^k}.$$

This is somewhat reminiscent of the Chernoff method. In fact, the method of moments for concentration can be shown to be tighter than the Chernoff method, in the sense that

$$\underset{k\in \mathbb{N}}{\inf }\frac{\mathbb{E}|X-\mu {|}^k}{{\lambda }^k}\le \underset{t>0}{\inf }\frac{\mathbb{E}\exp (t(X-\mu ))}{\exp (t\lambda )},$$

for all $\lambda$ if $X\ge 0$ and its MGF exists. However the Chernoff method is analytically much more tractable, hence more popular. It’s difficult to find the $k$ which minimizes the left hand side.