이 실험 소개
마르코프 연쇄는 상태 사이를 무작위로 이동하지만, 각 이동의 확률은 그 상태에 도달한 경로가 아니라 현재 상태에만 달려 있습니다. 내일의 날씨는 오늘의 날씨에, 웹 서퍼가 다음에 방문할 페이지는 현재 페이지에, 분자의 다음 형태는 현재 형태에 달려 있습니다. 연쇄가 어떻게 시작하든, 적절한 조건을 만족하는 연쇄는 시작 상태를 잊고 정상 상태 π에 수렴합니다. 전이 확률을 수정하고 연쇄를 실행하여 장기 빈도와 분포 pₙ이 π로 수렴하는 모습을 살펴보세요.
학습 목표
- 마르코프 연쇄의 전이 행렬을 작성하고 각 행의 합이 1인지 확인하기
- n단계 후의 분포를 p₀Pⁿ으로 계산하기
- πP = π를 풀어 정상 분포 구하기
- 수렴 속도와 P의 두 번째로 큰 고윳값 사이의 관계 살펴보기
- 주기적 연쇄처럼 수렴하지 않는 연쇄 알아보기
사용 방법
- 1Weather 체인에서 실행을 누르고 토큰을 관찰하세요. 그런 다음 1000단계를 누르세요. 막대는 점선에 얼마나 가까워졌나요?
- 2시작 상태를 바꿔 보세요. 정상 상태도 바뀌나요? 위쪽 그래프의 초반 부분도 바뀌나요?
- 3정상 상태를 직접 확인해 보세요. π에 행렬을 곱해 다시 π가 되는 것을 보여 주세요.
- 4느린 혼합을 선택하세요. 위쪽 그래프가 안정되는 데 몇 단계가 필요한가요? |λ₂| 및 표시된 값과 비교해 보세요.
- 5주기적 순환을 선택하세요. 각 상태에서 보내는 시간의 비율은 안정되는데도 위쪽 그래프는 왜 결코 안정되지 않나요?
- 6즉시 잊기를 선택하세요. 분포가 한 단계 만에 π에 도달하는 이유는 무엇인가요?
모델
가정
- 세 개의 상태와 시간에 따라 변하지 않는 전이 확률입니다. 각 행은 슬라이더 두 개로 편집하며, 남은 확률이 현재 상태에 머무를 확률입니다.
- 표본 경로는 시드가 지정된 난수 생성기에서 나오므로, 실행 번호가 같으면 항상 같은 경로가 생성됩니다. ‘새 실행’을 선택하면 시드가 바뀝니다.
- 정상 상태는 연립 일차 방정식을 정확히 풀어 구합니다. 오차가 1 % 이내가 될 때까지 필요한 단계 수는 ln 100 / (-ln |λ₂|)로 추정합니다.
수업에서 해 보기
- Q1P = [[0.9, 0.1], [0.5, 0.5]]일 때 정상 분포를 구하세요.
- Q2P의 모든 열의 합도 1이면 균등 분포가 정상 분포임을 보이세요.
- Q3|λ₂| = 0.95인 마르코프 연쇄가 있습니다. 시작 상태를 잊는 데 대략 몇 단계가 필요할까요?
- Q4‘주기적 순환 연쇄’에는 정상 분포가 있지만 pₙ은 그 분포로 수렴하지 않는 이유를 설명하세요.
- Q5Google의 초기 PageRank는 무작위 서퍼의 정상 분포입니다. 왜 모든 페이지로 이동할 작은 확률을 추가했을까요?
자주 묻는 질문
여기서 ‘기억이 없다’는 것은 무엇을 의미하나요?
미래는 현재 상태를 통해서만 과거에 의존합니다. 오늘 비가 온다는 것을 알고 있다면, 지난주에 날씨가 맑았다는 사실을 알아도 내일에 대해 더 알 수 있는 것은 없습니다.
모든 연쇄에 정상 상태가 있나요?
모든 유한 마르코프 연쇄에는 적어도 하나의 정상 분포가 있습니다. 모든 상태에서 다른 모든 상태로 이동할 수 있으면 정상 분포는 유일합니다. 여기에 연쇄가 비주기적이기까지 하면, 어떤 상태에서 시작하더라도 pₙ은 그 분포로 수렴합니다.
마르코프 연쇄는 어디에 사용되나요?
대기 행렬 및 신뢰성 모델, 유전학, 음성 인식, 텍스트 예측, 금융 분야에서 사용되며, 표본을 추출하려는 분포를 정상 상태 분포로 갖는 연쇄를 구성하는 마르코프 연쇄 몬테카를로에도 사용됩니다.