1
$\begingroup$

The probability of obtaining any particular random graph with $m$ edges is

$$\tag{1}p^m(1-p)^{{n \choose 2}-m}.$$

Why?

I just started to study graphs, and I can't understand where expression (1) comes from.

Consider the set $V = \{1,2,\ldots,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random process: each unordered pair $\{i,j\}$ of vertices, where $i \neq j$, occurs as an edge in $E$ with probability $p$, independently of the other unordered pairs.

$\endgroup$
5
$\begingroup$

There are $\binom{n}2$ pairs of vertices, so there are $\binom{n}2$ potential edges. Choose $m$ of them, and let $G$ be the graph with vertex set $V$ and those $m$ edges. Each of those edges gets chosen with probability $p$, so the probability that you choose all $m$ of them is $p^m$. However, that says nothing about the other $\binom{n}2-m$ edges: it’s just the probability of getting a graph that includes all $m$ of the specified edges. To get $G$, you must also fail to pick each of the other $\binom{n}2-m$ edges. The probability of not picking a given edge is $1-p$, and you need to fail to pick $\binom{n}2-m$ edges, so the probability that you miss every one of these edges is

$$(1-p)^{\binom{n}2-m}\;.$$

Finally, the probability that you pick all $m$ of the edges of $G$ and fail to pick each of the $\binom{n}2-m$ edges that aren’t in $G$ is the product of the two probabilities,

$$p^m(1-p)^{\binom{n}2-m}\;.$$

$\endgroup$

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.