マルコフ連鎖の脱乱択化：決定性近似アルゴリズム設計に対する新しい汎用手法の開発

点击翻译按钮获取中文摘要

本年度はマルコフ連鎖の脱乱択化研究のなかで, 全訪問時間研究において顕著な成果をあげることに成功した.これまで行ってきた研究は, 各時刻ごとのトークン配置の誤差解析であり, 即ちマルコフ連鎖(確率過程)とそれに類似する決定性過程の``空間平均''の誤差解析であった. 本年度はこの空間平均にあたるトークン分布の誤差解析を, ``時間平均''の誤差解析へ拡張することに成功した. 具体的には, 確率過程, 決定性過程のトークンがある頂点を訪問した回数(訪問頻度)の誤差の上界の導出に成功した. 既存研究でも時間平均にあたる訪問頻度の誤差解析は行われていたが, グラフ上の1トークン単純ランダムウォークに対応するものにとどまっており, 一般の可逆な遷移確率かつ複数トークンまで拡張に成功した本研究の意義は大きい.特に, 訪問頻度の解析手法を用いることで, 一般の遷移確率を持つマルコフ連鎖に類似する決定性過程の, 全訪問時間の上界を得ることに成功した. これは一般の遷移確率に対する初の全訪問時間の上界であり, 本年度にこの成果をまとめ, 国際会議に採択され発表済みである. 更に, 本成果は既存の複数トークン単純ランダムウォークに対応する決定性過程のものを改善している.全訪問時間解析を更に洗練させることにも成功しつつあり, 特定の構造上ではあるが, 遷移確率を工夫することによるランダムウォークの高速化アルゴリズムに習い, それを模倣する決定性過程の全訪問時間が通常の単純なものよりも高速化出来ることを示しており, 29年度, 国際会議に投稿予定である.このように, 本年度の研究でこれまで行ってきた空間平均の解析と時間平均の解析が研ぎ澄まされ, MCMC法の脱乱択化へ大きな進歩が見られた.