MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 children(r)}E[|T_v|])$. I have not found a way to solve the CDF.

share|cite|improve this question

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.