本論文ではn-1次元単体中の整数格子点上に定義された対数分離凹分布からのランダムサンプリング法とその応用について議論する.具体的には,マルコフ連鎖モンテカルロ(MCMC)法に基づく近似サンプリング法,完璧サンプリング法,および正規化定数の計算法に対する効率的アルゴリズムの設計と性能解析を行う.さらに,得られた計算法を実際の問題に適用する.

　MCMC法は,サンプリングにマルコフ連鎖を利用するモンテカルロ法であり,数値積分,シミュレーションなどに用いられる.大規模な空間を持つ対象に対して効果的な計算法であり,特にランダムサンプリング自体が困難な問題に対して強力に効果を発揮する.MCMC法を実際に用いる上で,大きな問題となるのがマルコフ連鎖の収束の速さである.すなわち,「マルコフ連鎖を何回推移させれば,定常分布に十分近くなるのか」という問題である.この問題が本論文の主題のひとつである.

　本論文で扱う対数分離凹分布は連続空間中の対数凹分布に素朴に対応する離散分布のひとつである.しかし,数多く存在する連続空間中の対数凹分布に対する算定法を離散的な対数凹分布に直接適用することは困難である.その理由として,連続分布の算定に用いられるスケーリングの技法が離散分布に対しては一般に使えないこと,マルコフ連鎖の推移の方向の自由度が減ることの2点が挙げられる.この点を踏まえ,連続空間を対象とする先行研究のほとんどでは収束の速さをコンダクタンス法に基づいて算定しているのに対し,本研究ではカップリング法に基づく算定を行う.

　本論文ではn-1次元単体中の整数格子点上に定義された対数分離凹分布に対して,2つの新しい"hit-and-run"型のマルコフ連鎖を提案する.1つは効率的な近似サンプリング法を目的とするマルコフ連鎖である.このマルコフ連鎖がO(n2ln(Kε(-1)))時間で収束することを経路カップリング法を用いて示す.ただしKは単体の一辺の長さである.この証明において交互不等式のアイデアを導入し,対数分離凹分布が交互不等式を満たすことを利用する.もう1つは効率的な完璧サンプリング法を目的とするマルコフ連鎖である.このマルコフ連鎖が「単調」であることを示し,単調CFTPアルゴリズムに基づく完璧サンプリング法を実現する.単調性の証明においても交互不等式が証明の鍵となる.さらにこの単調マルコフ連鎖が高速に収束するための条件を提示し,条件を満たす場合にO(n3ln(Kn))時間で収束することを示す.証明においては,新たに提案する特殊な距離を導入した経路カップリング法を用いる.

　本論文のもうひとつの主題はMCMC法の解の近似精度保証と計算時間の議論である.本論文では,n-1次元単体中の整数格子点上に定義された対数分離凹関数の積分法について,MCMC法に基づく乱択近似計算法を与える.提案する計算法は自己帰着性を利用した再帰的なモンテカルロ法で,上述の近似サンプリング法および完璧サンプリングを利用する.提案する乱択近似計算法に関して,以下の2つの技術的な注意点を挙げる.ひとつは従来研究の多くが2分法に基づく再帰を行っているのに対し,本研究ではn分法に基づく再帰を採用する点である.この変更により,近似解の精度保証において注意深い議論が必要となる.もうひとつは得られる近似解の期待値の真の値からの偏りについて議論を行う点である.従来研究では,近似解の期待値の真の値からの偏りについての議論が不十分であり,計算機実験によって大きな偏りが生じる場合があることも確認される.本研究ではこの偏りを小さくするための方法を提案し,得られる近似解の期待値の真の値からの偏りを理論的に算定すると共に,実験的に偏りが小さくなることを示す.この議論により,しばしば実用の場面において現れる,精度の保証された近似解を得るのに必要な計算時間が確保できない場合にも,質の良い近似解を与えることが可能となる.

　本論文ではn-1次元単体中の整数格子点上に定義された対数分離凹分布の例として,待ち行列ネットワークの基本的で重要なモデルのひとつである閉ジャクソンネットワークの積形式解,統計学における基本的な多変量統計データである2行分割表の一様分布および多項超幾何分布,生物情報学の多くの統計的手法において多項分布の共役分布としてしばしば現れる(離散化)Dirichlet分布を取り扱う.これらの問題に対して,効率的な近似サンプリング法,完璧サンプリング法および乱択近似計算法を与える.

　本論文は高次元単体中の整数格子点上に定義された対数分離凹分布からのランダムサンプリング法とその応用について議論している.具体的には,マルコフ連鎖モンテカルロ法に基づく近似サンプリング法,完璧サンプリング法,および正規化定数の計算法に対する効率的アルゴリズムの設計と性能解析を行っている.さらに,得られた計算法を実際の問題に適用している.

