対数優モジュラ分布からのサンプリング
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,有限分配束上の対数優モジュラ分布に対して,マルコフ連鎖モンテカルロ (MCMC: Markov chain Monte Carlo) 法に基づくランダムサンプリングアルゴリズムを議論する.1996 年 Propp, Wilson の提案した過去からのカップリング (CFTP: coupling from the past) 法は,マルコフ連鎖のシミュレーションを工夫することで,定常分布に厳密に従う完璧サンプリングを実現する.過去からのカップリング法を効率的に実行するには,単調な更新関数の設計が重要な課題である.本稿では有限束上の可逆的酔歩が単調な更新関数を持つための必要十分条件は定常分布が対数優モジュラであることを示す.また,対数優モジュラ分布の応用として,Tutte 多項式の値の計算に対する多項式時間乱択近似計算法についても議論する.
- 2009-11-20
著者
関連論文
- 対数優/劣モジュラ分布からのサンプリング (アルゴリズムと計算機科学の数理的基盤とその応用)
- A polynomial-time perfect sampler for the Q-Ising with local fields (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 頂点独立なノイズ付きQ-イジング模型のための多項式時間パーフェクトサンプラー
- コーダルグラフサンドイッチ問題とその応用
- 対数優モジュラ分布からのサンプリング
- 平成20年春季研究発表会ルポ(情報の窓)
- マルコフ連鎖の完璧シミュレーション(超ロバスト計算原理とモデリング・シミュレーション)
- Enumeration of Graph Sandwiches (Acceleration and Visualization of Computation for Enumeration Problems)
- 一般化メディアン安定結婚問題に対する乱択近似アルゴリズム
- 1-B-3 一般化メディアン安定結婚問題に対する乱択近似アルゴリズム(アルゴリズム)
- マルコフ連鎖モンテカルロ法における近似精度保証と完璧サンプリング法(研究会推薦博士論文速報)
- コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)