Assume that we have the following process of randomly creating a tree: we start from a initial tree $\mathcal T_0 = \left\{v_0\right\}$ (a tree containing one node). At each time step $t$, we choose a random node of $\mathcal T_{t-1}$ and we add a child to that node to create $\mathcal T_t$. For example, for $\mathcal T_1=\left\{v_0, v_1\right\}$ and $v_1$ is a child of $v_0$. For $\mathcal T_2 = \left\{v_0, v_1, v_2\right\}$, we have two possibilities either $v_1$ and $v_2$ are children of $v_0$ or $v_1$ is the child of $v_0$ and $v_2$ is a child of $v_1$. Let,
$$ L_t:\,\text{number of children of the node $v_0$ in $\mathcal T_t$} $$
and $$ H_t:\, \text{the height of $\mathcal T_t$} $$
Now I want to find a efficient method to compute the following probabilities:
- $P\left[L_t = \ell\right]$
- $P\left[H_t \ge h\right]$
- $P\left[H_t \ge h \cap L_t = \ell\right]$
What I mean by a efficient method is given $t$, $\ell$ and $h$ I can compute each of theses probabilities in a polynomial time complexity.