확률 매트릭스

수학에서 확률적 행렬은 마르코프 체인의 전환을 설명하는 데 사용되는 정사각형 행렬이다. 각각의 항목은 확률을 나타내는 음수가 아닌 실제 숫자다.^{[1][2]: 9–11} 확률행렬, 전이행렬, 대체행렬 또는 마르코프행렬이라고도 한다.^{[2]: 9–11} 확률적 매트릭스는 20세기 초 안드레이 마르코프에 의해 처음 개발되었으며, 확률론, 통계학, 수학 금융, 선형 대수학뿐만 아니라 컴퓨터 과학과 인구 유전학 등 광범위한 과학 분야에 걸쳐 사용법을 찾아냈다.^{[2]: 1–8} 확률론적 행렬에는 몇 가지 다른 정의와 유형이 있다.^{[2]: 9–11}

오른쪽 확률형 행렬은 실제 제곱 행렬이며, 각 행은 1에 해당한다.

왼쪽 확률형 행렬은 실제 제곱 행렬이며 각 열은 1로 요약된다.

이중 확률 행렬은 각 행과 열을 합한 1로 음수가 아닌 실제 숫자의 제곱 행렬이다.

같은 맥락에서, 확률 벡터(확률 벡터라고도 함)를 1에 합한 비음수 실수인 벡터로 정의할 수도 있다. 따라서 오른쪽 확률행렬의 각 행(또는 왼쪽 확률행렬의 열)은 확률적 벡터다.^{[2]: 9–11} 영어 수학 문헌에서 흔히 볼 수 있는 관습은 확률의 열 벡터와 왼쪽 확률 매트릭스보다는 확률의 행 벡터와 우 확률 매트릭스를 사용하는 것이다. 이 논문은 그 관습에 따른다.^{[2]: 1–8}

역사

확률적 매트릭스는 러시아 수학자겸 세인트의 교수인 안드레이 마르코프에 의해 마르코프 사슬과 나란히 개발되었다. 1906년에 이 주제에 대해 처음 출판한 페테르부르크 대학교.^{[2]: 1–8 [3]} 그의 초기 의도된 용도는 언어 분석과 카드 섞기 같은 다른 수학 과목에 사용되었지만, 마르코프 체인과 행렬 모두 다른 분야에서 빠르게 사용한다는 것을 발견했다.^{[2]: 1–8 [3][4]}

확률론적 매트릭스는 안드레이 콜모고로프와 같은 학자들에 의해 더욱 발전되었는데, 그는 연속 시간 마르코프 과정을 허용함으로써 가능성을 확장했다.^[5] 1950년대에 이르러서는 계량법과^[6] 회로 이론 분야에서 확률론적 매트릭스를 이용한 기사가 등장하였다.^[7] 1960년대에, 확률론적 매트릭스는 행동^[8] 과학에서 지질학^[9][10], 주거 계획에 이르기까지 훨씬 더 다양한 과학 작품에 등장했다.^[11] 또한, 확률적 매트릭스와 마코비안 공정의 사용 범위와 기능성을 보다 일반적으로 개선하기 위해 이 수십 년을 통하여 많은 수학적 연구가 행해졌다.

1970년대부터 현재까지 확률론적 매트릭스는 구조과학부터^[12] 의료 진단^[13], 인사관리에 이르기까지 형식적인 분석이 필요한 거의 모든 분야에서 활용되고 있다.^[14] 또한 확률론적 매트릭스는 일반적으로 마르코프 매트릭스라는 용어에 따라 토지 변경 모델링을 광범위하게 사용한다는 것을 발견했다.^[15]

정의 및 속성

확률적 매트릭스는 카디널리티 S와 함께 유한 상태 공간 S에 대한 마르코프 체인 X를_t 설명한다.

한 번에 i에서 j로 이동할 확률이 Pr(j i) = P인_i,j 경우, P를_i,j i번째 행과 j번째 열 요소로 사용하여 확률적 행렬 P가 주어진다.

