Ich habe mir einen Vortrag vom MIT über Skip List angesehen. Insgesamt verstehe ich das Material, aber eines. Was ist „mit hoher Wahrscheinlichkeit“? Ich verstehe es wirklich überhaupt nicht. Ich habe die Vorlesungsnotizen gesehen, aber ich habe es immer noch nicht verstanden.
Sie haben es einfach sagte: „Ereignis $ E $ tritt mit hoher Wahrscheinlichkeit (whp) auf, wenn für jedes $ \ alpha \ geq1 $ eine geeignete Auswahl von Konstanten vorliegt, für die $ E $ mit einer Wahrscheinlichkeit von mindestens $ 1 – O (1 / n ^) auftritt \ alpha) $ „.
Etwas von algorithmist.com hat auch nicht geholfen.
Was ist $ \ alpha $ und was ist $ 1 – O (1 / n ^ \ alpha) $? Wenn ich diese Sache nicht verstehe, bin ich verwirrt über die Analyse, warum „Mit hoher Wahrscheinlichkeit kostet jede Suche in einer $ n $ -Element-Sprungliste $ O (\ lg n) $“.
Kommentare
- Beachten Sie, dass randomisierte und probabilistische Algorithmen nicht dasselbe sind .
Antwort
Ein Ereignis tritt mit hoher Wahrscheinlichkeit in Bezug auf einen Parameter $ n $ auf, wenn es mit der Wahrscheinlichkeit $ p_n $ auftritt und $ \ lim_ {n \ to \ infty} p_n = 1 $. Normalerweise ist der Parameter $ n $ aus dem Kontext ersichtlich. In diesem Fall ist es beispielsweise wahrscheinlich die Anzahl der Elemente in der Liste.
Die Definition von „mit hoher Wahrscheinlichkeit“ in den Vorlesungsunterlagen ist noch spezifischer und gibt an, wie schnell $ p_n $ konvergieren soll bis $ 1 $: Ein Ereignis tritt mit hoher Wahrscheinlichkeit auf, wenn es mit der Wahrscheinlichkeit $ p_n \ geq C / n ^ \ alpha $ für einige $ C auftritt, \ alpha > 0 $. Wenn Sie beispielsweise eine Zufallszahl aus $ \ {0, \ ldots, n \} $ auswählen, ist sie mit hoher Wahrscheinlichkeit ungleich Null, da die Wahrscheinlichkeit, dass sie ungleich Null ist, $ 1-1 / (n + 1) beträgt. \ geq 1-1 / n $ (in diesem Fall also $ C = \ alpha = 1 $).
Kommentare
- Das Grenzkriterium ist auch " genannt, fast sicher ". Ich habe gesehen, dass " hohe Wahrscheinlichkeit " hauptsächlich verwendet wird, wenn auf Wahrscheinlichkeiten Bezug genommen wird, die sich einer mit exponentieller Rate nähern.
- Wenn ich siehe " whp " es ist normalerweise gleichbedeutend mit " fast sicher ", und wenn ich es benutze (ohne es zu definieren), ist dies immer die Bedeutung, auf die ich mich beziehe. Aber allgemeiner könnte " whp " bedeuten, dass man sich entweder 1 nähert, sich 1 polynomiell schnell nähert oder sich 1 exponentiell schnell nähert. Wenn Sie es in einem der letzteren Sinne verwenden, müssen Sie es explizit definieren.
- Wirklich, ' würde $ p_n = 1 – \ frac {aufrufen 1} {\ log ^ * n} $ " mit hoher Wahrscheinlichkeit "? 😉 Aber ja: Um sicher zu gehen, definieren Sie auf jeden Fall, was Sie in Ihrem Kontext meinen.
- Was ist eine Standardreferenz (z. B. Lehrbücher), die WHP formal definiert? Ich habe versucht, einen Artikel über WHP in Wikipedia en.wikipedia.org/wiki/With_high_probability zu schreiben, aber er wurde zum Löschen vorgeschlagen, da es keine Quellen gibt Suchen nach Quellen.
- Sie können Standardlehrbücher für Komplexität und Algorithmen überprüfen. Aber selbst wenn Sie eine Referenz finden, verwendet ' nur das spezielle Lehrbuch ' den Begriff. ' ist es wahrscheinlich am besten, es nur explizit als allgemeine Definition ohne einen spezifischen " Beweis ".