A basic question on random graph

207 Views Asked by At

Consider undirected graphs with $n$ vertices. now consider the set of all possible edges (excluding self-loops). now, select edges from the set with probability $p$ independent of the other edges. so, we have a random graph. call it $A_p$. Do, the same thing but now with probability $q(q\geq p)$ to get another random graph $A_q$.

Let $Q$ be the collection of graphs such that if $X \in Q$ and $X \subset Y$(means that the edge set of $Y$ contains edge set of $X$) then $Y \in Q$.

In a book, I see that $P(A_p \in Q) \leq P(A_q \in Q)$. I don't find any trivial argument for this. Any suggestion will be helpful.

1

There are 1 best solutions below

2
On BEST ANSWER

As mentioned by @Nate, the key notion here is called coupling. Simply put, this means that there exists two random objects $G_p$ and $G_q$ defined on a common probability space $(\Omega,\mathcal F,\Pr)$ such that:

  • $G_p$ is distributed as $A_p$
  • $G_q$ is distributed as $A_q$
  • $G_p\subseteq G_q$ with full probability

Assuming these random objects exist, one gets $$ P(A_p\in Q)=\Pr(G_p\in Q),\qquad P(A_q\in Q)=\Pr(G_q\in Q), $$ and, for every increasing property $Q$, $$ [G_p\in Q]\subseteq[G_q\in Q], $$ from which the result is direct.

A simple way to couple the random graphs $G_p$ for every $p$ in $[0,1]$ at once is to start from an i.i.d. collection $(U_e)_e$ of random variables unform on $[0,1]$, indexed by the edges $e$ of the complete graph. Then, for each $p$, the edge set of $G_p$ is defined as $$ \{e\mid U_e\leqslant p\}.$$ The property that $G_p\subseteq G_q$ for each $p\leqslant q$ follows.