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

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

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

[研究目的の概要]
　マルコフ連鎖を用いたサンプリングは、MCMC法(マルコフ連鎖モンテカルロ法)等における重要な問
題である。従来のサンプリング法では、初期状態から十分な回数推移させることによりサンプリングを行
っているが、その回数の算定は経験に基づくものであることが多い。本研究で対象とする「マルコフ連鎖
を用いたパーフェクトサンプリング法」は、目的とする分布を極限分布に持つマルコフ連鎖から、極限分
布に「厳密に」従うサンプルを得る手法である。従来手法では、(予め定めた)有限回の推移の後、サンプリ
ングを行うため、その回数をどれほど多くしても「厳密な」サンプリングは不可能である。1996年にPropp
とWilsonによって提案されたcoupling from the past法(以下CFTP法)は、マルコフ連鎖の極限分布に
厳密に従うサンプリングを可能とする驚くべき手法である。この手法は、無限の過去から推移しているマ
ルコフ連鎖を仮想的に考え、現時点でサンプリングを行うという革新的なアイデアに基づく。現時点の状
態を知るために、過去に遡り全状態からのcouplingが起こっているか(coalescenceが起こっているか)
を確認することから、CFTPという名前がついている。本研究は、積形式解に従う離散分布等を応用に持
つ、分離対数凹分布を極限分布として持つマルコフ連鎖の設計と、極限分布に厳密に従うサンプリングを
行うCFTP法の設計を目的としている。CFTP法を実行する際には、大量の乱数を用いる必要があり、安
定した高速な乱数の発生アルゴリズムの実装が必要となる。
[研究成果の概要]
ゲノム解析等にしばしば用いられる(離散化)ディリクレ分布に対し,推移回数が入力サイズの強多項式
で抑えられる近似サンプリング法の開発を行った。更にCoupling From the Past法(CFTP法)を用いた
厳密サンプリング法の構築に世界で初めて成功している。この厳密サンプリング法についても,推移回数
は入力サイズの強多項式でおさえることができる。この解法について,現在計算機を用いた大掛かりな計
算実験を行っており,理論的な計算時間と,実際の計算時間の比較を行う予定である。

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

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

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