![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
パーフェクトサンプリングを実現するアルゴリズムの一つ．
Markovモデルと等価な更新関数(update function)を生成する．これは，等確率で発生する有限状態の乱数に対して，Markovモデルの遷移確率と同じ確率で遷移するように，遷移先の状態を決めたもの．例えば，s1からs2へ1/3で遷移するときに，6状態をとる乱数を想定して，状態sで1か2が出た場合はs2へ遷移する．この関数の決め方は一意ではない．
まず，全ての状態について，上記の等確率乱数を一回生成して，遷移させる．このとき，遷移先が一つの状態なら，アルゴリズムを終了して，収束したこの状態のシンボルを出力する．
もしだめなら，先ほどの状態遷移の前の状態を想定し，等確率な状態から始めて，今回と前回の2段階分をたどったときに，一つの状態に到達したなら，そのシンボルを出力．もし駄目なら，さらに前にもどる．
こうして出てきたシンボルは，定常状態の結合確率に従うサンプリングと同じ．
--しましま
