過去からのカップリング (coupling from the past)

パーフェクトサンプリングを実現するアルゴリズムの一つ.

Markovモデルと等価な更新関数(update function)を生成する.これは,等確率で発生する有限状態の乱数に対して,Markovモデルの遷移確率と同じ確率で遷移するように,遷移先の状態を決めたもの.例えば,s1からs2へ1/3で遷移するときに,6状態をとる乱数を想定して,状態sで1か2が出た場合はs2へ遷移する.この関数の決め方は一意ではない.

まず,全ての状態について,上記の等確率乱数を一回生成して,遷移させる.このとき,遷移先が一つの状態なら,アルゴリズムを終了して,収束したこの状態のシンボルを出力する.

もしだめなら,先ほどの状態遷移の前の状態を想定し,等確率な状態から始めて,今回と前回の2段階分をたどったときに,一つの状態に到達したなら,そのシンボルを出力.もし駄目なら,さらに前にもどる.

こうして出てきたシンボルは,定常状態の結合確率に従うサンプリングと同じ.

--しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:13:14 (2492d)