¿Cuál es el número esperado de pasos en un camino aleatorio de la hoja a hoja en un árbol binario?

Question

Deje $h \geq 2$ ser un número natural. Considere la posibilidad de un completo árbol binario de altura $h$. Dicen que tomar una caminata aleatoria a partir de la "izquierda" de la hoja. ¿Cuál es el número esperado de pasos antes de que la "derecha" de la hoja es visitado? Hay una conocida forma cerrada para esto? Si no, ¿hay algún superior o inferior de los límites?

Como ejemplo, vamos a $h = 3$. Entonces estamos buscando a la anterior árbol y preguntando cuál es el número esperado de pasos a pie desde el nodo 4 nodo 7 es.

---

Lo que he encontrado:

Denotar $n = 2^h - 1$ a ser el número de nodos en el árbol. Este problema puede ser visto como un sistema de ecuaciones lineales. Deje $x_i$ denotar el número esperado de pasos a pie de nodo $i$ a un nodo $n$. Estamos tratando de encontrar una $x_{(n+1)/2}$ en el sistema $$ \begin{cases} x_1 = 1 + \frac{1}{2}x_2 + \frac{1}{2}x_3 \\ x_i = 1 + \frac{1}{3}x_{\lfloor i/2 \rfloor} + \frac{1}{3}x_{2i} + \frac{1}{3}x_{2i+1} & \text{for } 1 < i < \frac{n+1}{2} \\ x_i = 1 + x_{\lfloor i/2 \rfloor} & \text{for } \frac{n+1}{2} \leq i < n \\ x_n = 0. \end{casos} $$

Me escribió un programa en Python para resolver este sistema. He encontrado los siguientes valores: $$ \begin{array}{c|c} h & \text{expected number of steps} \\ \hline 2 & 4 \\ \hline 3 & 24 \\ \hline 4 & 84 \\ \hline 5 & 240 \\ \hline 6 & 620 \\ \hline 7 & 1512 \\ \hline 8 & 3556 \\ \hline 9 & 8160 \\ \hline 10 & 18396 \end{array} $$ He conectado estos valores en OEIS, pero no fue ninguna coincidencia de la secuencia.

---

Aunque no sé como resolver un valor exacto, me puede proporcionar un límite inferior de $2^{h+1} - 3h - 1$.

Tenga en cuenta que un paseo por el de la izquierda de la hoja a la derecha de la hoja debe pasar a través de la raíz. Por lo tanto, podemos límite inferior el valor deseado por el número esperado de pasos antes de que la raíz es visitado en un paseo aleatorio comenzando desde la izquierda de la hoja. Entonces estamos preguntando cuántos pasos toma al azar a pie de un nodo en el nivel $h$ hasta el nodo raíz en el nivel $1$.

En el nivel $h$, siempre paso a nivel de $h-1$. En el nivel $i$ donde $1 < i < h$, tiene un $\frac{2}{3}$ oportunidad de subirse a un niño en el nivel $i+1$ $\frac{1}{3}$ oportunidad de pisar a los padres en el nivel $i-1$.

Deje $x_i$ denotar el número esperado de pasos de forma aleatoria a pie de nivel $h-i+1$ a nivel 1. Entonces estamos tratando de encontrar a $x_1$ en el sistema de ecuaciones $$ \begin{cases} x_h = 0\\ x_i = 1 + \frac{2}{3}x_{i-1} + \frac{1}{3}x_{i+1} & \text{for } 1 < i < h\\ x_1 = 1 + x_2. \end{casos} $$ Yo reclamo que $x_{i-1} = x_i + 2^i - 3$$1 < i \leq n$. Proceder por inducción. Como el caso del caso, tenemos $x_1 = x_2 + 1 = x_2 + 2^2 - 3$. Para la inducción de la hipótesis, supongamos que $x_{k-1} = x_k + 2^k - 3$. Luego de nuestro paso de inducción, tenemos $$ \begin{align*} x_k &= 1 + \frac{2}{3}x_{k-1} + \frac{1}{3}x_{k+1} \\ &= 1 + \frac{2}{3}\left(x_k + 2^k - 3\right) + \frac{1}{3}x_{k+1} \end{align*} $$ que reorganiza a $x_k = x_{k+1} + 2^{k+1} - 3$, lo que demuestra la demanda.

Entonces tenemos $$ x_1 = \sum_{i=2}^h \left( 2^i - 3 \right) = 2^{h+1} - 3h - 1. $$

