# Understanding the expression $p^m(1-p)^{{n \choose 2}-m}$ in random graphs.

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.

## 1 Answer

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}\;.$$