Randomisierter meldepflichtiger Haufen - erwartete Höhe

Randomisierte meldepflichtige Heaps haben eine Operation "Meld", mit der wir dann alle anderen Operationen definieren, einschließlich Einfügen.

Die Frage ist, wie hoch ist die erwartete Höhe dieses Baums mit Knoten?$n$

Satz 1 von Gambin und Malinkowski, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science, Bd. 1521, S. 344–349, 1998; PDF ) gibt die Antwort auf diese Frage mit Beweis. Ich verstehe jedoch nicht, warum wir schreiben können:

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

Für mich ist die Höhe des Baumes

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

was ich erweitern kann:

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

Die Wahrscheinlichkeit, dass das Maximum einer Höhe von zwei Teilbäumen gleich $k$ kann unter Verwendung des Gesetzes der Gesamtwahrscheinlichkeit umgeschrieben werden:

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

Am Ende bekomme ich also:

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

Hier stecke ich fest. Ich kann sehen, dass mehr oder weniger gleich ist (wir brauchen jedoch höchstens ) . Aber außer dass nichts von Anfang an zur Formel führt.$\mathbb{P}[h_{Q_L} > h_{Q_R}]$$\frac{1}{2}$$\leq \frac{1}{2}$

Die Höhen der Teilbäume scheinen für mich nicht unabhängig zu sein.

Danke für die Hilfe.

In der Zeitung ist nicht die Höhe. Es ist die Länge eines zufälligen Weges von der Wurzel in einem vollständigen Binärbaum (sie bestehen darauf, dass jedes Blatt "Null" ist), also ist der Ausdruck, den sie haben, das Richtige.$h_Q$

Sie können auch eine Induktion vermeiden. Die Wahrscheinlichkeit, an einem bestimmten Blatt der Tiefe enden, beträgt nur . Die erwartete Länge des Spaziergangs ist also$d$$2^{-d}$

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

welche die Entropie einer Verteilung eine Menge von Größe.$|\text{leaves}(Q)|$