마르코프 연쇄 정상 분포
골드 I의견: 0
\(N\)개의 상태로 이루어진 마르코프 연쇄가 있다. 상태 \(i\)에서 상태 \(j\)로 이동할 확률은 \(p_{i,j}\)이며, 각 행의 합은 \(1\)이다. 또한 이 마르코프 연쇄는 에르고딕(ergodic)하여 유일한 정상 분포가 존재한다.
정상 분포 \(\pi_1, \pi_2, \ldots, \pi_N\)을 구하여라. 정상 분포는 \(\pi \cdot P = \pi\)와 \(\sum_{i=1}^N \pi_i = 1\)을 만족하는 분포이다.
각 \(\pi_i\)를 기약분수 \(P/Q\) 형태로 출력한다.
- \(2 \le N \le 10\)
- \(1 \le B_i \le 10\,000\)
- \(1 \le a_{i,j}\), \(\;\sum_{j=1}^N a_{i,j} = B_i\)
- 마르코프 연쇄는 에르고딕이다.
첫째 줄에 상태 수 \(N\)이 주어진다.
다음 \(N\)개의 줄 중 \(i\)번째 줄에 정수 \(B_i\)와 정수 \(a_{i,1}, a_{i,2}, \ldots, a_{i,N}\)이 공백으로 구분되어 주어진다. \(p_{i,j} = \dfrac{a_{i,j}}{B_i}\)이다. 모든 \(a_{i,j} \ge 1\)이며 \(\sum_{j} a_{i,j} = B_i\)이다.
\(N\)개의 줄에 걸쳐 \(\pi_1, \pi_2, \ldots, \pi_N\)을 차례로, 각각 기약분수 \(P/Q\) 형태로 출력한다. (\(\gcd(P, Q) = 1\), \(Q \ge 1\))
2
2 1 1
2 1 1
1/2
1/2
\(2\)개 상태, 전이 확률이 모두 \(\frac{1}{2}\)인 대칭 체인. 정상 분포는 균등하게 \(\pi_1 = \pi_2 = \frac{1}{2}\)이다.
2
3 1 2
4 3 1
9/17
8/17
상태 \(1 \to 2\)의 확률 \(\frac{2}{3}\), \(2 \to 1\)의 확률 \(\frac{3}{4}\). \(\pi_1 = \frac{9}{17}\), \(\pi_2 = \frac{8}{17}\)이다.
riseoj 작성
출처 Original
평가 및 의견
마르코프 연쇄 정상 분포
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마르코프 연쇄 정상 분포