マルコフ連鎖を用いた組合せ的対象のランダム生成法および数え上げ

使用马尔可夫链随机生成和枚举组合对象

基本信息

批准号：
04J11479
负责人：
来嶋秀治
金额：
$ 1.79万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-04J11479/
关键词：
マルコフ連鎖モンテカルロ法近似サンプリング法完璧サンプリング法持ち行列ネットワーク多項式時間乱択近似解法多変量離散分布コーダルグラフ待ち行列ネットワーク対数分離凹関数パーフェクトサンプリング分割表

项目摘要

多変量離散分布に対する効率的なランダムサンプリング法の開発に従事した.詳細には高次元単体中の整数格子点上に定義された分布に対して,分布を記述する関数が交互不等式と呼ばれる不等式を満たす場合について,マルコフ連鎖を用いた効率的なランダムサンプリング法を設計した.特に,これまで扱っていた対数分離型の分布の結果を発展させ,一般の分布に対する交互不等式を与え,提案手法の適用範囲を拡張した.この成果をBCMPネットワークに応用した.BCMPネットワークはジャクソンネットワークを一般化した待ち行列ネットワークモデルである.BCMPネットワークはネットワーク中のジョブの均衡分布として積形式解を持つことが知られている.積形式解の正規化定数から,平均滞在客数,平均滞在時間,スループットなどのネットワークの重要な指標を計算することができる.我々は,BCMPネットワークの積形式解が交互不等式を満たすことを示し,高速に収束するマルコフ連鎖,および単調マルコフ連鎖を提案した.これらのマルコフ連鎖を用いて効率的な近似/完壁サンプリング法を提案した.また,コーダルグラフの列挙算法ならびにランダム生成法の研究にも取り組んだ.コーダルグラフは,数値計算,最適化,統計学などの分野で頻出するグラフクラスである.コーダルグラフの全列挙,ならびにランダム生成法は,統計学におけるグラフィカルモデリングにおけるモデル選択支援,MP困難問題である最小コーダルグラフ補完に対する効率的な探索などの応用をもつ.我々は,2つの与えられたグラフに挟まれるコーダルグラフに対して,半順序構造が階層をなすことを示し,効率的な列挙算法を与えた.この結果を利用することで,直ちにコーダルグラフに対するマルコフ基底が得られ,マルコフ連鎖モンテカルロ法に基づくランダム生成法が実現できる.さらに,最小コーダルグラフ補完の局所最適性規準も与えている.

我们参与了用于多元离散分布的有效随机抽样方法的开发。特别是，对于高维单一的整数晶格点上定义的分布，当描述分布的函数满足称为交替不平等的不平等时，我们设计了一种有效的随机抽样方法。特别是，我们开发了对数分布分布的结果，到目前为止，我们已经处理过，使一般分布的交替不平等，并扩展了所提出的方法的范围。我们将此结果应用于BCMP网络。 BCMP网络是概括杰克逊网络的队列网络模型。已知BCMP网络将产品形式解决方案作为网络中工作的平衡分布。从产品形式解决方案的归一化常数中，我们可以计算网络的重要指标，例如平均停留时间，平均住院时间和吞吐量。我们表明，BCMP网络的产品形式解决方案满足交替的不平等，并提出了一个快速收敛的马尔可夫链和单调马尔可夫链。我们提出了使用这些马尔可夫链有效的近似/完整采样方法。我们还研究了编码图和随机生成方法的枚举方法的研究。代码图经常用于数值计算，优化和统计等字段。编码图和随机生成方法的完整枚举为统计图中图形建模中的模型选择提供了支持。它具有诸如有效搜索最小代码图完成之类的应用，这是一个困难的MP问题。我们表明，部分订单结构是夹在两个给定图之间的编码图的层次结构，并且我们还提供了一个有效的枚举方法。通过此结果，我们还可以在此范围内实现Markov，我们可以在Markov中获得Markov的添加方法，我们可以在Markov中获得Markov Monte。最小代码图完成的最佳标准。