매트릭스 분석법

확률론에서, 행렬 분석법은 반복 구조(어떤 점 이후)와 1차원 ^[1][2]이하에서 무한히 성장하는 상태 공간을 가진 마르코프 사슬의 정상 확률 분포를 계산하는 기술이다.이러한 모델은 M/G/1 ^[3][4]큐의 전이를 기술할 수 있기 때문에 종종 M/G/1 타입 마르코프 체인으로 기술된다.이 방법은 매트릭스 기하학 방법의 보다 복잡한 버전이며 M/G/1 ^[5]체인에 대한 고전적인 솔루션 방법입니다.

방법 설명

M/G/1형 확률 행렬은 다음과 같은 형태^[3] 중 하나이다.

${\displaystyle P=pmatrix 시작}B_{0}&B_{1}&B_{2}&B_{3}&\cdots\\A_{0}&A_{1}&A_{2}&A_{3}&\cdots\&A_{0}&A_{1}&A_{2}&\cdots\&&A_{0}&A_{1}&\cdots\vdots &\vdots &\vdots &\dots \end {pmatrix}$

여기서_i B와_i A는 k × k 행렬이다.(마크가 없는 매트릭스엔트리는 0을 나타냅니다).이러한 행렬은 M/G/1 ^[6][7]큐에 내장된 마르코프 체인을 기술한다.만약 P가 환원 불가능하고 양의 반복이라면, 정상 분포는 방정식에^[3] 대한 해로 주어진다.

${\displaystyle P\pi =\pi \display\mathbf {e} ^{\text{\text}T}}\pi =1}$

여기서 e는 모든 값이 1인 적절한 차원의 벡터를 나타냅니다.P의 구조에 맞추어 is는₁ ,, ,, …로 분할된다₂₃.이러한 확률을 계산하기 위해 확률행렬 G 열은 다음과 같이 계산된다^[3].

${\displaystyle G=\sum _{i=0}^{\infty}G^{i}A_{i}.$

G는 ^[8]보조행렬이라고 불린다.매트릭스가 정의되어^[3] 있다

${\displaystyle {\overline {A}_{i+1}&=\sum _{j=i+1}^{\infty }G^{j-i-1}A_{j}\{\overline {B}_{i}&={j=i}^{infty}G^{-I}{j}$

그럼₀ solving은^[3] 풀어서 구해요.

${\displaystyle {\overline {B}}_{0}\pi _{0}&=\pi _{0}\\pi \left(\mathbf {e})^{\text{\text}T}}+\mathbf {e}^{\text{T}}\left(I-\sum _{i=1}^{\infty}{\overline {A}_{i}\right)^{-1}\sum _{i=1}^{\infty}{\overline {B}_{i}\right}\pi _{0}&1\endaligned}}$

the는_i 1988년 Vaidyanathan Ramaswami가 처음 발표한 수치적으로 안정된 관계인 Ramaswami의 ^[3]공식에 의해 주어진다.^[9]

${\displaystyle \pi _{i}=(I-{\overline {A}_{1})^{-1}\left[{\overline {B}_{i+1}\pi _{0}+\sum _{j=1}^{i-1}{\overline {A}_{i}_{i}\j}\ge}, 오른쪽,$

G의 계산

G를 ^[10][11]계산하는 방법에는 두 가지 일반적인 반복 방법이 있습니다.

• 기능 반복
• 주기적 감소

도구들

• MAMSolver^[12]

레퍼런스