Converging in probability to Poisson branching process

46 Views Asked by At

Consider a random directed multigraph $D(n,r)$ on vertex set $[n] = \{1, \dots , n\}$, defined as follows. Let each vertex $i \in [n]$ have $r$ out-neighbours selected uniformly at random from $[n]$. Let $X$ be a random variable that indicates the size of the largest strongly connected component of this graph.

We know that as $n \to \infty$, $\frac{X}{n} \xrightarrow[]{P} \sigma(\mu)$, where $\sigma(\mu)$ is the survival probability of a Poisson branching process with parameter $\mu$.

Is it possible to compute $\Pr(X > a)$?