2026-03-12T14:47:01Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00102910 2025-01-21T10:38:27Z 1164:2592:7425:7658

多項式時間決定的サンプラーの頂点誤差解析 白髪丈晴 山内由紀子 来嶋秀治 山下雅史 マルコフ連鎖モンテカルロ法 (MCMC 法) とは，マルコフ連鎖をシミュレートすることで所望の分布からサンプリングを行う手法である．本稿ではロータールーターモデル (Propp 機械) など 「ランダムウォークの脱乱択化」 に関する研究を応用し，マルコフ連鎖を模倣する決定的サンプリングアルゴリズムを提案する．そして，決定的サンプリングアルゴリズムと対応するマルコフ連鎖の分布の頂点誤差 (L∞ 距離) の解析を行い，マルコフ連鎖の混交時間に関する上界を与える．この上界を用いて，0-1 ナップサック解，線形順序拡大，マッチングなどの一様分布に急速混交するマルコフ連鎖が知られるいくつかの #P 完全問題に対し，決定的サンプリングアルゴリズムが所望の分布と頂点誤差が ε 以下の分布を，入力と ε-1 の多項式時間で出力する事を示す． 情報処理学会 2014-09-05 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/102910 AN1009593X 研究報告アルゴリズム（AL） 2014-AL-149 4 1 7 https://ipsj.ixsq.nii.ac.jp/record/102910/files/IPSJ-AL14149004.pdf application/pdf 221.9 kB 2016-09-05