スキップリストに関するMITからの講義を見ました。全体的に、私は資料を理解していますが、1つだけです。 「高確率」とは？まったくわかりません。講義ノートを見ましたが、まだわかりませんでした。
ただ「イベント$ E $は、任意の$ \ alpha \ geq1 $に対して、少なくとも$ 1 − O（1 / n ^）の確率で$ E $が発生する定数の適切な選択がある場合、高い確率（whp）で発生します。 \ alpha）$ “。
algorithmist.com の何かも役に立ちませんでした。
とは$ \ alpha $と$ 1 − O（1 / n ^ \ alpha）$とは何ですか？このことを理解していないと、「高い確率で、$ n $要素のスキップリスト内のすべての検索に$ O（\ lg n）$がかかる」理由の分析に混乱します。
コメント
- ランダム化された確率的アルゴリズムは同じものではないことに注意してください。
回答
イベントが確率$ p_n $で発生した場合、パラメーター$ n $に関して高い確率で発生します。および$ \ lim_ {n \ to \ infty} p_n = 1 $。通常、パラメータ$ n $はコンテキストから明らかです。この場合、たとえば、リスト内の要素の数である可能性があります。
講義ノートの「確率が高い」の定義はさらに具体的で、$ p_n $が収束する速度を指定します。 $ 1 $へ：ある$ C、\ alpha > 0 $に対して、確率$ p_n \ geq C / n ^ \ alpha $で発生した場合、イベントは高い確率で発生します。たとえば、$ \ {0、\ ldots、n \} $から乱数を選択した場合、ゼロ以外の確率は$ 1-1 /（n + 1）であるため、ゼロ以外の確率が高くなります。 \ geq 1-1 / n $（したがって、この場合は$ C = \ alpha = 1 $）。
コメント
- 制限基準は"ほぼ確実に"とも呼ばれます。 "高い確率"は、指数関数的に近づく確率を指すときに主に使用されます。
- 私が" whp "を参照してください。通常は"とほぼ確実に同義です"、そして私がそれを（それを定義せずに）使用するとき、これは常に私が参照する意味です。しかし、より一般的には、" whp "は、1に近づく、1に近づく、または1に指数関数的に近づくことを意味します。後者の意味で使用する場合は、必ず明示的に定義してください。
- 実際には、'は$ p_n = 1- \ frac {を呼び出します。 1} {\ log ^ * n} $ "高い確率で"？ ;）しかし、そうです。安全のために、どのような場合でも、コンテキストでの意味を定義してください。
- WHPを正式に定義する標準リファレンス（教科書など）とは何ですか？ウィキペディア en.wikipedia.org/wiki/With_high_probability にWHPに関する記事を書こうとしましたが、ソースがないため削除が提案されたので、ソースを探しています。
- 標準の複雑さとアルゴリズムの教科書を確認できます。ただし、参照が見つかった場合でも、その'はその特定の教科書'での用語の使用法のみです。 '特定の"証明"。