Por lo tanto el número esperado de pasos para llegar a la raíz de una hoja es $2^{h+1} - 3h - 1$. Esto le da a nuestro límite inferior.

---

No sé a dónde ir desde aquí. Mirando los números, sospecho que uno podría ser capaz de demostrar una $\Omega(h2^h)$ límite inferior.

Answer 1

En primer lugar, el pie tiene que ir de la hoja a la raíz. Este es un simple paseo aleatorio en la dirección vertical, con una probabilidad de $\frac23$ ir hacia abajo y $\frac13$ ir arriba. El tiempo de espera $a_k$ para llegar a la raíz de la profundidad de $k$ satisface

$$ t_k=1+\frac23t_{k+1}+\frac13t_{k-1} $$

para $k=1,\ldots,h-2$ con condiciones de contorno de la $t_0=0$$t_{h-1}=1+t_{h-2}$. La solución general es $t_k=c_1+c_22^{-k}-3k$. La primera condición de frontera de los rendimientos de $c_2=-c_1$, y luego el segundo de los rendimientos

$$ c_1-c_12^{1-h}-3(h-1)=1+c_1-c_12^{2-h}-3(h-2)\;, $$

con la solución

$$ c_1=2^{h+1}\;. $$

Por lo tanto $t_k=2^{h+1}\left(1-2^{-k}\right)-3k$, lo $t_{h-1}=2^{h+1}-4-3(h-1)=2^{h+1}-3h-1$.

Ahora tenemos que añadir la de veces que se necesita para avanzar hacia el objetivo de la hoja. En la raíz, tenemos la probabilidad de $\frac12$ ir de nuevo a la izquierda, donde nos llevara $t_1=2^{h+1}\left(1-2^{-1}\right)-3\cdot1=2^h-3$ a de volver a la raíz, y la probabilidad de $\frac12$ ir a la derecha, por lo que el tiempo de espera $b_0$ a ir a la derecha satisface

$$ b_0=1+\frac12\left(2^h-3+b_0\right)\;, $$

con la solución de $b_0=2^h-1$. A partir de entonces, en la profundidad de $k$, tenemos la probabilidad de $\frac13$ a progresar y $\frac23$ a desviarnos en una gráfica con $2^h-2-\frac12\left(2^{h-k}-2\right)=2^h-2^{h-k-1}-1$ bordes, de los cuales, $2$ de plomo de la espalda, por lo que el tiempo de retorno en este caso es $2^h-2^{h-k-1}-1$. Por lo tanto el tiempo de espera $b_k$ a progresar satisface

$$ b_k=\frac23\left(2^h-2^{h-k-1}-1+b_k\right)+\frac13\cdot1\;, $$

así

$$ b_k=2^{h+1}-2^{h-k}-1\;. $$

Tenga en cuenta que esto también cubre $b_0=2^{h+1}-2^{h-0}-1=2^h-1$. Suma más de $k$ $0$ $h-2$los rendimientos de una contribución

$$ \sum_{k=0}^{h-2}\left(2^{h+1}-2^{h-k}-1\right)=\left(2^{h+1}-1\right)h-2^{h+2}+5\;, $$

para un total de

\begin{align} 2^{h+1}-3h-1+\left(2^{h+1}-1\right)h-2^{h+2}+5 &=2^{h+1}h-2^{h+1}-4h+4\\ &=4(h-1)\left(2^{h-1}-1\right). \end{align}

P. S.: tenga en cuenta que esta realidad contiene todo lo que necesitas para calcular el número esperado de pasos desde cualquier nodo a otro nodo. Si el nodo inicial es en la profundidad de $a$, el nodo final es en la profundidad de $b$ y su antecesor común más bajo es en la profundidad de $c$, entonces toma

$$2^{h-c+1}\left(1-2^{c-a}\right)+3(c-a)=2^{h-c+1}-2^{h-a+1}+3(c-a)$$

pasos para alcanzar el ancestro común y

$$ \sum_{k=c}^{b-1}\left(2^{h+1}-2^{h-k}-1\right)=2^{h-b+1}-2^{h-c+1}+(b-c)\left(2^{h+1}-1\right) $$

pasos para alcanzar el nodo final, para un total de

$$ \left(2^{b}-2^{-a}\right)2^{h+1}+(b-c)\left(2^{h+1}-1\right)+3(c-a)\;. $$

En el caso de que estés interesado en se $c=0$$a=b=h-1$.