高速な復元抽出の直感的な説明先日@niamさんと@tsubosakaさんのつぶやきを見てて，確率{pi}で復元抽出するWalker's alias methodというものを知りました．たまたま，今日，復元抽出する用事があったので，思い出して調べた次第．私も昔同じことをやろうとして，O(log n)でいけるからまぁいいやと思っていたのですが，このアルゴリズムだとO(1)でいけます． 解説はこのあたりのブログを参照． 比較的高速な復元抽出アルゴリズム高速に非復元抽出をするアルゴリズムはないだろうか？(2)さて，私は理解力が足りなくてこのあたりの説明を読んでもなんでこれでいいのかさっぱりわからなかったので，絵に描いて理解しました．確率{pi}で復元抽出するためには，piに比例した面積の図形を壁に貼ってダーツをすればいいのです．{0.1, 0.05, 0.3, 0.1, 0.45}だったとします．するとこんなの． まさか毎回
