The computation of the stationary distribution in random-walk-type Markov chains: via unraveling the trinity of stability

随机游走型马尔可夫链中平稳分布的计算：通过解开稳定性三位一体

基本信息

批准号：
21K11770
负责人：
増山博之
金额：
$ 2.75万
依托单位：
Tokyo Metropolitan University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究課題は，ランダム・ウォーク(RW)型マルコフ連鎖における「安定性のトリニティ」，すなわち，安定性に関わる3つの量「増分平衡分布の裾減衰率」「エルゴード収束率」「定常分布裾減衰率」の関係性の解明とその応用を目的としている. この目的の達成に向けて, 代表的なRW型マルコフ連鎖であるM/G/1型，GI/G/1型，Upper Block-Hessenberg (UBH)型マルコフ連鎖などを対象に，エルゴード性に関するドリフト条件とポアソン方程式の解析を行うと共に，その解析結果を用いて, 定常分布に対する高精度な近似計算法や，準アルゴリズム的解構築法(有限手続きの反復により厳密解に収束する構築法)の確立などを目指す．2022年度の研究実績は以下の通りである．小課題①: 漸近的なレベル独立性をもつUBH型マルコフ連鎖を対象とし, 定常分布の劣指数漸近公式を導出すると共に, システム参加の再試行(retrial)や断念(balking)があるマルコフ型待ち行列への応用を示した. また, 一般的なUBH型マルコフ連鎖における定常分布の準アルゴリズム的解構築は, 1反復ごとに1つの分数線形計画問題を解くことを要求するが, 本小課題で導いた劣指数漸近公式の成立条件下では, そうした分数線形計画問題の求解を回避できることを示した.小課題②: 可算状態マルコフ連鎖に関するポアソン方程式について解析を行い, ブロック分解に適した解を「基礎偏差行列」として定義し, その閉じた表現形を導いた. さらに, その結果を用いて, M/G/1型マルコフ連鎖の最終列増大切断近似の劣幾何収束性に関する過去の研究成果を補強し, 国際英文誌での論文採択にこぎつけた.小課題③: M/G/1型マルコフ連鎖のレベル増分切断近似について解析を行い, 誤差の全変動ノルムが劣幾何的に収束するための十分条件と, その条件下での劣幾何収束公式を導いた. また, 幾何収束性についても解析を行い, レベル毎の幾何収束公式を導出した.

该研究主题旨在阐明和应用马尔可夫链中的“稳定性三位一体”之间的关系，即与稳定性相关的三个数量：增量平衡分布的尾阻尼速率，厄基德收敛速率和稳定分布的尾巴降低速率。为了实现这一目标，我们分析了典型RW马尔可夫链的厄法德和泊松方程的漂移条件，m/g/1，gi/g/1和上层盖帽（UBH）马尔可夫链（UBH）马尔可夫链，并使用分析结果，并使用分析结果，我们旨在通过稳态分布和Quasi-Algith方法（Quasi-Algitm-Algith Odeast）进行高度准确的近似方法（Quasi-Algitm-Algitm-Alogith Ondercture）方法（A A A I I构建方法（A）程序）。 2022年的研究结果如下：小任务1：我们为稳定分布提供了一个亚指数渐近公式，并证明了在系统参与重试和balk的Markov排队中的应用。此外，尽管在通用UBH型马尔可夫链中固定分布的准算术解决方案构建需要解决每种迭代的一个分数线性编程问题，但我们表明，衍生在此小任务中的亚指数渐近式套管可以避免解决此类小数线性的线性编程问题。小任务2：我们分析了可数状态马尔可夫链的泊松方程，并定义了适合块分解的解决方案为“基本偏差矩阵”，并得出了其封闭的表型。此外，使用结果，我们先前的研究结果对M/G/1 Markov链的最终柱增长切割近似的下等几何融合得到了增强，并在国际英语期刊中采用了该论文。次要任务3：我们分析了M/G/1 Markov链的水平收入断裂近似，并得出了误差规范的足够条件，以在这些条件下以下几何差异和下几何收敛公式收敛。我们还分析了每个级别的几何收敛公式。

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

An error bound for the level-increment truncation approximation of M/G/1-type Markov chains

M/G/1型马尔可夫链水平增量截断近似的误差界

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Kanzaki Masaaki;Otachi Yota;Uehara Ryuhei;角田　英一郎，八木　祐介，重弘裕二;Katsuhisa Ouchi and Hiroyuki Masuyama
通讯作者：
Katsuhisa Ouchi and Hiroyuki Masuyama

Hiroyuki Masuyama: List of Publications

增山宏之：出版物清单