Probability that one random graph is contained in another

Question

Let $G_{n,p}, n\in \mathbb{N}, p\in(0,1)$ be the binomial random graph, i.e. a graph on $n$ vertices where an edge is in $G_{n,p}$ with probability $p$.

For some $q\in(0,1)$, what is the probability that $G_{n,p}\subset G_{n,q}$?

Answer 1

Assuming that the two graphs are independent of each other, we could do the following, where $N:=\binom{n}{2}$:$\newcommand{\order}[1]{\lvert #1\rvert}$

Start by partition the set of all graphs on $[n]$ based on the number of edges they contain; let $\mathcal{G}_{n,k}$ be the set of such graphs on $[n]$ with $k$ edges. Then we get $$ \begin{align*} P(G_{n,p}\subseteq G_{n,q})=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}P(G_{n,p}=G,\ G_{n,p}\subseteq G_{n,q})=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}P(G_{n,p}=G,\ G\subseteq G_{n,q}). \end{align*} $$ Now, of course these events are independent, and so we can break up the probability. Further, if $G$ contains $k$ edges, then $P(G_{n,p}=G)=p^k(1-p)^{N-k}$ and $P(G\subseteq G_{n,q})=q^k$. Hence $$ \begin{align*} P(G_{n,p}\subseteq G_{n,q})&=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}P(G_{n,p}=G)P(G\subseteq G_{n,q})\\ &=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}p^k(1-p)^{N-k}q^k\\ &=\sum_{k=0}^{N}\binom{N}{k}(pq)^k(1-p)^{N-k}\\ &=(1-p+pq)^N. \end{align*} $$ Note that this is definitely in $[0,1]$: writing the base as $1-(p-pq)=1-p(1-q)$ shows this.

---

Another way to come to this:

The event that $G_{n,p}\subseteq G_{n,q}$ is precisely the event that each edge is either not contained in $G_{n,p}$ or is contained in both $G_{n,p}$ and $G_{n,q}$. These are disjoint events, and the events that this holds for each edge are independent of each other.

For a given edge $e$, the probability of this is $$ P(e\notin G_{n,p}\text{ or }e\in G_{n,p}\text{ and }G_{n,q})=(1-p) + pq. $$ Noting that there are $N$ such edges, we again get $$ P(G_{n,p}\subseteq G_{n,q})=(1-p+pq)^N. $$