numerical method for Markov chainとは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

マルコフ連鎖の数値解法

読み方：まるこふれんさのすうちかいほう
【英】：numerical method for Markov chain

概要

マルコフ連鎖の定常分布や過渡的分布を数値的に計算するための方法. 定常分布の計算は線形方程式系を解く問題に帰着され, 解法として消去法や状態縮約法などの直接法, ヤコビ法, ガウス・ザイデル法, 状態縮約/非縮約法などの反復法がある. また, 構造化されたマルコフ連鎖に対しては行列幾何形式解を利用する方法も有力である. 一方, 過渡的分布に対しては, 離散時間ではべき乗法, 連続時間ではランダム化を利用する方法などがある.

詳説

　マルコフ連鎖をマルコフ連鎖の数値的に解析する際の中心的な対象は定常分布である. 有限状態空間 ${\mathcal S}=\{ 1, 2, \ldots, N \}\,$ 上の既約で非周期的な (つまりエルゴード的) マルコフ連鎖を考え, その推移確率行列を $\boldsymbol{P}=(p_{ij})\,$ , 定常分布を $\boldsymbol{\pi}=(\pi_1, \pi_2,\ldots,\pi_N)\,$ とする. 一様化により, 連続時間マルコフ連鎖の定常分布は, 離散時間マルコフ連鎖の定常分布として計算できるので, 以下では離散時間マルコフ連鎖に限定して考える.

　エルゴード的なマルコフ連鎖では, 定常分布は

(平衡方程式)	$\pi_j = \sum_{i=1}^N \pi_i p_{ij}, \quad j=1, 2, \ldots,N, \qquad \,$	$(1)\,$
(正規化条件)	$\sum_{j=1}^N \pi_j = 1 \,$	$(2)\,$

を満たす一意の解として与えられる (式(1)) の解は定数倍に関して一意でないため, 式 (2) で正規化する). したがって, 定常分布の計算は, 原理的には線形方程式系を数値的に解く問題に帰着される. 状態数 $N\,$ が大きくなければ, 消去法や状態縮約法などの直接法 (反復計算を伴わない方法) でも解を求めることは可能だが, 一般にマルコフ連鎖によるモデル化はモデルが複雑になるに従って状態数が急激に増加する傾向があるため, そのような場合は計算精度などを考慮して反復法を用いることが多い.

ガウス・ザイデル法　反復法では, 反復回数 $k \to \infty\,$ のときに定常分布 $\boldsymbol{\pi}\,$ に収束するような近似値の列 $\boldsymbol{\pi}^{(k)} = (\pi_1^{(k)}, \pi_2^{(k)}, \ldots,\pi_N^{(k)})\,$ を構成する. 例えば, ヤコビ法 (Jacobi method) では, 適当な初期分布 $\boldsymbol{\pi}^{(0)}\,$ からスタートして

$\pi_j^{(k)} = \sum_{i=1}^N \pi_i^{(k-1)} p_{ij}, \quad j=1, 2, \ldots,N$

によって分布列 $\boldsymbol{\pi}^{(k)}\,$ を構成し, $\boldsymbol{\pi}^{(k-1)}\,$ と $\boldsymbol{\pi}^{(k)}\,$ が十分近くなった時点で収束したと判断する. エルゴード的なマルコフ連鎖に対しては, ヤコビ法は計算誤差を除けば必ず収束するが, 一般に大きな $N\,$ に対してはあまり収束は速くない. これに対して, ガウス・ザイデル法 (Gauss-Seidel method) では

$\pi_j^{(k)} = \frac{ \sum_{i=1}^{j-1} \pi_i^{(k)} p_{ij} + \sum_{i=j+1}^{N} \pi_i^{(k-1)} p_{ij} }{1-p_{jj}}, \quad j=1, 2, \ldots,N$

によって分布列を構成する. この方法では, $k\,$ 回目の反復で既に更新されている値を逐次利用するため, ヤコビ反復法に比べると一般に収束が速くなることが多い. また, 推移確率行列がブロック構造を持つ場合には, ブロックごとに更新された値を利用するブロックガウス・ザイデル法 (block Gauss-Seidel method) も有効である. さらに収束を加速する手段として過剰緩和法 (overrelaxation method) の利用がある. 過剰緩和法では, 緩和 (または加速) 係数を $\omega\,$ として

$\pi_j^{(k)} = \frac{ \omega \sum_{i=1}^{j-1} \pi_i^{(k)} p_{ij} + (1-\omega) \pi_j^{(k-1)} p_{jj} + \omega \sum_{i=j+1}^{N} \pi_i^{(k-1)} p_{ij} }{1-p_{jj}}, \quad j=1, 2, \ldots,N$

によって $\boldsymbol{\pi}^{(k)}\,$ を計算する. $\omega>1\,$ のときには, 外挿により $\boldsymbol{\pi}^{(k-1)}\,$ から $\boldsymbol{\pi}^{(k)}\,$ を計算しており, 適切な $\omega\,$ を選ぶことで収束を加速することが可能となる. なお, ガウス・ザイデル系の方法では, 初期分布 $\boldsymbol{\pi}^{(0)}\,$ が (2) を満たしていても, 途中の計算でこの制約が満たされなくなるため, 計算の最後に (2) が満たされるよう正規化することが必要である.

