Pensé en este problema hace mucho tiempo, pero no tengo ideas al respecto.
El algoritmo generador es el siguiente. Suponemos que hay nodos discretos numerados de a . Luego, para cada en , hacemos que el padre del ésimo nodo en el árbol sea un nodo aleatorio en . Itere a través de cada en orden para que el resultado sea un árbol aleatorio con el nodo raíz . (Quizás esto no sea lo suficientemente aleatorio, pero esto no importa).
¿Cuál es la profundidad esperada de este árbol?
pr.probability
zhxchen17
fuente
fuente
Respuestas:
Creo que hay un resultado de concentración sobre , pero aún no he completado los detalles.elogn
Podemos obtener un límite superior para la probabilidad de que el nodo tenga antepasados sin incluir 0 . Para cada posible cadena completa de d antepasados distintos de cero ( un 1 , un 2 , . . . , Un d ) , la probabilidad de que la cadena es ( 1n d 0 d (a1,a2,...,ad) . Esto corresponde a1(1a1)(1a2)⋯(1ad)×1n veces un término de(1+11n donde se ordenan los términos. Entonces, un límite superior para esta probabilidad es1(1+12+13+⋯1n−1)d dondeHn-1es eln-1er número armónico1+11n(d!)Hdn−1 Hn−1 n−1 . Hn-1≈log(n-1)+γ. Paradynfijos→∞, la probabilidad de que el nodonesté en profundidadd+1es como máximo1+12+...+1n−1 Hn−1≈log(n−1)+γ d n→∞ n d+1
Mediante la aproximación de Stirling podemos estimar esto como
Para grande , algo mucho más grande que e log n , la base de la exponencial es pequeña, por lo que este límite es pequeño, y podemos usar el límite de unión para decir que la probabilidad de que haya al menos un nodo con d antecesores distintos de cero es pequeño.d elogn d
Ver
Luc Devroye, Omar Fawzi, Nicolas Fraiman. "Propiedades de profundidad de los árboles recursivos aleatorios anexos escalados".
B. Pittel. Nota sobre las alturas de los árboles recursivos aleatorios y los árboles de búsqueda aleatorios aleatorios. Estructuras aleatorias y algoritmos, 5: 337-348, 1994.
El primero afirma que el segundo mostró que la profundidad máxima es con alta probabilidad, y ofrece otra prueba.(e+o(1))logn
fuente
Esta pregunta fue respondida hace varios años, pero, solo por diversión, aquí hay una prueba simple del límite superior. Le damos un límite a la expectativa, luego un límite de cola.
Defina rv como la profundidad del nodo i ∈ { 0 , 1 , ... , n - 1 } . Defina ϕ i = ∑ i j = 0 e d j .di i∈{0,1,…,n−1} ϕi=∑ij=0edj.
lema 1. La profundidad máxima esperada, es como máximo eE[maxidi] .eHn−1
Prueba. La profundidad máxima es a lo sumo . Para finalizar mostramos E [ ln ϕ n - 1 ] ≤ elnϕn−1 .E[lnϕn−1]≤eHn−1
Para cualquier , acondicionamiento en ϕ i - 1 , mediante inspección de ϕ i , E [ ϕ ii≥1 ϕi−1 ϕi
Por inducción se deduce que
Entonces, por la concavidad del logaritmo,
Aquí está el límite de la cola:
lema 2. Arregle cualquier . Entonces Pr [ max i d i ] ≥ ec≥0 es como máximo exp ( - c ) .Pr[maxidi]≥eHn−1+c exp(−c)
Prueba. Mediante la inspección de , y el límite de Markov, la probabilidad en cuestión es como máximo Pr [ ϕ n - 1 ≥ exp ( eϕ
( e - 1 ) Hnorte- O ( 1 ) maxyoreyo≥lnϕt−lnn [EDITAR: habló demasiado pronto]fuente
I have actually thought about the same question (although in a completely different formulation) a few months ago, as well as some close variants.
I don't have a closed form (/ asymptotic) solution for it, but you might find this view useful (are you only looking for upper bound perhaps?).
The process you describe here is a generalization of the Chinese Restaurant Process, where each "table" is a subtree whose root's parent isv0 .
This also gives us a recursion formula for your question.
Denote byh(n) the expected heights of a such tree process with n nodes.
Denote byPn(B)=Πb∈B(b−1)!n! (the probability of distribution B of the nodes into subtrees).
Then the quantity you're looking for,h(n) , is given by:
If you wish to code this recursion, make sure you use the following so it won't go into infinite loop:
WhereBn is the set of all partitions of n identical balls into any number of non-empty bins, and h(1)=1 .
In practice, when I needed this I just used a simple monte-carlo method for estimatingh(n) , as trying to actually compute h by this method is extremely inefficient.
fuente