${\displaystyle P=\left는 경우에는{\begin{행렬}P_{1,1}&.P_{1,2}&, \dots &.P_{1,j}&, \dots &.P_{1,S}\\P_{2,1}&.P_{2,2}&, \dots &.P_{2,j}&, \dots &.P_{2,S}\\\vdots, \vdots &, \ddots &, \vdots &, \ddots, \vdots \\P_{i,1}& &, &.P_{i,2}&, \dots &.P_{i,j}&, \dots &.P_{i,S}\\\vdots, \vdots &, \ddots &, \vdots &, \ddots, \vdots \\P_{S,1}& &, &.P_{S,2}&, \dots &.P_{S,j}&, \dots &.P_{S,S}\\\end{매트릭스}}\right 뻗는다.}$

상태 i에서 다른 모든 상태로의 총 전환 확률은 1이어야 하므로,

${\displaystyle \sum _{j=1}^{S}P_{i,j}=1;\,}$

따라서 이 행렬은 우경 확률적 행렬이다.^{[2]: 1–8}

P의 각 행 i에 걸친 위의 요소별 합은 P1 = 1로 보다 간결하게 쓰여질 수 있다. 여기서 1은 모든 행의 S차원 벡터다. 이를 통해 두 개의 우측 확률론 매트릭스 P′과 P′′의 제품도 우측 확률론임을 알 수 있다. P′ P′ 1 = P′ (P′ 1) = P′ 1 = 1 일반적으로 우측 확률행렬 P의 k번째 파워 P도^k 우측 확률행렬이다. 두 단계로 i에서 j로 이행할 확률은 그 다음 P의 제곱의 (i, j)-th 요소에 의해 주어진다.

${\displaystyle \left(P^{2}\right)_{i,j}.}$

일반적으로 k단계의 행렬 P에 의해 주어진 유한 마코프 체인의 어떤 상태로부터 다른 상태로 가는 확률 전환은^k P에 의해 주어진다.

시스템이 처음에 있을 수 있는 위치와 어떤 확률을 가지고 있을 수 있는지를 지정하는 상태의 초기 확률 분포는 행 벡터로 주어진다.

고정 확률 벡터 π은 변환 행렬의 적용에 따라 변하지 않는 행 벡터로 쓰여진 분포로 정의된다. 즉, 고유값 1과 연관된 확률 행렬의 행 고유 벡터인 집합 {1, …, n}에 대한 확률 분포로 정의된다.

${\displaystyle {\boldsymbol {\pi }P={\boldsymbol {\pi}}.}$

어떤 확률적 매트릭스의 스펙트럼 반경이 하나임을 알 수 있다. 게르슈고린 원 정리로는 확률행렬의 모든 고유값은 절대값이 1보다 작거나 같은 값을 갖는다. 또한 모든 우측 확률행렬에는 고유값 1: 벡터 1과 연관된 "불확실한" 열 고유 벡터 1이 있으며, 이들의 좌표는 모두 1과 같다(A 곱하기 1은 행 입력의 합과 같으며, 따라서 1과 같다는 것만 관찰한다). 정사각형 행렬의 좌우 고유값이 같기 때문에 모든 확률적 행렬에는 적어도 고유값 1과 관련된 행 고유 벡터가 있고 모든 고유값의 최대 절대값도 1이다. 마지막으로 브루워 고정점 정리(유한 집합 {1, …, n}의 모든 확률 분포의 콤팩트 볼록 세트에 적용됨)는 고정 확률 벡터인 일부 좌측 고유 벡터가 있음을 암시한다.

한편, 페론-프로베니우스 정리는 또한 모든 불가해한 확률적 매트릭스에 그러한 고정 벡터가 있음을 보장하며, 고유값의 가장 큰 절대값은 항상 1이다. 그러나 이러한 행렬은 수정할 필요가 없기 때문에 이러한 행렬에 직접 적용할 수 없다.

일반적으로 그러한 벡터가 여러 개 있을 수 있다. 그러나, 엄격히 긍정적인 항목(또는 더 일반적으로, 더 일반적으로, 되돌릴 수 없는 주기적 확률적 매트릭스의 경우)을 가진 매트릭스의 경우, 이 벡터는 고유하며, 우리가 다음 한계를 가지고 있다는 것을 관찰함으로써 계산할 수 있다.

${\displaystyle \lim _{k\오른쪽 화살표 \}\ft }\왼쪽(P^{k}\오른쪽)_{i,j}={\boldsymbol{\pi}}}}}}$

