Árbol recursivo aleatorio

En teoría de probabilidad , un árbol recursivo aleatorio es un árbol con raíz elegido uniformemente al azar entre los árboles recursivos con un número dado de vértices.

En un árbol recursivo con vértices, los vértices están etiquetados con los números de a , y las etiquetas deben decrecer a lo largo de cualquier camino hacia la raíz del árbol. Estos árboles no están ordenados, en el sentido de que no hay un orden diferenciado de los hijos de cada vértice. En un árbol recursivo aleatorio, todos esos árboles tienen la misma probabilidad. ${\estilo de visualización n}$${\estilo de visualización 1}$${\estilo de visualización n}$

Como alternativa, se puede generar un árbol recursivo aleatorio comenzando desde un único vértice, la raíz del árbol, etiquetado como , y luego, para cada etiqueta sucesiva desde hasta, se elige un vértice aleatorio con una etiqueta más pequeña para que sea su padre. Si cada una de las opciones es uniforme e independiente de las otras opciones, el árbol resultante será un árbol recursivo aleatorio. ${\estilo de visualización 1}$${\estilo de visualización 2}$${\estilo de visualización n}$

Con alta probabilidad, el camino más largo desde la raíz hasta la hoja de un árbol recursivo aleatorio de -vértice tiene longitud . ^[1] El número máximo de hijos de cualquier vértice, es decir, grado, en el árbol es, con alta probabilidad, . ^[2] La distancia esperada del ésimo vértice desde la raíz es el ésimo número armónico , de donde se sigue por linealidad de expectativa que la suma de todas las longitudes de camino de raíz a vértice es, con alta probabilidad, . ^[3] El número esperado de hojas del árbol es con varianza , por lo que con alta probabilidad el número de hojas es . ^[4]${\estilo de visualización n}$${\displaystyle e\log n}$${\displaystyle (1\pm o(1))\log _ {2}n}$${\estilo de visualización k}$${\estilo de visualización k}$${\displaystyle (1\pm o(1))n\log n}$${\estilo de visualización n/2}$ ${\estilo de visualización n/12}$${\displaystyle (1\pm o(1))n/2}$

Zhang (2015) enumera varias aplicaciones de árboles recursivos aleatorios para modelar fenómenos que incluyen la propagación de enfermedades, los esquemas piramidales , la evolución de los idiomas y el crecimiento de las redes informáticas. ^[4]