La altura esperada de un subárbol

Question

Tengo un árbol con $n$ hojas. La altura del árbol es $n-1$ por lo que en cada nivel sólo 2 de los nodos tienen un padre común, y otros nodos sólo tienen un padre. Un ejemplo de mi árbol es el siguiente con 5 hojas y su altura es de 4

Sé que $m$ hojas de $n$ hojas están infectadas (nodos negros), quiero calcular la expectativa de la altura del ancestro común de todas las hojas infectadas. Sabemos que todos los padres de un nodo infectado también están infectados. He intentado un enfoque recursivo pero no he encontrado ninguna respuesta. He definido $X_{m,n}$ como la altura del ancestro común de los nodos infectados cuando el número de nodos infectados es $m$ y el número de todos los nodos es n. Podemos escribir :
\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} Cualquier sugerencia e idea será apreciada.

Answer 1

Interesante pregunta, pero no creo que la expectativa esté bien definida sólo con esta estructura. Por ejemplo, hay dos árboles únicos con altura 3:

      o              o
     / \            / \
    o   o          o   o
   / \  |         / \  |
  o   o o        o   o o
 / \  | |        |   | | \
o   o o o        o   o o  o

De lo cual se puede calcular que $E[X_{1,4}]=\frac{7}{4}$ utilizando el primer árbol, pero $\frac{3}{2}$ utilizando el segundo.