Der Nachweis von Sprunglisten ist in der Erwartung stark gewichtsausgeglichen

Wie groß ist bei einer Sprungliste mit der Höhe $n$ die erwartete Länge innerhalb eines konstanten (multiplikativen) Faktors?

In Abschnitt 2.2 von Cache-Oblivious B-Trees werden stark gewichtsausgeglichene Suchbäume wie folgt definiert:

Für eine Konstante $d$ , jeder Knoten $v$ in der Höhe $h$ hat $\Theta(d^h)$ Nachkommen.

Sie behaupten:

Suchbäume, die die Eigenschaften 1 und 2 erfüllen, umfassen gewichtsausgeglichene B-Bäume, deterministische Sprunglisten und Sprunglisten im erwarteten Sinne.

Ich habe bereits nach dem Anspruch auf deterministische Sprunglisten gefragt. Diese Frage bezieht sich auf den Anspruch auf Überspringlisten.

Ich glaube, dass Sprunglisten diese Eigenschaft in Erwartung haben, aber ich kann keinen strengen Grund finden. Die Wahrscheinlichkeit umgekehrt (was ist die Höhe angesichts der Länge) kann direkt auf einen konstanten Faktor berechnet werden. Eine differenzierte Analyse finden Sie unter Die Binomialtransformation und die Analyse von Sprunglisten .

Bearbeiten:

Es gibt verschiedene Begriffe zum Definieren von "Nachkommen" in Überspringlisten. Dieser Begriff wird in Pughs Originalarbeit nicht verwendet. Einige mögliche Interpretationen von "Nachkommen" ergeben sich aus der Anzeige von Sprunglisten als Bäume. Verschiedene Möglichkeiten, dies zu tun, sind in enthalten

• Eine Limit-Theorie für zufällige Sprunglisten
• Deterministische Sprunglisten
• Bäume überspringen, eine alternative Datenstruktur zum gleichzeitigen Überspringen von Listen
• Erkundung der Dualität zwischen Überspringlisten und binären Suchbäumen

Unter Verwendung des Begriffs "Deterministische Sprunglisten" denke ich, dass dies eine andere Möglichkeit ist, dieselbe Frage zu stellen:

$n$

$d$

Wie Sie es gefragt haben, ist die Frage nach der erwarteten Länge (angesichts der Höhe) ohne vorherige Verteilung auf die Länge der Zeichenfolge nicht sinnvoll.

$h$$h$$X=X(h)$$h$$2^{-h}$$h$$X$$\mathrm{Geometric}(2^{-h})$$\mathrm{E}(X) = (1-2^{-h})2^h$

Bearbeiten:

$h+1$$h$

Legen Sie bei Ihrer Neuformulierung der Frage fest, wie oft Sie die Münze werfen? Wenn nicht, ist es nicht notwendig, eine Verteilung anzugeben, wenn Sie aufhören, die Münze zu werfen?

$H_i$$i \in \mathbb{N}^+$$\mathbb{N}^+$$Pr[H_i = k] = 2^{-k-1}$$i$$H = \max \{H_i \mid i=1,\dots,N\}$$N \in \mathbb{N}^+$

$Pr[H \geq k \mid N] = 1 - \prod_{i=1}^{N} Pr[H_i < k] = 1 - (1 - 2^{-k})^n$ .

Nun können wir die Wahrscheinlichkeit von bei berechnen : . Die Null der ersten partiellen Ableitung dieses Ausdrucks für befindet sich bei (unter Verwendung von Wolfram Alpha). Beachten Sie, dass ich nicht in der Lage / eifrig genug war zu prüfen, ob dies wirklich ein Maximum ist oder nicht. Wenn dies der Fall ist, ist Maximum-Likelihood-Schätzer für die Sprunglistenlänge bei maximaler Turmhöhe .$H=k$$N$$Pr[H = k \mid N] = Pr[H \geq k \mid N] - Pr[H \geq k + 1 \mid N] = (1-2^{-k-1})^n - (1-2^{-k})^n$$N$$N^*_k = \frac{\ln\left( \frac{\ln(1 - 2^{-k})}{\ln(1 - 2^{-k - 1})}\right) }{ \ln(1 - 2^{-k-1}) - \ln(1 - 2^{-k})}$$N^*_k$$N$$k$

Einige Werte, auf die nächste Ganzzahl gerundet:

k    N^*_k
1    2
2    5
3    11
4    22
5    44
10   1419
20   1.5e6

Das fühlt sich vernünftig an; Vielleicht möchten Sie überprüfen, ob . Ich erwarte, dass die erwartete Höhe einer Sprungliste für feste Länge ein Standardergebnis ist.$\mathbb{E}[k \mid N^*_k] \approx k$

Hat jemand eine gute Idee, wie man ein Asymptotikum für bekommt ? Der Ausdruck, den ich gefunden habe, ist nicht sehr hilfreich.$N^*_k$