Question

I can't work out the solution to the following exercise:

We have $2n$ vertices grouped in $2$ clusters of equal size. The probability of having an edge between $i$ and $j$ is $p$ if $i$ and $j$ are in the same cluster and $q$ otherwise. This is a simple SBM with $2$ clusters. The problem ask to show that if $(p+q) << \log(n)/n $, the probability of having a singleton in the realization of this SBM goes to $1$ has n goes to infinity.

Here $(p+q) << \log(n)/n $ means that $f(n) = p(n) + q(n)$ has a function of $n$ satisfy $\underset{n \rightarrow \infty}\lim \frac{f(n)}{\log(n)/n} = 0$.

I've been trying the following approach. Let $S$ the event we are interested in and for any vertex $i$ let $X_i$ be the indicator random variable of the event $i$ is singleton. Define $X = \sum_{i} X_i$, then $\mathbb{P}(S) = 1 - \mathbb{P} (X = 0)$. Since $X$ is non negative, then $\mathbb{P} (X = 0) \le \frac{\text{Var}[X]}{(\mathbb{E}[X])^2}$.

In addition, I observe that since $X_i$ is binary valued, then $\text{Var}[X_i] \le \mathbb{E}[X_i^2] = \mathbb{E}[X_i]$. So

$$\text{Var}[X] \le \mathbb{E}[X] + \sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j]$$

Computing all the terms I get:

$$\mathbb{E}[X] = 2n(1-p)^{n-1}(1-q)^{n}$$ $$\sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j] = n^2q(1-p)^{2n-2}(1-q)^{2n-1} + n(n-1)p(1-p)^{2n-3}(1-q)^{2n} \le n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)$$

For the convariances, I've split the cases when $i$ and $j$ are in the same cluster and when $i$ and $j$ are in different clusters.

All in all, I get: $$\frac{\text{Var}[X]}{(\mathbb{E}[X])^2} \le \frac{2n(1-p)^{n-1}(1-q)^{n} + n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)}{4n^2(1-p)^{2n-2}(1-q)^{2n}}$$

This term doesn't look quite right for what I'm supposed to prove, does it?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top