Probability with Measure

6.2 The Paley-Zygmund inequality \((\Delta )\)

Recall that Markov’s and Chebyshev’s inequalities controlled how large \(\P [X\geq c]\) could become, using the moments of the random variable \(X\). The Paley-Zygmund inequality is similar in style, but it seeks to control how large \(X\) can become relative to \(\E [X]\).

Lemma 6.2.1 (Paley-Zymund Inequality) Let \(X\) be a non-negative random variable and suppose that \(0<\E [X^2]<\infty \). Then for any \(\theta \in [0,1]\),

\[\P [X>\theta \E [X]] \geq (1-\theta )^2\frac {\E [X]^2}{\E [X^2]}.\]

Proof: Note that \(X=X\1_{\{X\leq \theta \E [X]\}} + X\1_{X>\theta \E [X]}\) and take expectations to obtain

\begin{equation} \label {eq:pz_0} \E [X]=\E \l [X\1_{\{X\leq \theta \E [X]\}}\r ] + \E \l [X\1_{\{X>\theta \E [X]\}}\r ]. \end{equation}

We will bound the two terms on the right hand side of the above. If \(\1_{\{X\leq \theta \E [X]\}}\) is non-zero then \(X\leq \theta \E [X]\), so also \(X\1_{\{X\leq \theta \E [X]\}}\leq \theta \E [X]\). Hence we have \(\E [X\1_{X\leq \theta \E [X]}] \leq \theta \E [X]\). For the second term, we apply the Cauchy-Schwarz inequality (Exercise 5.12) and obtain that

\[\E \l [X\1_{\{X>\theta \E [X]\}}\r ]\leq \l (\E [X^2]\E [\1_{\{X>\theta \E [X]\}}^2]\r )^{1/2}.\]

Indicator functions are either zero or one, hence \(\1_A^2=\1_A\), and by (4.2) satisfy \(\E [\1_A]=\P [A]\). We thus obtain that above equation is bounded above by \((\E [X^2]\P [X>\theta \E [X]])^{1/2}\). Putting all this into (6.2) we obtain

\[\E [X]\leq \theta \E [X] +\l (\E [X^2]\P [X>\theta \E [X]]\r )^{1/2}\]

which rearranges to the required result. ∎

The most common application of the Paley-Zymund inequality is to set \(\theta =0\) and obtain

\begin{equation} \label {eq:paley_zygmund_0} \P [X>0]\geq \frac {\E [X]^2}{\E [X^2]}. \end{equation}

In combination with upper bounds on \(\E [X]\) and lower bounds on \(\E [X^2]\), equation (6.3) is often used to show that \(X\) is not identically zero. This technique is particularly useful when the random variable \(X\) is known to be a limit of some sequence \((X_n)\), and bounds on \(\E [X]\) and \(\E [X^2]\) can be obtained from corresponding bounds on \(\E [X_n]\) and \(\E [X_n^2]\) via the monotone and dominated convergence theorems.

More generally (6.3) simply provides a lower bound on the probability that some random variable is non-zero. It is often called the second moment method.

Example 6.2.2 Consider a graph with \(n\) vertices. For each (unordered) pair of distinct vertices \((v_1,v_2)\), the edge from \(v_1\) to \(v_2\) is present in the graph with probability \(p\), independent of all other pairs of vertices. This graph is known as the Erdős-Renyi graph, often denoted by \(G(n,p)\). We are interested in whether \(G(n,p)\) contains isolated vertices, which are vertices that have no edges connected to them, as \(n\to \infty \).

Let \(E_i\) be the event that vertex \(i\) is isolated, and let \(Y_n=\sum _{i=1}^n \1_{E_i}\) be the number of isolated vertices. The probability of each vertex being isolated is \(\P [E_i]=(1-p)^{n-1}\), so the expected number of isolated vertices is \(\E [Y_n]=\sum _{i=1}^n\P [E_i]=n(1-p)^{n-1}\).

A pair of distinct vertices, that is \(i\neq j\), is part of \(2n-3\) edges (and not \(2n-2\), because they are both part of the edge between them), so \(\P [E_i\cap E_j]=(1-p)^{2n-3}\). We can calculate the second moment too, with the help of Exercise 2.5, as
\(\seteqnumber{0}{6.}{3}\)
\begin{align*} \E [Y_n^2] &= \sum _{i,j=1}^n \P [E_i\cap E_j] \\ &= \sum _{i=1}^n\P [E_i] +\sum _{\stackrel {i,j=1}{i\neq j}}^n \P [E_i\cap E_j] \\ &= n(1-p)^{n-1}+n(n-1)(1-p)^{2n-3} \end{align*} Note that since \(Y\) takes integer values, \(\P [Y>0]=\P [Y\geq 1]\). The Paley-Zygmund inequality gives that

\[\P [Y\geq 1]\geq \frac {n^2(1-p)^{2n-2}}{n(1-p)^{n-1}+n(n-1)(1-p)^{2n-3}} =\frac {1}{\frac {1}{n}(1-p)^{-n-3}+\frac {n-1}{n}(1-p)^{-1}}.\]

Allowing \(p\) to depend on \(n\), it follows that if \(\frac {1}{n(1-p)^n}\to 0\), or equivalently \(n(1-p)^n\to \infty \), as \(n\to \infty \) then we must have \(\P [Y\geq 1]\to 1\) as \(n\to \infty \). If that condition holds, then for large \(n\) it is very likely that \(G(n,p)\) contains at least one isolated vertex.