Pilha fundível aleatória - altura esperada

Heaps mescláveis ​​aleatórios possuem uma operação "meld", que usamos para definir todas as outras operações, incluindo insert.

A questão é: qual é a altura esperada dessa árvore com nós?$n$

O teorema 1 de Gambin e Malinkowski, Filas de prioridade aleatória fundível (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, pp. 344–349, 1998; PDF ) dá a resposta a esta pergunta com prova. No entanto, não entendo por que podemos escrever:

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

Para mim, a altura da árvore é

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

que posso expandir para:

$$\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]\,.$$

A probabilidade de que a altura máxima de duas subárvores seja igual a pode ser reescrita usando a lei da probabilidade total:$k$

$$\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*}$$

Então, no final, eu recebo:

$$\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*}$$

É aqui que estou preso. Eu posso ver que é mais ou menos igual $\mathbb{P}[h_{Q_L} > h_{Q_R}]$ (No entanto, precisamos no máximo≤$\frac{1}{2}$ ) Mas exceto que nada levando à fórmula desde o início.$\leq \frac{1}{2}$

As alturas das subárvores não parecem independentes para mim.

Obrigado pela ajuda.

$h_Q$não é a altura. É o comprimento de uma caminhada aleatória da raiz em uma árvore binária completa (eles insistem que todas as folhas são "nulas"), então a expressão que elas têm é a coisa certa.

Além disso, você pode evitar a indução. A probabilidade de terminar em uma folha específica de profundidade$d$ é apenas $2^{-d}$. Portanto, a duração esperada da caminhada é

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

qual a entropia de uma distribuição um conjunto de tamanho $|\text{leaves}(Q)|$.