I'm trying to prove a fiddly lemma for homework, but getting absolutely nowhere with it. Here, $G_{n,p}$ and $G_{n,m}$ represent, respectively, random graphs on $n$ vertices where the number of edges is binomially distributed with probability $p$ (i.e. any edge in the graph is present with probability $p$ and $N = {n \choose 2}$ possible edges, mean $Np$), and random graphs on $n$ vertices uniformly distributed across all possible such graphs with $m$ edges. We say $G_{n,p}$ has a property $Q = (Q_n)$ 'WHP' (with high probability) if $\mathbb{P}_{n,p}(Q_n) \to 1$ as $n \to \infty$ (similarly for $G_{n,m}$) - for example, this might be that the graph is connected, or is a forest.

Now, the lemma I want to prove is as follows:

Let $(Q_n)$ be a property of graphs. Then $G_{n,p}$ has $Q$ WHP iff for every $x > 0$ and $\epsilon > 0$ we have (as $n \to \infty$): $$\#\{m: |m-pN| \leq xn\sqrt{pq} \text{ and } \mathbb{P}_{n, m}(Q_n) < 1 - \epsilon\} < \epsilon n \sqrt{pq}$$

Now I've spent a very long time trying to chisel away at thie "lemma" but sadly I'm having no luck. In the $\Rightarrow$ direction, we have to translate from some condition in $G_{n,p}$ to one in $G_{n,m}$; the latter condition is, conceptually, on showing that the number of $m$ "close to the mean" which have a low $\mathbb{P}(Q_n)$ is small. One thought I had was to try and convert from our binomial distribution to its normal approximation and then use that (since of course $n\sqrt{pq}$ is a close approximation to the standard deviation), but again no progress.

It was suggested that it might help to observe that if $\omega (n) \to \infty$ as $n \to \infty$ then WHP,

$$|e(G_{n,p}) - pN| \leq \omega(n)n\sqrt{pq}\;,$$

but I couldn't complete the proof - nothing has worked so far. Could anyone help please? I've spent ages on this and not managed either direction, so the more detailed assistance you could provide the better. Many thanks for the help.

  • $\begingroup$ The "as $n \rightarrow \infty$" in the lemma means "$\exists n_0 \forall n \geq n_0$", the lower-case $q := 1-p$ and $\omega$ is an arbitrary series? $\endgroup$ – frafl Feb 26 '13 at 10:59
  • $\begingroup$ If $e(G_{n,p})$ is the number of edges, than by Chebyshev you get $P(|e(G_{n,p}) - pN| \leq \omega(n)n\sqrt{pq}) \geq 1 - \frac{\binom{n}{2}pq}{n^2\omega(n)^2pq}$, which approaches 1, as $n \rightarrow \infty$. $\endgroup$ – frafl Feb 26 '13 at 18:37

We observe that for any series $\omega(n) \notin \mathcal{O}(n)$ there is a series $\omega'(n) := \frac{\omega(n)}{n}$ with $\lim_{n \rightarrow \infty} \omega'(n) = \infty$. Therefore (using Chebyshev's inequality): $$\mathbb{P}_{n,p}(|e(G_{n,p}) - pN| > \omega(n)\sqrt{pq}) \leq \frac{Npq}{\omega(w)'n^2pq} \rightarrow 0 $$ as $n\rightarrow \infty$.

Since $$\forall\epsilon>0:\; \mathbb{P}_{n,p}(|e(G_{n,p}) - pN| > \omega(n)\sqrt{pq} \cap \mathbb{P}_{n,m}(Q_n) < 1 - \epsilon) \leq \mathbb{P}_{n,p}(|e(G_{n,p}) - pN| > \omega(n)\sqrt{pq})$$ this also holds for the intersection of those events. We're now able to restrict our attention to the $m$ which are "linearly close" to the expected value $pN$, but we must consider every linear series $\omega(n)=xn$. So for every $\epsilon > 0$, as $n\rightarrow \infty$: $$\mathbb{P}_{n,p}(\mathbb{P}_{n,m}(Q_n)<1-\epsilon)) \rightarrow 0 \\ \Leftrightarrow \forall x>0:\;\mathbb{P}_{n,p}(|e(G_{n,p}) - pN| \leq xn\sqrt{pq} \cap \mathbb{P}_{n,m}(Q_n) < 1 - \epsilon)\rightarrow 0$$

Now we investigate the relation between $\mathbb{P}_{n,p}(Q_n)$ and $\mathbb{P}_{n,m}(Q_n)$: $$\mathbb{P}_{n,p}(Q_n) = \mathbb{P}_{n,p}(\bigcup_{m\in\{1,\dots,N\}} (Q_n \cap e(G_{n,p}) = m)) \\= \sum_{m\in\{1,\dots,N\}} \mathbb{P}_{n,p}(e(G_{n,p}) = m)\cdot \mathbb{P}_{n,m}(Q_n)$$

