1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I’m not sure why you got stuck. Just continue the calculation. $\endgroup$ Jan 19, 2019 at 7:36
  • $\begingroup$ @YuvalFilmus Okay, I continued a bit more and made my stuck point more explicit. $\endgroup$
    – Ahmad
    Jan 19, 2019 at 8:08
  • $\begingroup$ I’m still not sure why you think you’re stuck. The product of probabilities is telescoping so is easy to compute. $\endgroup$ Jan 19, 2019 at 8:57
  • $\begingroup$ @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? $\endgroup$
    – Ahmad
    Jan 19, 2019 at 9:30
  • $\begingroup$ 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. $\endgroup$ Jan 19, 2019 at 10:05

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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