Expected Degrees

What this random tree construction interview question tests

This is a medium-difficulty probability question that asks you to compute the expected degree of a vertex in a randomly-constructed rooted tree. It rewards clear reasoning about linearity of expectation and the ability to decompose degree contributions across multiple random choices.

The question probes whether you can identify which random events contribute to a vertex's degree (both incoming and outgoing edges) and then set up the expectation calculation in a way that avoids heavy casework. The harmonic-number form of the answer suggests that you should think carefully about how many future vertices will be eligible to connect back to a given node.

• Linearity of expectation and indicator random variables
• Distinguishing parent-child edges in a rooted tree
• Summation and harmonic sums