흡수 마르코프 연쇄(도달 시간·흡수 확률) 계산기

한 번 들어가면 나오지 못하는 상태입니다. 전이행렬에서 자기 자신으로 갈 확률이 1인 행이 그것입니다. 도박꾼이 파산하거나 목표에 닿는 것, 게임이 끝나는 것, 절차가 완료되거나 중단되는 것이 흡수 상태입니다.

일시 상태끼리의 전이만 모은 Q에 대해 N = (I − Q)⁻¹로 정의되는 행렬입니다. N[i][j]는 i에서 시작해 끝나기까지 j에 머무는 횟수의 기댓값이며, 이 하나로 기대 흡수 시간과 흡수 확률이 모두 나옵니다.

급수로 보면 바로 보입니다. N = I + Q + Q² + ⋯이고 Q^k[i][j]가 «정확히 k걸음 뒤에 j에 있을 확률»이므로, 모두 더하면 j에 머무는 횟수의 기댓값이 됩니다. 등비급수의 합이 1/(1−q)인 것과 같은 꼴이며, 행렬판에서는 1 − q가 I − Q가 되는 셈입니다.

기본행렬의 행 합입니다. 어디에 머물렀든 한 걸음은 한 걸음이므로, 모든 일시 상태에 머문 횟수를 더하면 걸린 걸음 수가 됩니다. 분산도 같은 재료로 (2N − I)t − t∘t로 구합니다.

B = N·R입니다. R은 일시 상태에서 흡수 상태로 바로 가는 확률이고, N이 «가는 길에 어디에 얼마나 머무는가»를 담고 있으므로 둘을 곱하면 각 흡수 상태로 끝날 확률이 됩니다. 행 합은 언제나 1입니다.

묻는 것이 다릅니다. 정상분포는 흡수 상태가 없는 연쇄를 오래 두었을 때 «어디에 얼마나 있는가»이고, 흡수 연쇄는 «언제 어디서 끝나는가»입니다. 흡수 상태가 있으면 결국 거기에 갇히므로 정상분포를 묻는 것이 의미가 없어집니다.

I − Q가 특이하다는 뜻이며, 일시 상태들끼리 갇혀 영원히 도는 고리가 있다는 신호입니다. 그런 상태에서 출발하면 결코 흡수되지 않아 기대 시간이 무한대가 됩니다. 흡수 상태로 가는 길이 모든 일시 상태에 있는지 확인해 보십시오.

닫힌 꼴이 있는 예와 견주면 됩니다. 공정한 도박꾼의 파산은 파산 확률이 (목표 − 시작)/목표, 기대 게임 수가 시작×(목표 − 시작)이고, 테니스 듀스는 한 점 승률이 p일 때 게임 승률이 p²/(1 − 2p(1−p))입니다. 이 계산기의 답이 그 값과 소수점까지 맞습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지며 입력한 행렬은 이 기기에만 남습니다.