Relationship between the random graph models $G_{n,k}$ and $G_{n,p}$.

Question

This is an excerpt from “Introduction to Random Graphs” by Frieze and Karoński

We start with an empty graph on the set $[n]$, and insert $m$ edges in such a way that all possible ${n \choose 2} \choose m$ choices are equally likely. We denote such a random graph by $\mathbb{G}_{n, m}=\left([n], E_{n, m}\right)$ and call it a uniform random graph.

We now describe a similar model. We start with an empty graph with vertex set $[n]$ and perform ${n \choose 2}$ Bernoulli experiments inserting edges independently with probability $p$. We call such a random graph, a binomial random graph and denote it by $\mathbb{G}_{n, p}=\left([n], E_{n, p}\right)$.

Consider now a graph property $\mathscr{P}$ defined as a subset of the set of all labeled graphs on vertex set $[n]$, i.e., $\mathscr{P} \subseteq 2^{n \choose 2}$.

The author derives the following equalities:

Let $N = {n \choose 2}$. Then:

$\mathbb{P}\left(\mathbb{G}_{n, p} \in \mathscr{P}| |E_{n, p}| =k\right) =\frac{\mathbb{P}\left(\mathbb{G}_{n, p} \in \mathscr{P} \wedge\left|E_{n, p}\right| = k\right)}{\mathbb{P}\left(\left|E_{n, p}\right| = k\right)} =\underset{G \in \mathscr{P} \atop|E(G)|=k}{\sum{}} \frac{p^{k}(1-p)^{N-k}}{{N \choose k} p^{k}(1-p)^{N-k}} =\underset{G \in \mathscr{P} \atop|E(G)|=k}{\sum{}} \frac{1}{N \choose k} =\mathbb{P}\left(G_{n, k} \in \mathscr{P}\right)$

My questions are as follows:

1. When we write $\mathbb{P}(G_{n,k} \in \mathscr{P})$, are we asking for the probability that any of the $G_{n,k}$ having that property? Is it the same interpretation when we write $\mathbb{P}(|E_{n,p}| = k)$? In general, when we write $G_{n,k}$, I assume we’re talking about any of the random graphs, but not a particular one?

2. In the last part of the excerpt, I don’t quite get how the second equality (the one where we pass from division to summation) is derived (mainly because I’m unsure about the meaning of the elements in the left hand side).

3. In the last equality, I understand $\frac{1}{N \choose k}$ to be the probability that a random graph $G$ fitting our criteria would occur. So how does summing over all $G$’s give $\mathbb{P}(G_{n,k} \in \mathscr{P})$?

Answer 1

To be clear, let me write in bold the random variables.

We are generating at random the edge set $\mathbf E_{n,p}$, giving us a single random graph $\mathbf G_{n,p}$.

For any graph $G$ with $m$ edges, $\Pr[\mathbf G_{n,p} = G] = p^m (1-p)^{N-m}$.

The graph property $\mathscr P$ is a set of graphs. We have $$ \Pr[\mathbf G_{n,p} \in \mathscr P] = \sum_{G \in \mathscr P} \Pr[\mathbf G_{n,p} = G] $$ because this is a sum over disjoint events that make up the event $\mathbf G_{n,p} \in \mathscr P$.

Let $\mathscr P_k$ denote the subset of $\mathscr P$ consisting only of the graphs that have $k$ edges. Then as before, $$ \Pr[\mathbf G_{n,p} \in \mathscr P \land |\mathbf E_{n,p}| = k] = \Pr[\mathbf G_{n,p} \in \mathscr P_k] = \sum_{G \in \mathscr P_k} \Pr[\mathbf G_{n,p} = G]. $$ But now $\Pr[\mathbf G_{n,p} = G]$ simplifies to $p^k (1-p)^{N-k}$ inside the sum, since we know $G$ has $k$ edges. So we get $$ \Pr[\mathbf G_{n,p} \in \mathscr P \land |\mathbf E_{n,p}| = k] = \sum_{G \in \mathscr P_k} p^k(1-p)^{N-k} = |\mathscr P_k| p^k (1-p)^{N-k}. $$ The number of edges in $\mathbf G_{n,p}$ is binomial: $|\mathbf E_{n,p}| \sim \textit{Binomial}(N,p)$. In particular, $\Pr[|\mathbf E_{n,p}| = k] = \binom Nk p^k (1-p)^{N-k}$. By the definition of conditional probability, $$ \Pr[\mathbf G_{n,p} \in \mathscr P \mid |\mathbf E_{n,p}| = k] = \frac{\Pr[\mathbf G_{n,p} \in \mathscr P \land |\mathbf E_{n,p}| = k] }{\Pr[|\mathbf E_{n,p}| = k]} = \frac{|\mathscr P_k| p^k (1-p)^{N-k}}{\binom Nk p^k (1-p)^{N-k}} $$ which simplifies to $|\mathscr P_k|/\binom Nk$.

Now consider a second random graph: the graph $\mathbf G_{n,k}$, chosen uniformly at random from all $\binom Nk$ graphs with vertex set $[n]$ and $k$ edges. Because we are sampling uniformly, $\Pr[\mathbf G_{n,k} \in \mathscr P_k] = |\mathscr P_k|/\binom Nk$. Additionally, $\Pr[\mathbf G_{n,k} \in \mathscr P] = |\mathscr P_k|/\binom Nk$, because the only way $\mathbf G_{n,k}$ could be an element of $\mathscr P$ is by being an element of $\mathscr P_k$.

So we conclude that $$ \Pr[\mathbf G_{n,k} \in \mathscr P] = \frac{|\mathscr P_k|}{\binom Nk} = \Pr[\mathbf G_{n,p} \in \mathscr P \mid |\mathbf E_{n,p}| = k]. $$

---

In words, without algebra: every $k$-edge graph is equally likely to be the value of $\mathbf G_{n,p}$, so when we condition $\mathbf G_{n,p}$ on having $k$ edges, we get the uniform distribution on $k$-edge graphs.