* 過去からのカップリング (coupling from the past) [#q5cf7d33]

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

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

> --しましま

**関連項目 [#gf723a01]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.

-[[coupling from the past]]
#br
-[[Markovモデル]]
-[[MCMC]]
#br
-[[検索:過去からのカップリング]]

**リンク集 [#c85ce73b]

//関連するWWW資源があればリンクしてください.

-[[CFTP を用いた Perfect Sampling>http://homepage2.nifty.com/TOMOMI/TRs/SMAPIP-final.pdf]] @ 松井知己 & 来嶋秀治

**関連文献 [#mad248c5]

//この%項目%に関連する書籍や論文を紹介してください.
-過去からのカップリングの基本文献~
J.Propp and D.Wilson "Exact sampling with coupled Markov chains and applications to statistical mechanics" Random Structures Algorithms, vol.9, pp.223-252 (1996)~
[[GoogleScholarAll:Exact sampling with coupled Markov chains and applications to statistical mechanics]]
-チュートリアル~
[[来嶋秀治, 松井知己 "完璧にサンプリングしよう!",オペレーションズ・リサーチ, vol.50, no.3〜5 (2005) の3回連載>http://www.orsj.or.jp/~archive/menu/03_50.html#vol3]]
-[[Book/Information Theory, Inference, and Learning Algorithms]] 32.2節

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS