权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

The purpose of this study is to clarify the relationship between the stability of the steady state distribution and the decay rate of the equilibrium distribution. This goal is achieved in the direction represented by RW type chain M/G/1 type GI/G/1 type Upper Block-Hessenberg (UBH) type chain M/G/1 type GI/G/1 type Upper Block-Hessenberg (UBH) type chain M/G/1 type GI/G/1 type Upper Block-Hessenberg (UBH) type M/G/G/1 type GI/G/G/1 type GI/G/G/The establishment of a quasi-closed loop solution construction method (a construction method for a closed loop solution with limited manual effort) is indicated. The following is the research results for the year 2022. Small problem 1: asymptotic independence of UBH-type chain reaction, stationary distribution of inferior exponent asymptotic formula to derive a common, systematic participation in the trial and balancing of the use of UBH-type chain reaction. The solution construction of quasi-stationary distribution of general UBH type chain problem is proposed. The solution of fractional linear program problem is proposed under the condition that the asymptotic formula of inferior exponent holds. Sub-topic 2: Computable state, linkage, equation, analysis, decomposition, solution, basic deviation, definition, closed expression In addition, the results of this paper are applied to strengthen the previous research results related to the poor geometric convergence of M/G/1 type chain. Small problem ③: M/G/1 type chain of chain and increase of cut off approximate analysis, error of full dynamic range of poor geometric bundle formula under all conditions. In addition, the geometric convergence equation is derived from the geometric convergence equation.

项目成果

期刊论文数量（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

增山宏之：出版物清单