# Probabilistic Method – 6

Q.1. Let $X_1, ..., X_n$ be non-negative real numbers. If $\lim_{n \rightarrow \infty} \frac{Var[X_n]} { (E[X_n])^2} = 0$, then $\lim_{n \to \infty} Pr [ X_n > 0] = 1$.

Solution.

$Pr [X_n \leq 0] \leq Pr[ | X_n - E[X_n] | \geq E[X_n] ] \leq \frac{Var[X_n]}{ (E[X_n])^2}.$ (the 2nd inequality follows from Chebyshev’s formula)

Taking limits as $n \rightarrow \infty$ on both sides, we get the desired result.

$-$

Q.2. If $p >> 1/n$, prove that, as $n$ approaches infinity, $G(n,p)$ contains a triangle. If $p << 1/n$, prove that, as $n$ approaches infinity, $G(n,p)$ does not contain a triangle.

Solution.

Let $Y_1, \ldots, Y_{ {n \choose 3} }$ be indicator variables for the corresponding 3-vertex-subsets inducing a triangle in $G(n,p)$.

Let $Y = \sum Y_i.$

$\therefore E[ Y ] = { n \choose 3} p^3. \ldots (1)$

$Var[Y] = \sum_i {Var [Y_i] } + \sum_{ i \neq j} {Cov[Y_i, Y_j]}$

$=$ ${n \choose 3} (p^3 - p^6) + 12 {n \choose 4} (p^5 - p^6)$

$\leq$ ${n \choose 3} p^3 + 12 {n \choose 4} p^5. \ldots (2)$

(Here, $Cov [ Y_i, Y_j] = 0$ if the corresponding triangles do not share an edge; number of ordered pairs of triangles sharing an edge $= 12 { n \choose 4}$.)

If $p << 1/n$, $E[Y] = 0$ as $n$ approaches infinity, proving one part of the question.

Now, from (1) and (2), $\frac{Var [Y]} {(E[Y])^2} \leq \Theta ( \frac{1} {n^3 p^3} + \frac {1} { n^2 p}).$

$\therefore \mbox { If } p >> 1/n \mbox{, } \lim_{n \to \infty} \frac{Var[Y]} { (E[Y])^2 } = 0,$ which implies that $lim_{n \to \infty} Pr [ Y > 0] = 1$, proving the other part of the question.

$-$

Advertisements