variance of number of isolated vertices in random graph $G(n,p)$

Question

Suppose we have random graph $G(n,p)$ from a uniform distribution with $n$ vertices and independently, each edge present with probability $p$. Calculating it's expected number of isolated vertices proves quite easy, chance of single vertex to be isolated is equal to $(1-p)^{n-1}$, then using linearity of probability, expected number of isolated vertices is equal to $n\times(1-p)^{n-1}$. However, I am tasked to calculate the variance of this number, or at least decent approximation of it, without any idea how to proceed.

Answer 1

I think indicators are easier to work with, as opposed to generating functions, no?

Let $(I_i:1\leqslant i \leqslant n)$ be a sequence of Bernoulli random variables, where $I_i$ if and only if vertex $i$ is isolated. Then, $\mathbb{E}[I_i]= (1-p)^{n-1}\triangleq r$. Now, let $N=\sum_{i =1}^n I_i$, the number of isolated vertices. Then, $$ {\rm var}(N) = \sum_{i=1}^n {\rm var}(I_i) + 2\sum_{i <j}{\rm cov}(I_i,I_j) = n{\rm var}(I_i)+ n(n-1){\rm cov}(I_i I_j). $$ Now, ${\rm var}(I_i)=\mathbb{E}[I_i^2]-\mathbb{E}[I_i]^2 = r-r^2=(1-p)^{n-1}(1-(1-p)^{n-1})$. Next, for ${\rm cov}(I_iI_j)=\mathbb{E}[I_iI_j]-\mathbb{E}[I_i]\mathbb{E}[I_j] = \mathbb{E}[I_iI_j]-(1-p)^{2n-2}$. Now, for the first object, note that, $I_iI_j=1$ if and only $I_i=I_j=1$, and $0$ otherwise. Note that, $\mathbb{P}(I_iI_j =1)= (1-p)^{2n-3}$, since the probability that $I_i$ and $I_j$ are both isolated is the probability that, there are no edges between $(n-2)$ vertices to $\{I_i,I_j\}$, and there is no edge between $I_i$ and $I_j$. Since the edges are independent, we conclude.

Thus, the answer is $$ n(1-p)^{n-1}(1-(1-p)^{n-1}) + n(n-1)p(1-p)^{2n-3}. $$

Answer 2

Let $P_{n,k}$ be the probability of exactly $k$ isolated vertices in $G(n,p)$. Look at what happens when we add a new vertex gives: $$ P_{n+1,k}=q^n P_{n,k-1} + (1-q^{n-k})q^k P_{n,k} + \sum_{i=1}^{n-k}\binom{k+i}{i}p^iq^kP_{n,k+i} $$ where

• $q=1-p$ as usual
• the first term is the new vertex being isolated
• the second term is new vertex not isolated but there are $k$ isolated vertices we started off from $G(n,p)$ (so there is an edge from vertex $n+1$ to one of the $n-k$ vertices which gives the $1-q^{n-k}$ factor, and $n+1$ cannot join to any of the $k$ isolated vertices in $[n]$ so the other factor $q^k$
• the sum is for starting with a graph of $k+i$ isolated vertices and this new vertex is neighbour to exactly $i$ of these.

Using this recurrence, you can show the probability generating function of the number of isolated vertices $$ G_n(z):=\sum_{k=0}^n P_{n,k}z^k $$ satisfies $$ G_n(z)=q^{n-1}(z-1)G_{n-1}(z)+G_{n-1}(1+q(z-1)). $$ This has closed form solution $$ G_n(z)=\sum_{k=0}^n\binom{n}{k}q^{nk-\binom{k}{2}}(z-1)^k $$ and so you obtain $$ \operatorname{Var}[\#\text{isolated vertices}]=nq^{n-1}((1-q^{n-1})+(n-1)pq^{n-2}). $$