Connected component of a deformed tree

Question

I have a balanced tree $T(V,E)$ of constant degree $d$. I remove each vertex from the tree with equal probability $p$. I refer to the largest remaining tree with the same root as $T'(V',E')$ (this tree can potentially be empty in the case that the root of $T$ was removed). I am trying to solve the CDF $P(|V'| > n)$.

I was able to solve the expectation $E[|V'|]$ using the observation that the expectation of the number of vertices in a tree with root $r$ is $E[|T_r|] = (1-p)(1 + \sum_{v \in \mathrm{children}(r)}E[|T_v|])$. I have not found a way to solve the CDF.

Answer 1

Your object is (essentially) a branching process with binomial offspring distribution $B(d,p)$ (if $d$ is the branching factor; $d-1$ if $d$ is the degree). The binomial case is likely to be well studied, so if good estimates exist then you might find them by searching on "binomial branching process".

Your observation corresponds to the fact they can be usefully studied via generating functions. Let $p_n$ be the probability that there are $n$ vertices in total, and let $G(z) = \sum_{n=0}^\infty p_n z^n$. Then the observation $p_{n+1} = (1-p)\mathbb{P}(|V_1| + \cdots + |V_d| = n)$ leads to the functional equation $$ (1-p)zG(z)^d = G(z) - p_0 = G(z) - p $$ by multiplying by $z^{n+1}$, then summing over $n$.