여기서 π은_j 행 벡터 π의 j번째 원소다. 무엇보다도, 이것은 상태 j에 있을 수 있는 장기적 확률은 초기 상태 i와 무관하다고 말한다. 이 두 연산 모두 동일한 정지 벡터를 제공한다는 것은 에고다이컬 정리의 한 형태인데, 이것은 일반적으로 다양한 분산형 역동적인 시스템에서는 사실이다. 즉, 시스템은 시간이 지남에 따라 정지 상태로 진화한다.

직관적으로 확률적 행렬은 마르코프 체인을 나타낸다. 확률 분포에 확률적 행렬을 적용하는 것은 총 질량을 보존하면서 원래 분포의 확률 질량을 재분배한다. 이 과정을 반복적으로 적용하면, 마코프 체인의 고정된 분포로 분포가 수렴된다.^{[2]: 55–59}

예: 고양이 및 마우스

타이머와 다섯 개의 인접한 상자들이 줄을 이루고 있고, 첫 번째 상자는 고양이 한 마리가, 다섯 번째 상자는 쥐 한 마리가 시간 0에 있다고 가정해 보자. 고양이와 마우스는 타이머가 시작되면 둘 다 임의의 인접 박스로 점프한다. 예를 들어 고양이가 두 번째 상자에 있고 마우스가 네 번째 상자에 있을 경우, 고양이가 첫 번째 상자에 있을 확률은 1/4이고 마우스가 타이머가 진전된 후 다섯 번째 상자에 있을 확률은 1/4이다. 고양이가 첫 번째 상자에 있고 마우스가 다섯 번째 상자에 있다면, 타이머가 진척된 후 고양이가 두 번째 상자에 있고 마우스가 네 번째 상자에 있을 확률이다. 고양이가 쥐를 잡아먹으면 둘 다 같은 상자에 넣으면 게임이 끝난다. 랜덤 변수 K는 게임에서 마우스가 머무르는 시간의 수를 제공한다.

이 게임을 대표하는 마르코프 체인은 포지션(cat, mouse)의 조합에 의해 지정된 다음의 5가지 상태를 포함한다. 주의 순진하게 열거하면 25개의 상태를 나열할 수 있지만, (그것은 쥐가 고양이의 상자를 점유하고 그것을 지나갈 때까지 살아남았다는 것을 의미하기 때문에) 쥐가 고양이보다 더 낮은 지수를 가질 수 없기 때문이거나, 또는 두 지수의 합이 항상 균등하게 같기 때문에 많은 지표가 불가능하다. 또한, 쥐의 죽음으로 이어지는 세 가지 가능한 상태가 하나로 결합된다.

• 상태 1: (1,3)
• 상태 2: (1,5)
• 상태 3: (2,4)
• 상태 4: (3,5)
• 상태 5: 게임 오버: (2,2), (3,3) & (4,4)

