redisホップテーブルからの検索時間の複雑さの理解

なぜジャンプ表の平均時間の複雑さがO(logn)なのか、これまでよく分からなかった.
でも後で見て
http://blog.xiaoheshang.info/?p=248は少し理解して、更に自分の思考を結びつけて、記録します
まず、先ほどの記事の「2^i個のノードごとに前の2^i個のノードを指す場合、1個のノードを探す複雑さがlogn(二分検索に似ている)になる」ことを理解する必要があります.これは問題ないはずです.
では問題ですが、なぜランダムな層数でもlognの複雑さを保証できるのでしょうか.
なぜなら、ここで言うランダムは、完全にランダムな1つの層数ではなく、ランダムなアルゴリズムによって、ランダムではない層数を算出するからである.
redisにおけるランダム層数のアルゴリズムから見ると

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

ここではZSKIPLIST_Pは2(実際には4、分かりやすくは2)であり、このコードは、落下層数がi+1の確率が0.5^iであることを理解することができる.
逆に理解すると、2つのノードごとに層数2が現れることが望ましいのは1であり、4つのノードごとに3番目の層が現れることが望ましいのも1であり、8つのノードごとに4番目の層(0.5^3)が現れることが望ましいのは1(期待値=単一確率*数)である.
これに基づいて,我々のデータ量が大きいほど所望の値に近づくことができるので,「2^i個のノードごとに前の2^i個のノードを指す場合」の効果,すなわち,検索の平均複雑度がO(logn)であると考えられる.