Probability of having at most a certain number of isolated vertices in random graph?

197 Views Asked by At

In Erdos-Renyi model of Binomial random graphs $G(n,p)$, if we have $np = \ln n - \ln \ln \ln n$, then what is the probability of having at most $a \ln n$ vertices be isolated.

Having isolated vertices in $G(n,p)$ has sharp threshold probability $p = \ln n / n$. So we are below the threshold probability. There must be isolated vertices. We need to compute $P(G(n,p) \text{has isolated vertices} \leq a \ln n)$; $a>0$.

If I define my event $X:= \text{number of isolated vertices} > a \ln n$, then using Markov's inequality, $P(X \geq 1) \leq EX$, and $EX = \frac{1}{O(\ln n)!}O(e^{\frac{\ln n}{ n} })$ which goes to 0 as $n \rightarrow \infty$.

But only this argument will not ensure that $P(\text{number of isolated vertices} \leq a \ln n) \rightarrow 1$.

Remark: We need to calculate $P(\text{number of isolated vertices}\leq a\ln n)$. By simply calculating the probabilities of all upto $a\ln n$ number of vertices, we get:

(let $X$ be the event of having $j = 1, \ldots, a\ln n$, number of isolated vertices)

$P(X \leq a\ln n) = \sum_{j = 1}^{a\ln n}(1-p)^{jn-j(j+1)/2}$.

Evaluating this, with $p=\ln /n - (\ln \ln\ln n )/ n$, we get something similar to a geometric series $P(X \leq a\ln n) = \sum_{j = 1}^{a\ln n}(\frac{\ln\ln n}{n})^{j+\frac{j(j+1)}{2n}}$.

Can it be written in a close form?

To get an upper bound, I take the max probability term (when j=1), $a\ln n$ times.

$P(X \leq a\ln n) \leq a\ln n(\frac{\ln\ln n}{n})^{1+\frac{1}{2n}}$