우리는 확률적 행렬인 $P{\displaystyle }$ ${\displaystyle P}($아래)를 사용하여 이 시스템의 전환 확률을 표시한다(이 행렬의 행과 열은 위에 열거된 가능한 상태로 색인화되며, 변환 전 상태는 행으로, 변환 후 상태는 열로 표시된다).^{[2]: 1–8} 예를 들어 상태 1 - 첫 번째 행부터 시작하여 시스템이 이 상태를 유지하는 것은 불가능하므로 P ${\displaystyle {11}_{}}$= ${\displaystyle 0}$ ${\displaystyle P_{11}=0$ 시스템도 상태 2로 전환할 수 없음 – 고양이가 같은 상자에 머물렀을 것이므로 P ${\displaystyle {12}_{}}$= ${\displaystyle 0}$ ${\displaystyle P_{12}=0$ 및 마우스와 유사한 인수로 인해${\displaystyle P_{}}$ ${\displaystyle {14}_{}}$= ${\displaystyle 0}$ ${\displaystyle P_{14}=0$ 상태 3 또는 5로의 전환이 허용되며, 따라서 $P{\displaystyle {}_{}}$ ${\displaystyle {13}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {15}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 0}$ ${\displaystyle P_{13}, P_{15$}\$neq 0}.$

${\displaystyle P={\begin{bmatrix}0&0&1/2&0&1/2\\0&0&0&0&0\\0&0&0&0&#1\1/1/4/4/1&#0&0&0&#1nd{bmatrix}}}.}$

장기평균

초기 상태가 어떻든 고양이는 결국 쥐를 잡을 것이고(확률 1) 정지상태 = = (0,0,0,0,0,0,1)는 한계로 접근한다.^{[2]: 55–59} To compute the long-term average or expected value of a stochastic variable ${\displaystyle Y}$, for each state ${\displaystyle S_{j}}$ and time ${\displaystyle t_{k}}$ there is a contribution of ${\displaystyle Y_{j,k}\cdot P(S=S_{j},t=t_{k})}$. Survival can 생존 상태의 경우$$ ${\displaystyle \mathrm{Y}}$= 1 ${\displaystyle$ Y$=1},$ 종료된 상태의 경우$$ $Y{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle Y=0}$을(를) 갖는 이진 변수로 처리된다. $Y{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle Y=0}$인 상태는 장기 평균에 기여하지 않는다$$.

위상형 표현

상태 5는 흡수 상태이므로 흡수 시간 분포는 이산 위상 유형 분산이다. 시스템이 상태 2에서 시작되어 벡터${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$,${\displaystyle 0,}$ ${\displaystyle 0}$ ${\displaystyle ]}$ ${\displaystyle [0,1,0,0,0]$으로 표시된다고 가정합시다$.$ 쥐가 죽은 주는 생존 평균에 기여하지 않기 때문에 상태 5는 무시될 수 있다. 초기 상태 및 전환 매트릭스는 다음과 같이 줄일 수 있다.

${\displaystyle {\boldsymbol {\tau }}=[0,1,0,0],\qquad T={\begin{bmatrix}0&0&{\frac {1}{2}}&0\\0&0&1&0\\{\frac {1}{4}}&{\frac {1}{4}}&0&{\frac {1}{4}}\\0&0&{\frac {1}{2}}&0\end{bmatrix}},}$

그리고

${\displaystyle (I-T)^{-1}{\boldsymbol{1}={\begin{bmatrix}2.75\4.5\\\2.75\end{bmatrix},}$

여기서 $I{\displaystyle }$ ${\displaystyle I}$은(는) ID 행렬이고, $1{\displaystyle \mathbf{}}$ ${\$ {$1}은$상태 위에 합으로 작용하는 모든 행렬의 열 행렬을$$ 나타낸다.

각 상태는 한 단계 동안 점유되므로 마우스의 생존 예상 시간은 단지 모든 생존 상태 및 시간에 대한 점유 확률을 합한 것이다.

${\displaystyle E[K]={\boldsymbol {\tau }}}왼쪽(I+T^{2}+\cdots \right){\boldsymbol{1}={\boldsymbol{1}{\1}=4.5}$

더 높은 순서의 순간은 다음을 통해 주어진다.

${\displaystyle E[K(K-1)\dots(K-n+1)]=n!{\boldsymbol {\tau }}(I-{T})^{-n}{T}^{n-1}\mathbf {1} \,.}$

참고 항목

• 밀도 행렬
• 마르코프 커널, 연속 상태 공간에 걸친 확률적 매트릭스와 동등한 것
• 행렬 차이 방정식
• DNA진화의 모델
• 뮤어헤드의 부등식
• 확률론적 자동화

참조