状態縮約/非縮約法　一方, 複数の状態をまとめて 1つの状態と見なした状態数の少ない確率過程に対して反復計算を行う方法に状態縮約/非縮約法 (aggregation/disaggregation method: AD法) がある. 例えば, 状態空間を $L\,$ 個の部分空間 ${\mathcal S}_1, \ldots, {\mathcal S}_L\,$ に分割し, ${\mathcal S}_{\alpha}\,$ には $d_\alpha\,$ 個の状態 $(\alpha,1), \ldots, (\alpha,d_\alpha)\,$ が含まれる場合を考え, 推移確率を $\boldsymbol{P}=( p_{(\alpha,i)(\beta,j)} )\,$ , 状態 $(\alpha,i)\,$ の定常確率を $\pi_{\alpha,i}\,$ , 部分空間 ${\mathcal S}_\alpha\,$ の定常確率を $\textstyle \tau_\alpha=\sum_{i=1}^{d_\alpha} \pi_{\alpha,i}\,$ とする. いま, $k-1\,$ 回の反復で近似値 $\pi_{\alpha,i}^{(k-1)}\,$ , $\tau_\alpha^{(k-1)}\,$ が求められているとしよう. $k\,$ 回目の反復計算のうち, まず縮約フェーズでは, 部分空間 ${\mathcal S}_\alpha,\; \alpha = 1,\ldots,L\,$ をそれぞれ 1つの状態 $s_\alpha\,$ に縮約した $L\,$ 状態の確率過程を考え, それをマルコフ連鎖と見なして (特殊なケースを除いて縮約した確率過程はマルコフ連鎖とならない) 推移確率, 例えば $s_\alpha\,$ から $s_\beta\,$ への推移確率を $\textstyle q_{\alpha,\beta}^{(k)}=\sum_{i=1}^{d_\alpha} \sum_{j=1}^{d_\beta}\pi_{\alpha,i}^{(k-1)} p_{(\alpha,i)(\beta,j)} / \tau_\alpha^{(k-1)}\,$ によって定める. このマルコフ連鎖 $\boldsymbol{Q}^{(k)}=(q_{\alpha,\beta}^{(k)})\,$ の平衡方程式を解いて, 更新された定常確率 $\tau_\alpha^{(k)},\; \alpha=1,\ldots,L\,$ を求める. 次に非縮約フェーズでは, 1つの着目した部分空間はそのままで他のすべての部分空間を1つの状態に縮約した確率過程を近似的にマルコフ連鎖と考える. 例えば, 部分空間 ${\mathcal S}_\alpha\,$ に注目した場合には, ${\mathcal S}_\alpha\,$ 内の推移確率は元のままで, ${\mathcal S}_\alpha\,$ 内の状態 $(\alpha,i)\,$ から縮約された状態への推移確率は $\textstyle \sum_{\beta \ne \alpha}\sum_{j=1}^{d_\beta} p_{(\alpha,i)(\beta,j)}\,$ , 逆に縮約された状態から $(\alpha,i)\,$ への推移確率は $\textstyle \sum_{\beta \ne \alpha} \sum_{j=1}^{d_\beta}\pi_{\beta,j}^{(k-1)} p_{(\beta,j)(\alpha,i)}/(1-\tau_{\alpha}^{(k)})\,$ で与えられるマルコフ連鎖を考え, その定常分布を計算し $\pi_{\alpha,i}^{(k)}, \; i=1,\cdots,d_\alpha\,$ を得る. この計算を, 注目する部分空間を ${\mathcal S}_1\,$ から ${\mathcal S}_L\,$ まで変えながら行えば, 更新された定常確率を求めることができる. この縮約/非縮約の手続きを, 値が収束するまで反復すればよい.

無限状態と過渡的分布　状態数が無限のマルコフ連鎖に対しては, 状態空間を適当な有限サイズで打ち切って数値計算を行うが, 打ち切るサイズによって計算時間と計算精度の間にトレードオフが生じるので注意が必要である. 構造が入っている場合 (後述) は, 上の方法を用いるにしてもその構造をうまく利用することによって, 少ない計算量で精度良い解が計算できることが多い.

　定常分布に比べると, 過渡的分布 (各時点における推移確率) の計算方法はそれほど多くないが, 離散時間マルコフ連鎖に対してはべき乗法, 連続時間マルコフ連鎖に対してはランダム化を利用する方法などが知られている.

