The expected height of a sub-tree

103 Views Asked by At

I have a tree with $n$ leaves. The height of tree is $n-1$ so at every level only 2 of nodes have a common parent, and other nodes have only one parent. A sample of my tree is as follow with 5 leaves and its height is 4
enter image description here

I know that $m$ leaves of $n$ leaves are infected (black nodes), I want to calculate the expected of the height of the common ancestor of all infected leaves. We know that every parent of an infected node is also infected. I tried recursive approach but I couldn't find any answer. I defined $X_{m,n}$ as the height of the common ancestor of infected nodes when the number of infected nodes is $m$ and the number of all nodes is n. We can write :
\begin{equation} E[X_{m,n}] = \frac{m}{n}E[X_{m-1,n-1}] + (1-\frac{m}{n})E[X_{m,n-1}] \\ X_{m,m} = m-1 \end{equation} Any suggestion and idea would be appreciated.