Montón fusionable aleatorio

Los montones fusionables aleatorios tienen una operación "fusión", que luego usamos para definir todas las demás operaciones, incluida la inserción.

La pregunta es, ¿cuál es la altura esperada de ese árbol con $n$ nodos?

El Teorema 1 de Gambin y Malinkowski, Colas de prioridad fusionables aleatorias (Actas de SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, pp. 344–349, 1998; PDF ) da la respuesta a esta pregunta con prueba. Sin embargo, no entiendo por qué podemos escribir:

E [h_{Q}] = \frac{1}{2} ((1 + E [h_{Q_{L}}]) + (1 + E [h_{Q_{R}}])) .

$\mathbb{E} [ h_Q] = \frac{1}{2} ((1 + \mathbb{E}[h_{Q_L}]) + (1 + \mathbb{E}[h_{Q_R}]))\,.$

Para mí la altura del árbol es

h_{Q} = 1 + max {h_{Q_{L}}, h_{Q_{R}}},

$h_Q = 1 + \max\, \{ h_{Q_L}, h_{Q_R}\}\,,$

que puedo ampliar a:

E [h_{Q}] = 1 + E [max {h_{Q_{L}}, h_{Q_{R}}}] = 1 + \sum k P [max {h_{Q_{L}}, h_{Q_{R}}} = k] .

$\mathbb{E} [ h_Q] = 1 + \mathbb{E}[\max \,\{ h_{Q_L}, h_{Q_R}\}] = 1 + \sum k \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k]\,.$

La probabilidad de que el máximo de una altura de dos subárboles sea igual a $k$ puede reescribirse usando la ley de probabilidad total:

\begin{aligned} P [max {h_{Q_{L}}, h_{Q_{R}}} = k] \\ = P [max {h_{Q_{L}}, h_{Q_{R}}} = k ∣ h_{Q_{L}} \leq h_{Q_{R}}] P [h_{Q_{L}} \leq h_{Q_{R}}] \\ + P [max {h_{Q_{L}}, h_{Q_{R}}} = k ∣ h_{Q_{L}} > h_{Q_{R}}] P [h_{Q_{L}} > h_{Q_{R}}] \\ = P [h_{Q_{R}} = k ∣ h_{Q_{L}} \leq h_{Q_{R}}] P [h_{Q_{L}} \leq h_{Q_{R}}] \\ + P [h_{Q_{L}} = k ∣ h_{Q_{L}} > h_{Q_{R}}] P [h_{Q_{L}} > h_{Q_{R}}] . \end{aligned}

$\begin{align*} \hspace{2em}&\hspace{-2em} \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k] \\ &= \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L}\leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\ &\hspace{2em} + \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \\ &= \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\ &\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}]\,. \end{align*}$

Entonces al final obtengo:

\begin{aligned} E [h_{Q}] & = 1 + \sum k {P [h_{Q_{R}} = k ∣ h_{Q_{L}} \leq h_{Q_{R}}] P [h_{Q_{L}} \leq h_{Q_{R}}] \\ + P [h_{Q_{L}} = k ∣ h_{Q_{L}} > h_{Q_{R}}] P [h_{Q_{L}} > h_{Q_{R}}]} . \end{aligned}

$\begin{align*}\mathbb{E} [ h_Q] &= 1 + \sum k \{ \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\ &\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \}\,. \end{align*}$

Aquí es donde estoy atrapado. Puedo ver que es más o menos igual (Sin embargo, necesitamos como máximo ) . Pero excepto que nada conduce a la fórmula desde el principio. $\mathbb{P}[h_{Q_L} > h_{Q_R}]$ $\frac{1}{2}$ $\leq \frac{1}{2}$

Las alturas de los subárboles no me parecen independientes.

Gracias por la ayuda.

algorithm-analysis data-structures randomized-algorithms heaps Mateusz Wyszyński
fuente

En el documento, no es la altura. Es la longitud de una caminata aleatoria desde la raíz en un árbol binario completo (insisten en que cada hoja es "nula"), por lo que la expresión que tienen es la correcta. $h_Q$

Además, puede evitar la inducción. La probabilidad de terminar en una hoja específica de profundidad es solo . Entonces, la longitud esperada de la caminata es $d$ $2^{-d}$

\sum_{ℓ \in leaves (Q)} depth (ℓ) 2^{- depth (ℓ)}

$\sum_{\ell\in \text{leaves}(Q)} \text{depth}(\ell)2^{-\text{depth}(\ell)}$

cuál la entropía de una distribución un conjunto de tamaño. $|\text{leaves}(Q)|$

Louis
fuente

¿Podría explicar con más detalle por qué no tengo que usar la inducción? Estoy de acuerdo con la fórmula para la longitud esperada. Simplemente no veo por qué debería ser O (logn)? ¿Qué quiere decir con entropía de una distribución en cadenas?

Mateusz Wyszyński

Debido a que la entropía de una distribución en un conjunto de tamaño es conocida por ser maximizada por una distribución uniforme, en cuyo caso es .

n

$n$

\log n

$\log n$

Louis

Montón fusionable aleatorio - Altura esperada

Respuestas: