¿Cuál es la profundidad esperada de un árbol generado aleatoriamente?

19

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).n0n1i{1,,n1}i{0,,i1}i0

¿Cuál es la profundidad esperada de este árbol?

zhxchen17
fuente
Supongo que es root y decir: "Entonces, para cada en , hacemos que el -ésimo nodo principal ...". ¿Derecho? v0i[1,n)i
Sin título
Que has intentado ¿Ha intentado escribir una relación de recurrencia, digamos para que es la profundidad esperada del nodo ? d(i)i
DW
3
Estos objetos se conocen con el nombre de "árbol recursivo aleatorio".
James Martin

Respuestas:

15

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 ( 1nd0d(a1,a2,...,ad) . Esto corresponde a1(1a1)(1a2)(1ad)×1n veces un término de(1+11ndonde se ordenan los términos. Entonces, un límite superior para esta probabilidad es1(1+12+13+1n1)d dondeHn-1es eln-1er número armónico1+11n(d!)Hn1dHn1n1 . Hn-1log(n-1)+γ. Paradynfijos, la probabilidad de que el nodonesté en profundidadd+1es como máximo1+12+...+1n1Hn1log(n1)+γdnnd+1

(logn)dn(d!)(1+o(1))

Mediante la aproximación de Stirling podemos estimar esto como

1n2πd(elognd)d.

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.delognd


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

Douglas Zare
fuente
2
Muy agradable. Para aclarar para otros lectores: como no puede repetir una , el término ( 1 + 1aies solo un límite superior. (1+12++1n1)d
Peter Shor
3

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 .dii{0,1,,n1}ϕi=j=0iedj.

lema 1. La profundidad máxima esperada, es como máximo eE[maxidi] .eHn1

Prueba. La profundidad máxima es a lo sumo . Para finalizar mostramos E [ ln ϕ n - 1 ] elnϕn1 .E[lnϕn1]eHn1

Para cualquier , acondicionamiento en ϕ i - 1 , mediante inspección de ϕ i , E [ ϕ ii1ϕi1ϕi

E[ϕi|ϕi1]=ϕi1+E[edi]=ϕi1+eiϕi1=(1+ei)ϕi1.

Por inducción se deduce que

E[ϕn1]=i=1n1(1+ei)<i=1n1exp(ei)=exp(eHn1).

Entonces, por la concavidad del logaritmo,

E[lnϕn1]lnE[ϕn1]<lnexp(eHn1)=eHn1.       

Aquí está el límite de la cola:

lema 2. Arregle cualquier . Entonces Pr [ max i d i ] ec0 es como máximo exp ( - c ) .Pr[maxidi]eHn1+cexp(c)

Prueba. Mediante la inspección de , y el límite de Markov, la probabilidad en cuestión es como máximo Pr [ ϕ n - 1exp ( eϕ

Pr[ϕnorte-1Exp(miHnorte-1+C)]mi[ϕnorte-1]Exp(miHnorte-1+C).
mi[ϕnorte-1]Exp(miHnorte-1)   

(mi-1)Hnorte-O(1)maxidilnϕtlnn [EDITAR: habló demasiado pronto]

(1o(1))eHn...

Neal Young
fuente
2

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 is v0.

This also gives us a recursion formula for your question.

Denote by h(n) the expected heights of a such tree process with n nodes.

Denote by Pn(B)=ΠbB(b1)!n! (the probability of distribution B of the nodes into subtrees).

Then the quantity you're looking for, h(n), is given by:

h(n)=BBnPn(B)maxbBh(b)

If you wish to code this recursion, make sure you use the following so it won't go into infinite loop:

h(n)=BBn{{n}}Pn(B)maxbBh(b)11n!

Where Bn 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 estimating h(n), as trying to actually compute h by this method is extremely inefficient.

R B
fuente
1
Thanks for the idea! Actually I wrote a monte-carlo program the first time when I met with this problem, but to my surprise the accurate result is so difficult to get.
zhxchen17