¿Probabilidad de una determinada forma de árbol generada aleatoriamente?

Question

Empiezo con un árbol de un nodo. A continuación, elijo repetidamente un nodo al azar y le añado un nodo hijo, deteniéndome cuando hay un cierto número de nodos.

Tratando todos los nodos como equivalentes e ignorando el orden de los hijos de un nodo, me gustaría calcular la probabilidad de producir una determinada forma de árbol.

Por ejemplo, sólo hay una manera de producir el árbol de 1 o 2 nodos, por lo que cada uno de ellos es 100% probable si me detengo en 1 o 2 nodos. Si estoy produciendo un árbol de 3 nodos, entonces podría obtener A->B->C o C<-A->B, cada uno con un 50% de probabilidad dependiendo de cuál de A o B se eligió antes de añadir C. De cualquiera de esos árboles, D podría insertarse en uno de los tres lugares (como hijo de A, B o C), pero algunos de esos resultados son equivalentes:

1. A->B->C
   `->D

2. A->B->C
      `->D

3. A->B->C->D

4. A->B
   |->C
   `->D

5. A->B->D
   `->C

6. A->B
   `->C->D

1, 5 y 6 tienen la misma estructura de árbol, por lo que hay un 50% de posibilidades de producir ese árbol, y un 16,67% de posibilidades de producir cada uno de los otros tres (2, 3, 4).

Answer 1

Hay $(k-1)!$ posibles árboles con $k$ nodos generados por su algoritmo. Ahora calculamos, dada una forma $T=(N,E)$ el número de árboles generados por su algoritmo de forma $T$ .

Primero algunas anotaciones: dada una arista $e=(n_1,n_2)\in E$ denotamos $\#(e)$ el número de aristas del subárbol con raíz $n_2$ más uno.

Definimos inductivamente $g(n)$ el número de manera de generar el sub-árbol de la raíz $n$ .

• Si $n$ es una hoja, entonces $g(n)=1$ .
• Si sólo hay una arista $e=(n,n_1)\in E$ de $n$ entonces $g(n)=g(n_1)$
• De lo contrario, deja que $e_1=(n,n_1);\dots;e_l=(n,n_l)$ sea el conjunto de todas las aristas que salen de $n$ . $$g(n)=\prod_{i=1}^{l-1}{\sum_{j=1}^{i+1} \#(e_j)\choose \#e_{i+1}}.\prod_{i=1}^{l}g(n_i) $$ Intuitivamente, el segundo producto corresponde al número de forma de producir todos los subárboles de forma independiente. Y el primer producto corresponde al número de intercalaciones en dichas producciones.

La probabilidad de generar una forma particular de tamaño $k$ y la raíz $n$ es así: $$ \frac{g(n)}{(k-1)!} $$

En la primera forma que dio

 A->B->C
  `->D

que daría:

$g(C)=g(D)=1$ desde $C$ y $D$ son hojas. $g(B)=g(C)=1$ . Y finalmente $g(A)={3\choose 1}g(D).g(B)=3$ .

Por lo tanto, la probabilidad es $g(A)/((4-1)!)=1/2$ .