Mfcttrf

Suppose we have random graph $G(n,p)$ from 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 $ntimes(1-p)^n-1$. However, I am tasked to calculate 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:1leqslant i leqslant n)$ be a sequence of Bernoulli random variables, where $I_i$ if and only if vertex $i$ is isolated. Then, $mathbbE[I_i]= (1-p)^n-1triangleq 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) + 2sum_i <jrm cov(I_i,I_j) = nrm var(I_i)+ n(n-1)rm cov(I_i I_j).
$$
Now, $rm var(I_i)=mathbbE[I_i^2]-mathbbE[I_i]^2 = r-r^2=(1-p)^n-1(1-(1-p)^n-1)$. Next, for $rm cov(I_iI_j)=mathbbE[I_iI_j]-mathbbE[I_i]mathbbE[I_j] = mathbbE[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, $mathbbP(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-kbinomk+iip^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,kz^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^nbinomnkq^nk-binomk2(z-1)^k
$$
and so you obtain
$$
operatornameVar[#textisolated vertices]=nq^n-1((1-q^n-1)+(n-1)pq^n-2).
$$