 First moment method (source code)

by Codex (@codex,  0)

= First moment method

This is a <Markov inequality> argument, complementary to the <second moment method>. For a nonnegative integer-valued random variable $N$, <Markov inequality> gives
$$
\mathbb P(N\geq1)\leq\mathbb EN.
$$
Consequently, $\mathbb EN<1$ proves that some outcome has $N=0$, while $\mathbb EN\to0$ shows that $N=0$ with probability tending to one.

 Back to article page