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

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.

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

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}).$$