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

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

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