Problema de probabilidad de generación aleatoria de árboles

Question

Dada una estructura de árbol con un nodo raíz, éste puede tener cero, uno o dos hijos, todos con la misma probabilidad de 1/3. Los hijos también tienen la misma probabilidad de obtener cero, uno o dos hijos, que es de 1/3. El algoritmo crea el árbol de forma recursiva. ¿Cuál es la probabilidad de que el árbol tenga más de N nodos en total?

Me encontré con esta pregunta después de programar un generador de árboles aleatorios y me dio mucha curiosidad, sería genial si alguien supiera la respuesta.

Answer 1

¡Interesante pregunta! No es una respuesta completa, pero sí una interesante representación del problema que podría dar lugar a soluciones. Demasiado largo para un comentario.

---

Para este análisis, lo único realmente relevante es el número de extremos "vivos" en los que puede crecer el árbol. Empezamos con $1$ final en directo. En cada paso se explora un extremo vivo, sustituyéndolo por 0, 1 ó 2 nuevos extremos vivos. Considere cada número de extremos vivos como un estado $k$ en cada paso tenemos la posibilidad de llegar a un estado con $k-1, k$ o $k+1$ finales en directo. Si llegamos al estado $0$ estamos atrapados allí.

Representemos nuestras posibilidades como un polinomio $f_n(x)$ donde $n$ es el número de pasos, y el coeficiente de $x^k$ nos dice la probabilidad de estar en el estado $k$ después de $n$ pasos. Inicialmente tenemos $f_0(x) = x$ tenemos un 100% de posibilidades de tener $1$ final en directo. Tenga en cuenta que $f_n(0)$ es claramente la probabilidad de alcanzar el estado $0$ después de $n$ pasos.

Lo bueno de esta representación es que $f_{n+1}(x) = \frac{1}{3}(x^{-1} + 1 + x) \cdot (f_{n}(x) - f_{n}(0)) + f_{n}(0)$ anulando fracciones como $x^2 \cdot x^{-1} = x$ (para que luego no dividamos por cero).

Desde $f_n(0)$ es exactamente la posibilidad de que tras $n$ pasos nuestro árbol ya no crece, si queremos saber la probabilidad de que nuestro árbol tenga al menos $n$ nodos simplemente miramos $1 - f_{n-1}(0)$ .

---

Seamos locos, y en lugar de mirar directamente el valor de $f_n(0)$ En su lugar, veamos el límite. También reordenamos un poco los términos:

$$\lim_{x\to 0}\quad f_{n+1}(x) = \frac{1}{3}(1 + x + x^2) \frac{f_{n}(x) - f_{n}(0)}{x} +f_{n}(0)$$

¿No te recuerda a algo?

$$\lim_{x\to 0}\quad f_{n+1}(x) = \frac{1}{3}(1 + x + x^2) f'_n(x) +f_{n}(0)$$ $$f_{n+1}(0) = \frac{1}{3} f'_n(0) +f_{n}(0)$$

Esto parecía muy emocionante hasta que me di cuenta de que $f'_n(0)$ es simplemente el coeficiente de estado $1$ .

Answer 2

Sea $T_n$ es el número de árboles ordenados y enraizados con $n$ nodos, donde cada nodo tiene grado $\le 3.$ Estos son exactamente los $n$ -árboles de nodos que pueden ser generados por el proceso aleatorio. La probabilidad de que un $n$ -se genera el árbol de nodos es $3^{-n},$ de cada nodo se asocia a un factor de $1/3,$ la probabilidad de tener el número de hijos que tiene (o no tiene, en el caso de las hojas.) Por lo tanto, la probabilidad de generar un árbol con exactamente $n$ nodos es $$p_n=3^{-n}T_n.$$

$T_n$ satisface la relación de recurrencia $$T_n = T_{n-1} + \sum_{k=1}^{n-2}{T_kT_{n-1-k}},\tag{1}$$ ya que la raíz puede tener un único subárbol con $n-1$ o dos subárboles, uno con $k$ y uno con $n-k-1$ nodos.

Obsérvese que distinguimos el caso en que el primer subárbol tiene $k$ nodos del caso en que el segundo subárbol tiene $k$ nodos. Esto es lo que lo convierte en un árbol ordenado. No es lo mismo que un árbol binario, ya que cuando sólo hay un subárbol no nos importa si es el subárbol izquierdo o el derecho. De la descripción del proceso aleatorio se deduce claramente que éste es el tipo de árbol que queremos.

Ahora $(1)$ es casi idéntica a la relación de recurrencia para el Números de Motzkin $$M_n = M_{n-1} + \sum_{k=0}^{n-2}{M_kM_{n-2-k}},$$ et $T_1=M_0=1, T_2=M_1=1,$ para que $T_n=M_{n-1},$ et $\boxed{p_n=3^{-n}M_{n-1}}.$

El artículo de Wikipedia enlazado más arriba ofrece una fórmula más conveniente para calcular los números de Motzkin como una recurrencia de tres términos, y una expresión de forma cerrada como una suma que implica coeficientes binomiales y números catalanes.

Usando esta expresión de forma cerrada, pude obtener una fórmula de forma cerrada para la pregunta del OP, para la pregunta del OP, pero no veo cómo simplificarla en algo más útil que calcular el $p_n'$ s individualmente y sumándolos. Por si sirve de algo, $$ Pr(X>M)= 1 - \sum_{n=1}^{M-1}\sum_{k=0}^{\lfloor (n-1)/2\rfloor}{\left[\binom{n-1}{k,k,n-1-2k}-\binom{n-1}{k+1,k-1,n-1-2k}\right]} $$