Paper 2, Section II, F

Probability | Part IA, 2016

A random graph with nn nodes v1,,vnv_{1}, \ldots, v_{n} is drawn by placing an edge with probability pp between viv_{i} and vjv_{j} for all distinct ii and jj, independently. A triangle is a set of three distinct nodes vi,vj,vkv_{i}, v_{j}, v_{k} that are all connected: there are edges between viv_{i} and vjv_{j}, between vjv_{j} and vkv_{k} and between viv_{i} and vkv_{k}.

(a) Let TT be the number of triangles in this random graph. Compute the maximum value and the expectation of TT.

(b) State the Markov inequality. Show that if p=1/nαp=1 / n^{\alpha}, for some α>1\alpha>1, then P(T=0)1\mathbb{P}(T=0) \rightarrow 1 when nn \rightarrow \infty

(c) State the Chebyshev inequality. Show that if pp is such that Var[T]/E[T]20\operatorname{Var}[T] / \mathbb{E}[T]^{2} \rightarrow 0 when nn \rightarrow \infty, then P(T=0)0\mathbb{P}(T=0) \rightarrow 0 when nn \rightarrow \infty

Typos? Please submit corrections to this page on GitHub.