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

点击翻译按钮获取中文摘要

本研究課題は，ランダム・ウォーク(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型マルコフ連鎖のレベル増分切断近似について解析を行い, 誤差の全変動ノルムが劣幾何的に収束するための十分条件と, その条件下での劣幾何収束公式を導いた. また, 幾何収束性についても解析を行い, レベル毎の幾何収束公式を導出した.