Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 12 / 1

Let $Z$ be a real random variable with finite expectation $m$ and finite variance ${\sigma }^2$. The Chebyshev inequality isThe proof is the pointwise comparisonTaking expectations and using the definition of variance givesDivision by the positive number $t^2$ proves the Chebyshev inequality, including the case ${\sigma }^2=0$. Equivalently, this is the Markov inequality applied to the nonnegative random variable $(Z-m{)}^2$.

Write $p=p(n)$ and let $T$ be the triangle count in a binomial random graph. For every three-element set $S$ of vertices, let $I_S$ be the indicator random variable that its three edges are present. ThenFor two distinct triples $S,R$, their indicator random variables are independent random variables unless they share an edge. Sharing just one vertex still leaves the sets of relevant edges disjoint. If they share an edge, their union has five edges, and thereforeThere are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)$ unordered pairs of distinct triangles in a graph sharing an edge: choose that edge, and then choose their two additional vertices. The variance of a sum consequently gives the exact formulaFor sufficiently large $n$, the hypothesis $np\to \infty$ ensures $p>0$, so $\mu >0$. Dropping negative terms and simplifying the binomial coefficients,Here $n^{2}p=n(np)\to \infty$ as well. The event $T\ge 2\mu$ implies $|T-\mu |\ge \mu$. Applying the Chebyshev inequality from part (i) gives the requested conclusion:Thus the triangle count is concentrated around its expectation throughout this range of the binomial random graph.