構造化されたマルコフ連鎖　確率モデル, 特に待ち行列モデルから派生するマルコフ連鎖には, 何らかの構造を持つものが多いため, その構造を利用した数値計算法が開発されている. 代表例として, 相型待ち行列に対する行列幾何形式解を考えよう. 到着過程やサービス過程}にマルコフ型到着過程や相型分布を導入することで, 広い範囲の待ち行列モデルは準出生死滅過程 (quasi-birth-and-death process) を含むGI/M/1型, あるいはM/G/1型マルコフ過程などの構造化されたマルコフ連鎖で表現することができる. このうち, GI/M/1型マルコフ連鎖は, レベル $n\; (=0,1,\ldots)\,$ と相 $i\;(=1,\ldots,d)\,$ の組 $(n,i)\,$ によって状態が表されるマルコフ連鎖で, 1回の推移では高々 1つ上のレベルまでしか推移せず, またレベル $n\,$ の状態からレベル $m\; (m\le n+1)\,$ の状態への推移確率 (または推移速度) がレベルの差 $m-n\,$ と各状態の相によって決まる性質を持っている. レベル $n\,$ の状態の定常確率ベクトルを $\boldsymbol{\pi}_n=(\pi_{n,1}, \ldots, \pi_{n,d})\,$ で表すと, 行列幾何形式解より, 公比行列 $\boldsymbol{R}\,$ を用いて

$\mathbf{\pi}_n = \mathbf{\pi}_0 \mathbf{R}^n, \quad n=1,2,\ldots$ 　　　　　 $(3)\,$

と表される. $\boldsymbol{R}\,$ は推移確率行列の要素を係数とする非線形行列方程式の非負最小解として与えられ, 逐次代入法などで計算することができる. また $\boldsymbol{\pi}_{0}\,$ は境界条件に相当する線形方程式を解いて求められる [2]. この方法は, 本来無限次元の定常分布を有限次元のベクトルと行列で表せるという特徴を持つが, 高速化のためには $\boldsymbol{R}\,$ の計算方法がポイントとなる.

　なお, M/G/1型マルコフ連鎖は行列幾何形式解を持たないが, やはりその構造を利用したさまざまな方法が考えられている [2].

参考文献

[1] D. P. Heyman and M. J. Sobel (eds.), 伊理, 今野, 刀根監訳, 『確率モデルハンドブック』, 朝倉書店, 1995.

[2] M. F. Neuts, Matrix Goemtric Solutions in Stochastic Models - An Algorithmic Approach, Johns Hopkins Univ. Press, 1981.

[3] M. F. Neuts, Structured Stochastic Matrices of {rm M/G/1} Type and Their Applications, Marcel Dekker, 1989.

[4] W. J. Stewart (ed.), Numerical Solution of Markov Chains, Marcel Dekker, 1991.

[5] W. K. Grassmann (ed.), Computational Probability, Kluwer Academic Publishers, 2000.

「OR事典」の他の用語

確率と確率過程：

マルコフ性マルコフ決定過程マルコフ連鎖マルコフ連鎖の数値解法マルコフ過程マルチンゲールラプラス変換

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「numerical method for Markov chain」の例文・使い方・用例・文例

「資格商法」とは文字通りには「qualification selling method」という意味であり、根拠のない資格や学位を法外な値段で売る詐欺的ビジネスである。
5 月15 日の午前 8 時30 分から午後 3 時まで、Oceanview 公園で開催される、毎年恒例のWalk for Petsについてのお知らせです。
イベントによる収益金の半分は、捨てられたペットのための保護施設であるHome for Petsに使われ、残りはさまざまな動物福祉団体に分配されます。
年次監査を行うために、Bradford and Partnersの会計士たちが10 月10 日の午前 10 時に当社を訪ねてくる予定です。
Bradfordの新人会計士2 名が今年の監査を担当すると連絡がありました。
こんにちは、Bradfordさん。
昨日 Bradfordさんが受け取られたデスクランプについてお電話を差し上げています。
取り違えてしまって申し訳ありませんが、あのランプは別のお客様に送られるはずのもので、誤って Bradfordさんに配送されました。
Bradfordさんが受け取るはずだった商品は、Anne Keeganさんからの贈り物のご注文でした。
タックマンモデルとは、チームビルディングにおける5段階、すなわち形成(Forming)、混乱(Storming)、統一(Norming)、機能(Performing)、散会(Adjourning)を示すモデルである。
着手する; 〔…の〕端緒を開く〔for〕.
紺《Oxford 大学およびその選手の色標》.
〔音楽会などへの〕優待券, 招待券〔to, for〕.
等位接続詞《and, but, or, for など; ⇔subordinate conjunction》.
【文法】相関語《either と or, the former と the latter など》.
[for a] holiday to [in] France last year. 昨年は休暇をとってフランスへ旅行した.
(最も奥の), foremost (真っ先の).
新大学, 1960 年以降に創設された大学, 板ガラス大学《Oxford, Cambridge のような石造りの ancient universities, 19 世紀に創設された London 大学のような赤れんが造りの redbrick universities に対して言う; 建築様式がふんだんに plate glass を使ってモダンなことから》.
コンセプション岬《California 州にある》.
être for this policy? この政策はどんな存在理由があるのか.

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「numerical method for Markov chain」を含む用語の索引
numerical method for Markov chainのページへのリンク


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

numerical method for Markov chainとは？ わかりやすく解説

マルコフ連鎖の数値解法

概要

詳説

「numerical method for Markov chain」の例文・使い方・用例・文例

numerical method for Markov chainとは？わかりやすく解説