덩어리성

확률론에서, 덩어리성은 케메니와 스넬이 처음 발표한 일부 연속시간 마르코프 체인의 주공간 크기를 줄이는 방법이다.^[1]

정의

마르코프 체인의 전체 상태 공간이 분리 상태의 하위 집합으로 나뉘는데, 여기서 이러한 하위 집합은 t로_i 표시된다고 가정하자.이것은 상태의 $파티션$${\displaystyle }$T${\displaystyle }$= { ${\displaystyle {t\mathrm{}}_{}}$1, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$, ${\displaystyle \dots \}}${\$displaystyle \scriptstyle {T=\{T_{1},t_{2},\ldots$\}}}을(를) 형성한다.상태 공간과 하위 집합의 수집은 모두 유한하거나 셀 수 없이 무한할 수 있다.연속 시간 Markov 체인${\displaystyle }${${\displaystyle {Xi}_{}}$} ${\displaystyle \{X_{i}\}\}}$은(는) 파티션의 하위 집합 t와_i t에_j 대해, 그리고 subset_i t에 있는 상태 n,n'인 경우에만 파티션 T에 대해 일괄적으로 사용할$$ 수 있다.

${\displaystyle \sum _{m\in t_{j}q(n,m)=\sum _{m\in t_{j}q(n,m),}$

여기서 q(i,j)는 state i에서 state j로 이행하는 비율이다.^[2]

마찬가지로, 확률적 매트릭스 P의 경우, P는 파티션의 하위 집합 t와_i t에_j 대해, 그리고 부분 집합 t에_i 있는 상태 n,n'인 경우에만 파티션 T에 있는 덩어리 가능한 매트릭스다.

${\displaystyle \sum _{m\in t_{j}p(n,m)=\sum _{m\in t_{j}p(n,m),}$

여기서 p(i,j)는 state i에서 state j로 이동할 확률이다.^[3]

예

행렬 고려

${\displaystyle P={\begin{pmatrix}{\frac {1}{2}}&{\frac {3}{8}}&{\frac {1}{16}}&{\frac {1}{16}}\\{\frac {7}{16}}&{\frac {7}{16}}&0&{\frac {1}{8}}\\{\frac {1}{16}}&0&{\frac {1}{2}}&{\frac {7}{16}}\\0&{\frac {1}{16}}&{\frac {3}{8}}&{\frac {9}{16}}\end{pmatrix}}}$

그리고 파티션 t = {(1,2),(3,4)에 일괄 처리되어 있음을 알 수 있으므로, 우리는 이렇게 쓴다.

${\displaystyle P_{t}={\begin{pmatrix}{\frac {7}{8}{8}}{8}}\\frac {1}{16}}\\frac {1}{15}}}{pmatrix}}}}}}}}$

그리고 P를_t T에 있는 P의 덩어리로 된 행렬로 불러라.

연속적으로 일괄 처리되는 프로세스

2012년, Katehakis와 Smit은 예언적으로 구성된 마르코프 체인의 고정 확률을 연속적으로 계산하여 고정 확률을 얻을 수 있는 '성공적으로 일괄 가능한 프로세스'를 발견했다.후자의 각 체인은 (일반적으로 훨씬) 작은 주 공간을 가지고 있으며, 이는 상당한 계산적 개선을 산출한다.이러한 결과는 많은 애플리케이션 신뢰성과 대기 중인 모델 및 문제를 가지고 있다.^[4]

준-허용도

프란체스치니스와 문츠는 요율 매트릭스의 작은 변화로 체인이 뭉쳐지는 준결함성을 도입했다.^[5]

참고 항목

• 거의 완전히 분해될 수 있는 마르코프 체인

참조