En la teoría de la probabilidad , un árbol recursivo aleatorio es un árbol enraizado elegido uniformemente al azar de los árboles recursivos con un número determinado de vértices.
Definición y generación
En un árbol recursivo con vértices, los vértices están etiquetados por los números de a y las etiquetas deben disminuir a lo largo de cualquier camino hasta la raíz del árbol. Estos árboles están desordenados, en el sentido de que no hay un orden distinguido de los hijos de cada vértice. En un árbol recursivo aleatorio, todos esos árboles son igualmente probables.
Alternativamente, se puede generar un árbol recursivo aleatorio partiendo de un único vértice, la raíz del árbol, etiquetado , y luego para cada etiqueta sucesiva de a elegir 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.
Propiedades
Con alta probabilidad, el camino más largo desde la raíz hasta la hoja de un -El á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 delel vértice de la raíz es el th número armónico , del cual se sigue por la linealidad de la expectativa que la suma de todas las longitudes de ruta de raíz a vértice es, con alta probabilidad,. [3] El número esperado de hojas del árbol escon varianza , por lo que con alta probabilidad el número de hojas es . [4]
Aplicaciones
Zhang (2015) enumera varias aplicaciones de árboles recursivos aleatorios en el modelado de fenómenos, incluida la propagación de enfermedades, los esquemas piramidales , la evolución de los lenguajes y el crecimiento de las redes informáticas. [4]
Referencias
- ↑ Pittel, Boris (1994), "Note on the height of random recursive trees and random m -ary search trees", Random Structures & Algorithms , 5 (2): 337–347, doi : 10.1002 / rsa.3240050207 , MR 1262983
- ^ Goh, William; Schmutz, Eric (2002), "Distribución límite para el grado máximo de un árbol recursivo aleatorio", Journal of Computational and Applied Mathematics , 142 (1): 61–82, doi : 10.1016 / S0377-0427 (01) 00460-5 , Señor 1910519
- ^ Dobrow, Robert P .; Fill, James Allen (1999), "Longitud total del camino para árboles recursivos aleatorios", Combinatoria, Probabilidad y Computación , 8 (4): 317–333, doi : 10.1017 / S0963548399003855 , MR 1723646
- ^ a b Zhang, Yazhe (2015), "Sobre el número de hojas en un árbol recursivo aleatorio", Revista Brasileña de Probabilidad y Estadística , 29 (4): 897–908, doi : 10.1214 / 14-BJPS252 , MR 3397399