Component Exploration and Branching Processes

From Component Exploration to a Branching Process

In a sparse random graph, a vertex typically has only a modest number of neighbors, even when the graph has many vertices. This suggests exploring a component by repeatedly asking how many new vertices each discovered vertex reaches. At the beginning of the exploration, most vertices remain unseen, and each possible edge is present with probability $c/n$. The resulting offspring count is close to a Poisson random variable with mean $c$. The approximation is useful because it replaces a graph exploration with a process whose individuals reproduce independently. It is an approximation for finite explorations, not an assertion that the entire finite random graph is a tree.

Throughout, $c>0$ is fixed and $n$ tends to infinity through values with $n\ge c$, so $p=c/n$ is a valid probability. The random graph $G(n,c/n)$ has vertex set $\{1,\dots,n\}$, and every unordered pair of distinct vertices is an edge independently with probability $c/n$. Fix a root vertex, say vertex $1$; symmetry means the choice of root does not affect the distribution.

Definition: Breadth-first exploration of the root component starts with the root discovered and a queue containing it. At each step, remove the first vertex in the queue and test its edges to vertices not yet discovered. Add every newly reached vertex to the queue. The offspring count at that step is the number of vertices newly discovered. The process ends when the queue is empty; its discovered vertices are exactly the root’s connected component.

When a vertex is processed, let $D$ be the number of vertices already discovered, including that vertex. There are $n-D$ unseen candidates. The edges from the vertex being processed to these candidates have not been tested before: previous steps tested edges from other processed vertices. Independence of the edges in $G(n,c/n)$ therefore gives the exact conditional distribution

X\mid D\ \sim\ \operatorname{Bin}\!\left(n-D,\frac{c}{n}\right).

This conditional law is the starting point. It is not exactly the same at every step, because $D$ grows as the exploration proceeds. But if only a bounded number of vertices have been discovered, then $n-D$ is close to $n$. In that regime the offspring count approaches a Poisson($c$) random variable.

Why the Offspring Law Is Poisson

Lemma: Fix a nonnegative integer $d$, and let $X_n\sim\operatorname{Bin}(n-d,c/n)$. For each fixed nonnegative integer $j$, $$ \Pr(X_n=j)\ \longrightarrow\ e^{-c}\frac{c^j}{j!}. $$ Thus $X_n$ converges in distribution to a Poisson random variable of mean $c$.

Proof. For $n$ large enough that $n-d\ge j$, the binomial formula gives $\Pr(X_n=j)=\binom{n-d}{j}(c/n)^j(1-c/n)^{n-d-j}$. The first two factors can be written as \[ \binom{n-d}{j}(c/n)^j =\frac{c^j}{j!}\prod_{i=0}^{j-1}\left(1-\frac{d+i}{n}\right), \] which tends to $c^j/j!$, since the product has a fixed number of factors and each tends to $1$. Also, $(1-c/n)^{n-d-j}\to e^{-c}$, by the standard exponential limit $(1-c/n)^n\to e^{-c}$; removing the fixed number $d+j$ of factors does not change the limit. Multiplying these limits proves the displayed point-probability limit.

To see that these limits give convergence in distribution, not just convergence at each fixed $j$, note that $\mathbb E[X_n]=(n-d)c/n\le c$. For any positive integer $M$, Markov’s inequality gives $\Pr(X_n>M)\le c/(M+1)$. A Poisson($c$) random variable has the same mean $c$, so its probability of exceeding $M$ has the same bound. The probabilities up to $M$ converge term by term; the two tails can be made arbitrarily small by taking $M$ large. This proves convergence in distribution. $\square$

The lemma applies to a fixed value of $D$. In a real exploration, $D$ is random and changes over time. The next result states the appropriate finite-exploration conclusion, accounting for both this changing pool of unseen vertices and the possibility of extra edges among already discovered vertices.

Theorem: Fix $c>0$ and a nonnegative integer $r$. As $n\to\infty$, the breadth-first exploration of the root component in $G(n,c/n)$, through its first $r$ generations, converges in distribution to a Galton–Watson branching process in which each individual has an independent Poisson($c$) number of offspring. In particular, the probability of an extra edge between vertices discovered in any fixed finite portion of the exploration tends to $0$.

