高速な復元抽出の直感的な説明

先日@niamさんと@tsubosakaさんのつぶやきを見てて，確率{p_i}で復元抽出するWalker's alias methodというものを知りました．たまたま，今日，復元抽出する用事があったので，思い出して調べた次第．私も昔同じことをやろうとして，O(log n)でいけるからまぁいいやと思っていたのですが，このアルゴリズムだとO(1)でいけます．

解説はこのあたりのブログを参照．

• 比較的高速な復元抽出アルゴリズム
• 高速に非復元抽出をするアルゴリズムはないだろうか？(2)

さて，私は理解力が足りなくてこのあたりの説明を読んでもなんでこれでいいのかさっぱりわからなかったので，絵に描いて理解しました．確率{p_i}で復元抽出するためには，p_iに比例した面積の図形を壁に貼ってダーツをすればいいのです．{0.1, 0.05, 0.3, 0.1, 0.45}だったとします．するとこんなの．

まさか毎回ダーツ投げさせる訳にもいかないので，randを呼びます．でも，これでは何がうれしいのかわかりません．四角形にしてみましょう．

ちょっとうれしさがわかってきました．rand.nextDouble()の値が，たとえば0.2から0.4の間なら橙にすればよいのです．このおおざっぱな0.2ずつの区間のことをここではブロックとでも読んでおきましょう．ところが，0から0.2の間ならどうでしょう．3色もあります．もっと詰まっていたら．やっぱり2分探索が必要な気がします．そこで，一つのブロックの中に高々2種類しかないような区切り方はできないでしょうか．できます．これができれば1回比較すればよいだけです．ブロックをnこ（ここでは5個）用意すれば可能です．こんな感じ．
randが0から0.2なら，つまり5倍してintにキャスとして0だったら，もう一度0.1以上か否かチェックして，以下なら青，以上なら橙を返せばOK．このブロックを作ってるのがWalker's alias algorithmです．まず，p_iをn倍したものをq_iとします．q_i < 1のものに一つずつブロックを割り当てます．図だと，青赤緑．次に，残った q_i > 1のものはq_i < 1が消費したブロックのあまりにとりあえず詰めていき，1以下になったら新しいブロックに割り当てます．橙は青と赤のあまりに詰めたところで1以下になったので，新しいブロックをもらいました．灰は残りに割り当てて完了．割り当て数はn個，上記の方法なら各ブロックごとに新しいブロックを一つずつしか消費しないので，最大でもn個ブロックがあれば十分なことがわかります．保存すべき情報は，各ブロックごとに境界となっている位置，2種類の色です．片方の色はインデックスと一致させておけばよいので，境界ともう一方の色だけ覚えればよいのでした．

ちょっとあまりに見事な方法だったので記事にしてみました．