　マルコフ連鎖モンテカルロ法は,サンプリングにマルコフ連鎖を利用するモンテカルロ法である.大規模な状態空間を持つ対象に対して効果的な計算法であり,特にランダムサンプリング自体が困難な問題に対しては効果を発揮する.本論文では,高次元単体中の整数格子点上に定義された対数分離凹分布からサンプリングを行うためのマルコフ連鎖を提案し,近似サンプリング法および完璧サンプリングを構築している.

　マルコフ連鎖モンテカルロ法を実際に用いる上で,大きな問題となるのがマルコフ連鎖の収束の速さである.本論文では,経路カップリング法を用いて提案するマルコフ連鎖の混交の速さを算定している.本論文のもうひとつの主題はモンテカルロ法の解の近似精度保証と計算時間の議論である.本論文では,高次元単体中の整数格子点上に定義された対数分離凹関数の積分法について,マルコフ連鎖モンテカルロ法に基づく乱択近似計算法を与えている.提案する計算法は自己帰着性を利用した再帰的なモンテカルロ法で,上述の近似サンプリング法および完璧サンプリングを利用している.提案する乱択近似計算法に関して,以下の2つの技術的な新規性が認められる.ひとつは従来研究の多くが2分法に基づく再帰を行っているのに対し,本研究では多分枝法に基づく再帰を採用し,効率的な積分法を構築している点である.もうひとつは,得られる近似解の期待値の真の値からの偏りについて議論を行っている点である.従来研究では,近似解の期待値の真の値からの偏りについての議論が不十分であり,計算機実験によって大きな偏りが生じる場合があることも確認されている.本研究では,この偏りを小さくするための方法を提案し,偏りの大きさを理論的に算定すると共に,従来手法より偏りが小さくなることを実験的に示している.この議論により,計算時間が十分確保できない場合にも,質の良い解を与えることが可能となる.

　本論文では高次元単体中の整数格子点上に定義された対数分離凹分布の例として,待ち行列ネットワークの基本的で重要なモデルのひとつである閉ジャクソンネットワークの積形式解,統計学における基本的な多変量統計データである2行分割表の一様分布および多項超幾何分布,生物情報学の多くの統計的手法において多項分布の共役分布としてしばしば現れる(離散化)ディリクレ分布を取り扱う.これらの問題に対して,効率的な近似サンプリング法,完璧サンプリング法および乱択近似計算法を与えている.

　本論文は,「マルコフ連鎖モンテカルロ法における近似精度保証と完璧サンプリング法」と題し、第1章「はじめに」,第6章「まとめ」を含め,6章より成る.

　第1章では,本研究の目的,関連する先行研究について論じ,その中で本研究の位置付けを明らかにしている.

　第2章では,本論文で用いる既存の手法について俯瞰している.

　第3章では,高次元単体中の整数格子点上の対数分離凹分布からのサンプリング法を提案している.3.1節において対数分離凹分布の定義を与え,3.2節では近似サンプリング法のためのマルコフ連鎖を提案し,その収束時間を経路カップリング法を用いて算定している.3.3節で完璧サンプリング法のためのマルコフ連鎖を新たに提案し,その単調性を示すことで,効率的な完璧サンプリング法を設計している.さらに,提案するマルコフ連鎖が高速に収束するための十分条件を与えている.

　第4章では,高次元単体中の整数格子点上の対数分離凹関数の積分に対する乱択近似スキームを提案している.4.1節では提案手法の核である再帰構造とモンテカルロ法について,基本的なアイデアについて述べている.4.2節では完璧サンプリング法を用いた場合について,提案手法の精度保証を与えている.4.3節では近似サンプリング法を用いることで高速化を図り,提案手法に対する精密な解析を行っている.4.4節では,近似解の期待値の真の値からの偏りについて議論している.

　第5章では,前節までの結果を実際の問題に適用した結果について述べている.5.1節では待ち行列ネットワークの基本的で重要なモデルのひとつである閉ジャクソンネットワークの積形式解が対数分離凹分布であることを示し,本研究の手法を適用している.5.2節では2元分割表に対して,人工的な対数分離凹分布を設計することで本研究の手法を適用している.5.3節では,離散化ディリクレ分布に対して本研究の手法を適用し,構築されたサンプリング法に関して計算機実験を行い,理論的な性能評価と実際の挙動に関する比較考察を行っている.

　以上を総合するに,本論文は,「高次元単体中の整数格子点上に定義された対数分離凹分布」に着目し,精密な議論を与えるとともに,情報理工学的な応用を複数取り上げ,理論的成果の適用を図っており,数理情報学の分野の発展に大きく寄与するものである.

　よって本論文は,博士(情報理工学)の学位請求論文として合格と認められる.