java - 不公平なコインでリストをスキップ

Question

だから私は学校でスキップリストを勉強していて、スキップリストで公平なコインではなく「不公平なコイン」を使うべきかどうかについて簡単に話しました. 0 < p < 1 である p に設定されます (したがって、「裏」の確率は 1 −p になります)。

これについて疑問に思った点がいくつかありますが、このトピックについてはすぐに説明してしまったので、よくわかりません。

1. これを行った場合、スキップ リストの高さ/サイズはどうなりますか? 確率が歪めば、明らかに状況が変わりますよね？任意の n 個の要素が含まれているとします。明らかに、公正なコインを使用した場合とは高さが異なります。

2. 任意のノードをスキップ リストに追加すると、そのノードが受け取るプロモーションの期待数はどのように変化しますか? このシナリオでそうなるかどうかはわかりませんが、話題になりました。

私が実際に理解せずに答えを出すだけの人を探しているわけではありませんが、確率の変化によってどのように影響を受けているかを理解できるように、これらの変化がなぜ起こっているのかを実際に説明していただければ幸いです.

編集: Pat Morin の Open Data Structures book の 99 ページに記載されている方程式とさまざまな確率を比較した後、理解できたと思います。同じ質問で他の人を助けるために、解決策を見つけたらコメントに投稿します。

Answer 1

ここであなたの質問に対する答えを調べることができます: https://en.wikipedia.org/wiki/Skip_list#Description
私はそれらを説明しようとします:
p を要素が次のレベルに昇格する確率とします。

1. 高さはlog _1/p nになります。
   理由:
   最後の行 0 には n 個の要素があります。すべての要素はpの確率で次に高い行に現れるため、行 1 にはn * p要素があります。同じ議論で、行 2 にはn * p ²要素が得られます。ご覧のとおり、n *があります。行xのp ^x要素。
   一番上の行には 1 つの項目があるため、方程式1 = n * p ^xが得られ、これをxについて解くと、x = log _1/p n (公正なコインの場合、 x = log ₂ n ) が得られます。
2. 各要素は、平均して1/(1-p)リストに表示されます。
   理由:
   1 つのリストにのみ表示される可能性は(1 - p)です(昇格の可能性はpです)。
   3 番目ではなく 2 番目のリストに入る可能性はp * (1 - p)です(1 回 [ p ] 昇格し、2 回目のコイントスでは昇格しません [ 1-p ])。
   2 番目だが 3 番目ではないp ² * (1 - p)など
   一般的には、xリストにある場合は
   p ^x-1 * (1-p)です。 要素が現れるリストの期待値については、次のようになります: exp = 1 * (1-p) + 2 * p * (1-p) + 3 * p
   
   ² * (1-p) ...
   = ∑ _i=0 ^∞ (i+1) * p ⁱ * (1-p)
   = (1-p) * ∑ _i=0 ^∞ (1+i) * p ⁱ
   = (1-p) * 1/(1-p) ²
   = 1/(1-p)
   合計を1/(1-p) ²に消去する証明は、https : //en. wikipedia.org/wiki/Geometric_series#Geometric_power_series