Here a Galton–Watson branching process starts with one individual, called generation $0$. Each individual independently has a random number of offspring with a common distribution; their offspring form the next generation. In the process in this theorem, that common distribution is Poisson($c$): the probability of exactly $j$ offspring is $e^{-c}c^j/j!$ for $j=0,1,2,\dots$.

Proof. First restrict attention to explorations that discover at most $L$ vertices, where $L$ is fixed. At any step before that restriction is exceeded, $D\le L$, so the conditional offspring law is $\operatorname{Bin}(n-D,c/n)$. For each $D\in\{1,\dots,L\}$, the lemma shows convergence to Poisson($c$); since there are only finitely many such $D$, the convergence is uniform over these possible values. Applying the conditional law step by step, the joint distribution of any fixed number of offspring counts converges to that of independent Poisson($c$) counts. One way to justify the independence in the limit is to condition successively on the exploration history: at each step the conditional offspring probabilities approach the same Poisson probabilities, regardless of the earlier counts, as long as $D\le L$.

It remains to justify that imposing the bound $L$ does not change the conclusion when $L$ is taken large. In a fixed $r$-generation exploration, the expected number of vertices at distance $j$ from the root is at most $c^j$: each such vertex has a simple path of length $j$ from the root, there are at most $n^j$ candidate paths, and each path is present with probability $(c/n)^j$. Thus the expected total number discovered through generation $r$ is at most $\sum_{j=0}^r c^j$, a finite quantity independent of $n$. Markov’s inequality bounds the probability of discovering more than $L$ vertices by $\bigl(\sum_{j=0}^r c^j\bigr)/L$, which tends to $0$ as $L\to\infty$.

Finally, among at most $L$ discovered vertices there are at most $\binom{L}{2}$ possible edges. Edges used to discover a vertex are the exploration-tree edges; any other edge between discovered vertices is an extra edge. Each such possible edge has probability $c/n$. A union bound gives probability at most $\binom{L}{2}c/n$ for any extra edge among these vertices, which tends to $0$ for fixed $L$. Combining this with the bound on exceeding $L$, then taking $L$ large, proves the theorem. $\square$

Worked Explorations

Worked Example: The First Two Conditional Offspring Counts

Take $G(100,2/100)$, so each edge is present independently with probability $p=0.02$. At the root there are $99$ unseen vertices. Therefore the number $X_1$ of root neighbors has distribution $\operatorname{Bin}(99,0.02)$, and its expectation is $99(0.02)=1.98$. In the branching-process approximation, the root’s offspring count is Poisson with mean $c=2$, whose expectation is $2$.

Suppose the root actually discovers three neighbors. There are now $D=4$ discovered vertices: the root and its three neighbors. When the first of these neighbors is processed, $100-4=96$ vertices are still unseen. Its number $X_2$ of newly discovered neighbors, conditional on the exploration so far, has distribution $\operatorname{Bin}(96,0.02)$. Its conditional expectation is $96(0.02)=1.92$, close to $2$, but it is not exactly $2$.

Check: the exact means are $99(2/100)=198/100=1.98$ at the root and $96(2/100)=192/100=1.92$ at the next step. The corresponding limiting mean is $c=2$. The small difference reflects the vertices already discovered.

Worked Example: Probabilities for a Poisson(2) Offspring Count

In the limiting process with $c=2$, let $X$ be one individual’s offspring count. Substitution into the Poisson formula gives $\Pr(X=0)=e^{-2}2^0/0!=e^{-2}$, $\Pr(X=1)=e^{-2}2^1/1!=2e^{-2}$, and $\Pr(X=2)=e^{-2}2^2/2!=2e^{-2}$. Thus the probability of at most two offspring is $e^{-2}+2e^{-2}+2e^{-2}=5e^{-2}$, approximately $0.6767$. The probability of more than two offspring is $1-5e^{-2}$, approximately $0.3233$.

