# Expectation for the number of leaf nodes in a randomized tree construction

Consider this procedure for building a tree from $$v_1, v_2, ..., v_n$$:

• insert $$v_1$$
• insert $$v_2$$ and connect it to $$v_1$$ via a directional edge from $$v_2$$ to $$v_1$$
• insert $$v_3$$ and with a uniform probabiliy connect it to $$v_1$$ or $$v_2$$
• ...
• insert $$v_n$$ and with a uniform porability connect it to $$v_1$$ or $$v_2$$,... $$v_{n-1}$$

The question is what is the expectation for the number of leaf nodes?

• I’m not sure why you got stuck. Just continue the calculation. – Yuval Filmus Jan 19 '19 at 7:36
• @YuvalFilmus Okay, I continued a bit more and made my stuck point more explicit. – Ahmad Jan 19 '19 at 8:08
• I’m still not sure why you think you’re stuck. The product of probabilities is telescoping so is easy to compute. – Yuval Filmus Jan 19 '19 at 8:57
• @YuvalFilmus I just try to calculate some probabilities but I'm almost goalless. Please check if you meant the same telescopic product I reached? And, then how to continue? – Ahmad Jan 19 '19 at 9:30
• Now it remains to sum an arithmetic series. There’s no need for us to spell out each step for you. You seem to be perfectly capable of carrying out the calculation on your own. – Yuval Filmus Jan 19 '19 at 10:05

I tried to define a random variable $$x_i$$ for a node $$i$$, which is $$1$$ if it is a leaf node and $$0$$ otherwise.

Then, I must find $$E(X) = \sum_i E(x_i)$$.

If $$A_{ij}$$ shows the event that the node $$j$$ is connected to the node $$i$$, then I must have $$\bar A_{ij}$$, and then $$Pr[x_i = 1] = Pr[\bar A_{ii+1}].Pr[\bar A_{ii+2} | \bar A_{ii+1}]....$$

$$j$$ must be bigger than $$i$$, pointing to the nodes that arrive after the node $$i$$. Let $$j$$ be $$i+1$$.

$$Pr[A_{ij}] = \frac{1}{j-1}$$ so $$Pr[\bar A_{ij}] = 1- \frac{1}{j-1} = \frac{j-2}{j-1}$$

The reason is that when the node $$j$$ arrives there are $$j-1$$ nodes to be attached to. Similarly:

$$Pr[\bar A_{ij+1} | \bar A_{ij}] = 1 - \frac{1}{j} = \frac{j-1}{j}$$

so

$$Pr[\bar A_{in} | \bar A_{ij} \cap \bar A_{ij+1} ... \cap \bar A_{in-1} ] = 1- \frac{1}{n-1} = \frac{n-2}{n-1}$$

So, let's multiply them to each other:

$$Pr[x_i = 1] = \frac{j-2}{j-1} . \frac{j-1}{j} .. \frac{n-2}{n-1}$$

Since the product is telescopic, we have:

$$Pr[x_i = 1] = \frac{j-2}{n-1}$$

By replacing $$j$$ with $$i+1$$:

$$E(x_i) = Pr[x_i = 1] = \frac{i-1}{n-1}$$

So $$E(X) = \sum_{i=1}^{n}E(x_i) = \sum_{i=1}^{n}\frac{i-1}{n-1} = \frac{1}{n-1}\frac{n(n-1)}{2} = \frac{n}{2}$$