平成20（2008）年度　重点型研究実施報告書

課題番号	20−共研−4205		分野分類			統計数理研究所内分野分類			f
						主要研究分野分類			2
研究課題名	マルコフ連鎖を用いた多項式時間パーフェクトサンプリング法の開発
重点テーマ	統計科学における乱数
フリガナ 代表者氏名	マツイ　トモミ 松井　知己				ローマ字		Tomomi Matsui
所属機関	中央大学
所属部局	理工学部情報工学科
職　　名	教授
配分経費	研究費	60千円		旅　費		60千円		研究参加者数		4　人

研究目的と成果（経過）の概要

[研究目的の概要]
マルコフ連鎖を用いたサンプリングは、MCMC法（マルコフ連鎖モンテカルロ法）等における重要な問題である。従来のサンプリング法では、初期状態から十分な回数推移させることによりサンプリングを行っているが、その回数の算定は経験に基づくものであることが多い。本研究で対象とする「マルコフ連鎖を用いたパーフェクトサンプリング法」は、目的とする分布を極限分布に持つマルコフ連鎖から、極限分布に「厳密に」従うサンプルを得る手法である。1996年にProppとWilsonによって提案された coupling from the past 法(以下CFTP法)は、マルコフ連鎖の極限分布に厳密に従うサンプリングを可能とする驚くべき手法である。この手法は、無限の過去から推移しているマルコフ連鎖を仮想的に考え、現時点でサンプリングを行うという革新的なアイデアに基づく。現時点の状態を知るために、過去に遡り全状態からの coupling が起こっているか（coalescenceが起こっているか）を確認することから、CFTPという名前がついている。本研究は、積形式解に従う離散分布等を応用に持つ、分離対数凹分布を極限分布として持つマルコフ連鎖の設計と、極限分布に厳密に従うサンプリングを行うCFTP法の設計を目的としている。
[研究成果の概要]
待ち行列ネットワークの基本であるジャクソン型ネットワークは、定常分布関数として積形式解を持つ．しかし閉ジャクソンネットワークの様々な特徴量を計算するには、その分割関数を数値的に計算する必要がある。本研究では、単一サーバからなる閉ジャクソンネットワークについて，その分割関数を計算する FPRAS(全多項式時間乱拓近似解法)の提案を行った。またこれに用いるMCMC法では，サンプリング法として我々の開発したCFTP法を用いている。
またこの解法を拡張することで，複数サーバからなる閉ジャクソンネットワークに対する，FPRASの構築も行った．

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

[査読付論文]
Shuji Kijima and Tomomi Matsui, ``Approximation algorithm and perfect sampler for closed Jackson networks with single servers,'' SIAM Journal on Computing, Volume 38, Issue 4, pp. 1484--1503 (2008).
Shuji Kijima and Tomomi Matsui, ``Randomized Approximation Scheme and Perfect Sampler for Closed Jackson networks with Multiple Servers, '' Annals of Operations Research, 162 (2008), pp. 35--55.

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

研究参加者一覧
氏名	所属機関
来嶋　秀治	京都大学
金野　秀敏	筑波大学
田村　義保	統計数理研究所