<Markov inequality> says that a nonnegative random variable $Y$ satisfies
$$
\mathbb P(Y\geq a)\leq\frac{\mathbb EY}{a}
\qquad(a>0).
$$
<Chebyshev inequality> says that a random variable with finite <variance> satisfies
$$
\mathbb P(|Y-\mathbb EY|\geq a)
\leq\frac{\operatorname{var}Y}{a^2}.
$$

Let $X$ count triangles in $G(n,p)$. The <triangle count in a binomial random graph> calculation gives
$$
\mu=\mathbb EX=\Theta(n^3p^3),
\qquad
\operatorname{var}X=O(n^3p^3+n^4p^5).
$$
Since $p\gg n^{-1}$,
$$
\mu\longrightarrow\infty,
\qquad
\frac{\operatorname{var}X}{\mu^2}
=O\left(\frac1{n^3p^3}+\frac1{n^2p}\right)
\longrightarrow0.
$$
For sufficiently large $n$, $\mu>200$, and <Chebyshev inequality> gives
$$
\mathbb P(X<100)
\leq\mathbb P(|X-\mu|>\mu/2)
\leq\frac{4\operatorname{var}X}{\mu^2}
\longrightarrow0.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 3 / a / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-122/3/a/solution