マルコフ連鎖における定常分布の不等式系に基づく数値計算法と待ち行列モデルへの応用

基于马尔可夫链平稳分布不等式系统的数值计算方法及其在排队模型中的应用

• 批准号: 19K11841
• 负责人: 滝根 哲哉
• 金额: $ 2.75万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11841/
• 关键词: マルコフ連鎖; 条件付き定常分布; 不等式系; 数値計算法; 待ち行列モデル; 定常分布

本研究の目的は、可算無限集合上で定義されるマルコフ連鎖の条件付き定常分布に対する新たな数値計算法を開発し、従来の行列解析法が適用できない各種待ち行列モデルの性能評価へ応用することである。従来の研究とは異なり、本研究では、条件付き定常分布を線形不等式系の解として特徴づける、すなわち、N次元ベクトルとして与えられる条件付き定常分布を相対的内部に含む凸多面体を同定し、それに基づく数値計算法を開発する。さらに、開発した数値計算法を基礎として、従来の行列解析法では取り扱うことができなかった各種待ち行列モデルに対して、それらに固有の構造を活用した数値的解法を確立を目指している。本年度は従来の標準的な手法では数値結果を得ることが困難な、状態爆発を起こす準出生死滅過程を対象に、不等式系に基づく接近法から得られる知見を整理した上で、幾つかの数値計算手法を考案し、数値実験を行った。その結果、不等式系に基づく接近法では推移律行列を構成する対角ブロック行列の逆行列に関する情報が不可欠であることから、状態爆発を起こす準出生死滅過程では常にこの部分の計算がボトルネックになることが確認された。この問題を回避するために、状態集約が可能なモデルに焦点を絞り、集約された状態空間上での平衡方程式に対して不等式系に基づく接近法を適用するという方針をたて、現在、チケット待ち行列と呼ばれるモデル群における小規模モデルに対する数値計算実験を繰り返しながら適用可能性を探っている。

The purpose of this study is to develop a new method for calculating the value of a computable infinite set, and to apply the new method to the performance evaluation of a computable infinite set. In this paper, we develop a method for calculating the linear inequality system with the condition of stationary distribution and the interior convex polyhedron with the condition of stationary distribution. The method of calculating the number of columns and columns is based on the method of calculating the number of columns and columns and the method of calculating the number of columns and columns is based on the method of calculating the number of columns and columns. This year's standard method of calculating numerical values is to examine the results of numerical values, to determine the state of the problem, to determine the process of life and death, to determine the inequality system, to determine the approximation method, and to determine the numerical values of numerical values. The result is that the inequality system is based on the approximation method, and the transition law is formed. The information is not required, and the state explosion is initiated. The calculation of the normal part is confirmed. The problem is avoided and the state is concentrated. The equilibrium equation in the state space is related to the inequality system. The approximation method is applied. The policy is related to the small scale problem. The calculation of the value is related to the small scale problem.

项目成果

NUMERICAL IMPLEMENTATION OF THE AUGMENTED TRUNCATION APPROXIMATION TO SINGLE-SERVER QUEUES WITH LEVEL-DEPENDENT ARRIVALS AND DISASTERS

• DOI: 10.15807/jorsj.64.61
• 发表时间: 2021-04
• 期刊: Journal of the Operations Research Society of Japan
• 作者: Masatoshi Kimura;T. Takine

On level-dependent QBD processes with explosive state space

具有爆炸状态空间的水平相关 QBD 过程

• DOI: 10.1007/s11134-022-09796-1
• 发表时间: 2022
• 期刊: Queueing Systems
• 影响因子: 1.2
• 作者: 車塚 彩菜;矢島 萌子;三好 直人;三好 直人;三好 直人;豊泉 洋，三好 直人;T. Takine
• 通讯作者: T. Takine

Characterization of the conditional stationary distribution in Markov chains via systems of linear inequalities

通过线性不等式系统表征马尔可夫链中的条件平稳分布

• DOI: 10.1017/apr.2020.40
• 发表时间: 2020
• 期刊: Advances in Applied Probability
• 影响因子: 1.2
• 作者: 車塚 彩菜;矢島 萌子;三好 直人;三好 直人;三好 直人;豊泉 洋，三好 直人;T. Takine;Masatoshi Kimura and Tetsuya Takine;Masatoshi Kimura and Tetsuya Takine
• 通讯作者: Masatoshi Kimura and Tetsuya Takine