Probability that vertex is isolated

Question

I just read about random graphs and the $G(n,p)$ model which has the following probabilistic properties. The probability space is given by $\Omega:=\{G \in \text{Graph} \ | \ G \ \text{has} \ n \ \text{vertices}\}$, with the sigma algebra $\text{P}(\Omega)$ and probability measure $\mathbb{P}$ given on a Graph with $n$ vertices by $$\mathbb{P}(G)=p^m(1-p)^{\binom{n}{2}-m}.$$ Now, I want to calculate the probability that a random graph has an isolated vertex, meaning a vertex with no neighbours. What does this event look like as a set? Is it given by the set $A:=\{G \in \Omega \ | \ G \ \text{has an isolated vertex} \}$ or how can I write this as a subset of $\Omega?$ I know that the probability is given by $(1-p)^{n-1}$ that a given vertex $v$ is isolated and therefore that $n (1-p)^{n-1}$ is the probability that it has any isolated vertex. However, why are those the probabilities? I cant seem to compute those. Any help is greatly appreciated!

Answer 1

Certainly $A := \{G \in \Omega \mid G \text{ has an isolated vertex} \}$ is a description of the set of all graphs in the probability space which have an isolated vertex.

To do calculations in this probability space, it helps to have a different description. It is a product space: each pair of vertices independently is adjacent with probability $p$. This gives us $$\mathbb{P}(\{G\})=p^m(1-p)^{\binom{n}{2}-m}$$ for a graph $G \in \Omega$ with $m$ edges, since we want $m$ specific pairs to be adjacent ($m$ factors of $p$) and the other $\binom n2 - m$ pairs not to be adjacent ($\binom n2 - m$ factors of $1-p$).

With this interpretation, we can show that $(1-p)^{n-1}$ is the probability that a specific vertex $v$ is isolated. There are $n-1$ other vertices; for each of them, we don't want to get an edge to $v$, so we multiply together $n-1$ factors of $1-p$.

It is not true that $n(1-p)^{n-1}$ is the probability that any vertex is isolated. This would be the probability if the events $A_v := \{G \in \Omega \mid v \text{ is isolated in }G\}$ were disjoint: two of them could not happen at the same time. In that case, $\mathbb P(A)$ would be the sum $\sum_v \mathbb P(A_v) = n (1-p)^{n-1}$.

However, these events are not disjoint: for example, in the empty graph with $0$ edges, all of them occur simultaneously.

Instead, $n(1-p)^{n-1}$ is an upper bound on $\mathbb P(A)$: the union bound. This says, in general, that if you have a bunch of events, the probability of at least one of them happening is at most the sum of their probabilities.