Der Nachweis von Sprunglisten ist in der Erwartung stark gewichtsausgeglichen

8

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 Θ(dh) 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

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

n

d

jbapple
quelle
1
n1n
Ich denke, ich verstehe, was du meinst, Raphael - im Kontext der ursprünglichen Definition von stark gewichtsausgeglichen ist die Überspringliste "Höhe" keine Baum "Höhe". Ich interessiere mich wirklich für beides, obwohl meine Frage die Turmhöhe sein sollte.
jbapple
1
P(h(x)=n|l(x)=j)=P(h(x)n|l(x)=j)P(h(x)n|l(x)=j)
Natürlich, Raphael, danke. Jetzt bearbeiten.
jbapple
2
Wenn Sie Ihre neu formulierte Frage "Wenn ich eine faire Münze nehme [...]" beantworten, erhalten Sie bei mathoverflow möglicherweise eine vernünftige Antwort, wenn Sie hier nichts erhalten. Wenn Sie dort posten, setzen Sie bitte auch hier einen Link.
Raphael

Antworten:

3

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.

hhX=X(h)h2hhXGeometric(2h)E(X)=(12h)2h

Bearbeiten:

h+1h

James King
quelle
"Sie sollten stattdessen berücksichtigen, wie oft Sie Schwänze erhalten, bevor Sie h Köpfe hintereinander erhalten, da dies Ihnen die Anzahl der Nachkommen eines Knotens der Höhe h in einer Überspringliste gibt." Können Sie das genauer erklären? Es gibt verschiedene Übersetzungen von Sprunglisten in Bäume, und sie geben verschiedenen Knoten unterschiedliche Nachkommen. Ich werde die Frage bearbeiten, um genauer zu sein.
jbapple
OK, ich habe einige Informationen über mögliche unterschiedliche Bedeutungen von "Nachkommen" hinzugefügt. Ich vermute, Ihre Interpretation stimmt mit der von mindestens zwei anderen überein.
jbapple
hihj>iij
2

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?

VPatel
quelle
Nein, ich lege nicht fest, wie oft ich die Münze wirf. Vielleicht ist es notwendig, eine Verteilung zu geben, aber ich bin nicht sicher. Ist meine Übersetzung des Problems falsch? Hat die ursprüngliche Formulierung eine genau definierte Antwort, ohne eine Verteilung festzulegen?
jbapple
Ich denke, die (neu formulierte) Frage macht ohne zusätzliche Informationen keinen Sinn. Ich weiß wirklich nichts über die ursprüngliche Frage, daher kann ich die Übersetzung nicht kommentieren.
VPatel
1

HiiN+N+Pr[Hi=k]=2k1iH=max{Hii=1,,N}NN+

Pr[HkN]=1i=1NPr[Hi<k]=1(12k)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=kNPr[H=kN]=Pr[HkN]Pr[Hk+1N]=(12k1)n(12k)nNNk=ln(ln(12k)ln(12k1))ln(12k1)ln(12k)NkNk

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.E[kNk]k

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

Raphael
quelle