- AllCalc 수학, 과학, 공학 이야기 확률통계
마르코프 체인, 마코브 체인, 마르코프 연쇄
-
- *.105.205.197
- 2024.08.15 - 17:46 2024.08.13 - 15:16 24 2
위키피디아 펌 및 AI 설명 추가
https://ko.wikipedia.org/wiki/%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%EC%97%B0%EC%87%84
확률론에서 마르코프 연쇄(Марков 連鎖, 영어: Markov chain)는 이산 시간 확률 과정이다.
마르코프 연쇄는 시간에 따른 계의 상태의 변화를 나타낸다. 매 시간마다 계는 상태를 바꾸거나 같은 상태를 유지한다. 상태의 변화를 전이라 한다. 마르코프 성질은 과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 것을 뜻한다
정의
확률 공간(Probability Space) \( \Omega \)와 모든 집합이 가측 집합인 가측 공간(Measurable Space) \( E \)가 주어졌다고 하자.
그렇다면, 메모리(Memory) \( k \)의 마르코프 연쇄는 다음 성질을 만족시키는 일련의 확률 변수 \( X_1, X_2, \dots \colon \Omega \to E \)이다.
(가측공간은 주로 상태공간의 부분집합임)
만약 다음 식의 양변이 존재한다면,
\[
\Pr(X_{n} = x_{n} \mid X_{n-1} = x_{n-1}, \ldots, X_{1} = x_{1}) = \Pr(X_{n} = x_{n} \mid X_{n-1} = x_{n-1}, \ldots, X_{n-K} = x_{n-K})
\]
이 경우, \( E \)를 메모리 \( k \)의 마르코프 연쇄 \( \{X_i\} \)의 상태 공간이라고 한다. 만약 메모리가 주어져 있지 않는 마르코프 연쇄는 메모리가 1인 마르코프 연쇄이다.
메모리가 1인 마르코프 연쇄는 과거의 상태가 알려져 있더라도 미래 상태의 조건부 기댓값에 영향을 미치지 않는 과정을 나타낸다. 이러한 성질을 마르코프 성질이라고 한다.
다음 성질을 만족시키는 마르코프 연쇄 \( X_i \colon \Omega \to E \)를 시간 동질 마르코프 연쇄라고 한다. 모든 \( i \in \mathbb{N} \), \( x, y \in E \)에 대하여,
\[
\Pr(X_{i+1} = x \mid X_{i} = y) = \Pr(X_{i} = x \mid X_{i-1} = y)
\]
다시 말해, 시간에 따라서 전이 확률은 변하지 않는다.
이와 유사하게, \( i \in \mathbb{N} \) 대신 실변수 \( t \in \mathbb{R} \)에 의존하는 경우도 정의할 수 있다. 이 경우를 연속 마르코프 과정이라고 한다.
예
ㄴ 유향 그래프로 나타낸 시간 동질 마르코프 연쇄의 예
상태 공간이 (모든 부분집합이 측도 가능한) 유한 집합이라고 하자. 이 경우, 시간 동질 마르코프 연쇄는 각 변에 0과 1 사이의 실수가 붙어 있는 유향 그래프로 표현된다. 이 경우 그래프는 다음과 같이 해석된다.
- 각 꼭짓점은 상태 공간의 원소에 대응된다.
- 상태 \( x_1 \in E \)에서 다른 상태 \( x_2 \in E \)로 가는 변은 정확히 하나가 있으며, 이 변에 붙어 있는 값은 \( \Pr(X_{n+1} = x_2 \mid X_n = x_1) \)이다. 만약 이 확률이 0이라면 변을 생략할 수 있다.
이러한 그래프를 상태 다이어그램 (영어: *state diagram*)이라고 한다.
행의 합이 1인 체인 vs 열의 합이 1인 체인?
일반적인 마르코프 체인 설명을 보면 열(세로축)의 합이 1인 것으로 설명합니다.
중고등학교 때 배웠던 행렬의 계산 과정과도 일치하구요.
그런데 아래 링크의 설명에서는 행(가로축)의 합이 1인 것을 설명합니다.
https://velog.io/@nochesita/%ED%99%95%EB%A5%A0%ED%86%B5%EA%B3%84-%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84-%EC%B2%B4%EC%9D%B8-Markov-Chain
Claude 3.5 Sonnet
네, 전이 행렬에서 행(row)의 합이 1인 것과 열(column)의 합이 1인 것은 중요한 차이가 있습니다. 이 차이를 설명해 드리겠습니다:
- 행(Row)의 합이 1인 경우:
- 이는 일반적인 마르코프 체인의 전이 행렬을 나타냅니다.
- 각 행은 현재 상태에서 다른 모든 가능한 상태로 전이할 확률을 나타냅니다.
- 모든 가능한 전이의 확률 합은 1이어야 하므로, 각 행의 합이 1이 됩니다.
- 이를 "행 확률적(row stochastic)" 행렬이라고 합니다.
- 열(Column)의 합이 1인 경우:
- 이는 역방향 전이를 나타내는 행렬입니다.
- 각 열은 다른 모든 상태에서 현재 상태로 전이해 올 확률을 나타냅니다.
- 이를 "열 확률적(column stochastic)" 또는 "좌 확률적(left stochastic)" 행렬이라고 합니다.
- 이러한 행렬은 일부 특수한 경우에 사용됩니다 (예: 역방향 마르코프 과정).
주요 차이점:
- 해석: 행의 합이 1인 경우는 "현재 상태에서 다음 상태로의 전이"를 나타내고, 열의 합이 1인 경우는 "이전 상태에서 현재 상태로의 전이"를 나타냅니다.
- 사용: 일반적인 마르코프 체인에서는 행의 합이 1인 행렬을 주로 사용합니다.
- 계산: 행의 합이 1인 경우, 상태 벡터를 행렬의 왼쪽에 곱하여 다음 상태를 계산합니다. 열의 합이 1인 경우, 상태 벡터를 행렬의 오른쪽에 곱합니다.
결론적으로, 주어진 설명에서 "전이 행렬의 각 row의 합은 반드시 1"이라는 부분이 일반적인 마르코프 체인의 전이 행렬을 더 정확하게 설명하고 있습니다.
열이든 행이든 한쪽만 일관적으로 사용하면 문제가 없는데,
AI의 경우 두개를 짬뽕시켜서 답변하는 경우가 있습니다.
주의하세요.
기타 참고
https://www.puzzledata.com/blog190423/
Comment 2
-
-
-
-
-
아이템 강화 확률 (12강 -> 18강을 이루기 위한 평균 기대 횟수는?)
https://allcalc.org/45976
-
A -> B -> C 단계로의 아이템 강화 설명
- A 유지 : A 70%
- B로 상승: B 30%
- A로 하락 : 50%
- B 유지 : 30%
- C로 상승 : 20%
초기에 A상태=90개, B상태=10개 를 모두 강화할 때
다음상태는 A상태=68개, B상태=30개, C상태=2개 가 될 것으로 예측.
주어진 정보를 마르코프 체인의 관점에서 해석해보겠습니다.
\[
P = \begin{bmatrix}
0.7 & 0.5 & 0 \\
0.3 & 0.3 & 0 \\
0 & 0.2 & 1
\end{bmatrix} \]
\[
\I_0 = \begin{bmatrix}
90 \\
10 \\
0
\end{bmatrix}
\]
90개가 A상태, 10개가 B상태에 있음을 나타냅니다.
I₁ = P * I₀
\[
I_1 = \begin{bmatrix}
0.70 & 0.50 & 0.00 \\
0.30 & 0.30 & 0.00 \\
0.00 & 0.20 & 1.00
\end{bmatrix}
\times
\begin{bmatrix}
90 \\
10 \\
0
\end{bmatrix}
\]
계산해 보면:
\[
\begin{aligned}
I_1[1행] &= (0.70 \times 90) + (0.50 \times 10) + (0.00 \times 0) \\
&= 63 + 5 \\
&= 68 \\
\\
I_1[2행] &= (0.30 \times 90) + (0.30 \times 10) + (0.00 \times 0) \\
&= 27 + 3 \\
&= 30 \\
\\
I_1[3행] &= (0.00 \times 90) + (0.20 \times 10) + (1.00 \times 0) \\
&= 0 + 2 \\
&= 2
\end{aligned}
\]
이 마르코프 체인 모델은 각 강화 시도가 독립적이며, 다음 상태가 오직 현재 상태에만 의존한다는 가정을 바탕으로 합니다. 이를 통해 시스템의 미래 상태를 예측하고 분석할 수 있습니다.