2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.