For all $\epsilon$, we observe what happens, if more than $\epsilon$ values are at least $\epsilon$ far from $1$: $$\mathbb{P}_{n,p}(\mathbb{P}_{n,m}(Q_n) < 1-\epsilon) > \epsilon \Rightarrow \mathbb{P}_{n,p}(Q_n) < 1 - \epsilon^2\\ \mathbb{P}_{n,p}(Q_n) > 1 - \epsilon^2 \Rightarrow \mathbb{P}_{n,p}(\mathbb{P}_{n,m}(Q_n) < 1-\epsilon) < \epsilon$$ Since we want the conditions to hold for every $\epsilon$ eventually, we can ignore the square: $$\forall \epsilon \exists n_0\forall n > n_0:\;\mathbb{P}_{n,p}(\mathbb{P}_{n,m}(Q_n) < 1-\epsilon) > \epsilon \\ \Leftrightarrow \forall \epsilon \exists n_0\forall n > n_0:\;\mathbb{P}_{n,p}(Q_n) < 1 - \epsilon$$

We put together what we gained so far: $$\mathbb{P}_{n,m}(Q_n) \rightarrow 1\\ \Leftrightarrow \forall x>0 \forall \epsilon,\epsilon'>0\exists n_0\forall n \geq n_0:\;\\ \mathbb{P}_{n,p}(|e(G_{n,p}) - pN| \leq xn\sqrt{pq} \cap \mathbb{P}_{n,m}(Q_n) < 1 - \epsilon) < \epsilon'$$

The only thing that remains to do, is to show that we can express the latter condition without $\mathbb{P}_{n,p}$, i.e. just by counting elements, as stated in the lemma. We'll do this for each direction separately.


$\forall x>0 \forall \epsilon' > 0 \exists n_0\forall n \geq n_0:$ $$\max_{m\in\{m:|m-pN|\leq xn\sqrt{pq}\}} \mathbb{P}_{n,p}(e(G_{n,p})=m) = \mathbb{P}_{n,p}(e(G_{n,p})=pN) \leq \frac{1}{\sqrt{Npq2\pi}} + \epsilon'$$ $\Rightarrow\forall x>0 \forall \epsilon,\epsilon' > 0 \exists n_0\forall n \geq n_0:$ $$\mathbb{P}_{n,p}(|e(G_{n,p}) - pN| \leq xn\sqrt{pq} \cap \mathbb{P}_{n,m}(Q_n) < 1 - \epsilon) \leq \#\{m:|m - pN| \leq xn\sqrt{pq}, \mathbb{P}_{n,m}(Q_n) < 1 -\epsilon \} \cdot (\frac{1}{\sqrt{Npq2\pi}} + \epsilon')\\ \leq\frac{\epsilon n\sqrt{pq}}{\sqrt{Npq2\pi}}+\epsilon'\epsilon n\sqrt{pq} $$ Now observe that the set of the $m$ does not decrease as $\epsilon \rightarrow 0$, while both summands of the last line decrease. Therefore the only possible limit for both summands is $0$, which yields this direction of the statement.


$\forall x>0 \forall \epsilon > 0 \exists n_0\forall n \geq n_0:$ $$\min_{m\in\{m:|m-pN|\leq xn\sqrt{pq}\}} \mathbb{P}_{n,p}(e(G_{n,p})=m) = \mathbb{P}_{n,p}(e(G_{n,p})=pN-xn\sqrt{pq}) \geq \frac{1}{\sqrt{e^{x^2}Npq2\pi}} - \epsilon$$ We now assume the contrary of the right side:

$\Rightarrow\forall \epsilon' \exists x>0 \exists \epsilon > 0 \forall n_0\exists n \geq n_0:$ $$\mathbb{P}_{n,p}(|e(G_{n,p}) - pN| \leq xn\sqrt{pq} \cap \mathbb{P}_{n,m}(Q_n) < 1 - \epsilon) \geq \#\{m:|m - pN| \leq xn\sqrt{pq}, \mathbb{P}_{n,m}(Q_n) < 1 -\epsilon \} \cdot \frac{1}{\sqrt{e^{x^2}Npq2\pi}} - \epsilon'\\ \geq \frac{\epsilon n\sqrt{pq}}{\sqrt{e^{x^2}Npq2\pi}}-\epsilon'\epsilon n\sqrt{pq}$$

So convergence is impossible and this direction is proven indirectly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.