Check: the two probabilities add to $5e^{-2}+(1-5e^{-2})=1$. The approximation describes the limiting offspring law; in $G(n,2/n)$, the first offspring count is exactly $\operatorname{Bin}(n-1,2/n)$, not exactly Poisson(2).

Worked Example: Expected Generation Sizes

Consider the limiting Galton–Watson process with mean offspring number $c=1/2$. Write $Z_j$ for the number of individuals in generation $j$, with $Z_0=1$. The root has expected offspring count $\mathbb E[Z_1]=1/2$. Conditional on $Z_1$, each of those individuals has expected offspring count $1/2$, so $\mathbb E[Z_2\mid Z_1]=Z_1/2$. Taking expectations gives $\mathbb E[Z_2]=\mathbb E[Z_1]/2=1/4$. One more step gives $\mathbb E[Z_3]=\mathbb E[Z_2]/2=1/8$.

Check: the expected numbers in generations $0,1,2,3$ are $1,1/2,1/4,1/8$, respectively. Each step multiplies the previous expectation by $c=1/2$, as follows directly from the conditional mean of the offspring count.

Fixed Component Sizes and the Scope of the Approximation

The branching process also predicts the probability that a fixed root has a component of a specified finite size. Let $T$ denote the total number of individuals in the Poisson($c$) branching process, with $T=\infty$ if the process never becomes extinct. For each fixed positive integer $k$, the probability that the root component in $G(n,c/n)$ has exactly $k$ vertices tends to $\Pr(T=k)$.

To justify this statement, explore until the queue empties or until $k+1$ vertices have been discovered. For the component to have size exactly $k$, the exploration must discover $k$ vertices and then exhaust the queue without discovering another. The possible lists of offspring counts for the $k$ processed vertices that achieve this are finite: the counts are nonnegative integers whose sum is $k-1$, with the queue nonempty before the final step and empty after it. For each such list, the conditional offspring probabilities converge, step by step, to the corresponding independent Poisson probabilities by the lemma. Extra edges among the $k$ discovered vertices have probability tending to zero, by the same finite-set bound in the theorem. Summing over the finite list of possibilities proves the claimed convergence.

This fixed-$k$ conclusion does not by itself describe the probability of very large components, nor does it imply that the entire component is tree-shaped when its size grows with $n$. The proof controls a fixed number of generations or a fixed finite exploration. As more vertices are discovered, the unseen pool shrinks, so offspring counts are no longer close to $\operatorname{Bin}(n,c/n)$. Also, extra edges between discovered vertices can create cycles. The branching process is a local approximation, not an exact model for the whole graph.

A Common Pitfall

Treating every offspring count as exactly $\operatorname{Bin}(n-1,c/n)$. This ignores the vertices already discovered. For example, in $G(10,2/10)$, the root has $9$ possible neighbors, so its offspring count is $\operatorname{Bin}(9,0.2)$. If the root has already discovered three neighbors, then $D=4$, leaving only $10-4=6$ unseen candidates for the next processed vertex. That vertex’s new-offspring count is $\operatorname{Bin}(6,0.2)$, not $\operatorname{Bin}(9,0.2)$. The respective means are $9(0.2)=1.8$ and $6(0.2)=1.2$.

The Poisson($c$) law captures the early-stage behavior because, for a fixed number of discoveries, $n-D$ is close to $n$. It should not be used as though the graph supplied an unlimited pool of fresh vertices at every step. The distinction matters whenever the exploration is allowed to grow large.

Check Your Understanding

Use the conditional binomial law and the finite-exploration approximation to answer these questions.

In $G(n,c/n)$, how many unseen candidates remain when $D$ vertices have been discovered, and what is the conditional offspring distribution?
For fixed $d$ and $j$, show how the binomial point probability approaches $e^{-c}c^j/j!$.
Why does the approximation not assert that every component of $G(n,c/n)$ is a tree?
In $G(50,1/50)$, compute the exact conditional mean offspring count when $D=6$, and compare it with the limiting mean.
Explain why convergence of the probability of a component of each fixed size does not alone determine the distribution of components whose sizes grow with $n$.