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.

-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: