먼저 마르코프 체인의 개념을 이해해야 한다. 첫째, 행렬 밀도를 피하기 위해 스파스 매트릭스에 해당하는 이산 마르코프 체인에 대해 논의합니다. 즉, 셀 수 있는 이산 상태 세트 S 는 임의의 i0, I 1 사이의 관계를 만족시킵니다. in ∩ s 와 시간 n+ 1 의 이전 상태입니다.

P (xn+1= in+1| x0 = i0, X 1=i 1, ..

P (xn+1= in+1| xn = in)

상태 간의 전환 관계, 무작위 과정 X 는 이산 마르코프 체인입니다. 즉, 다음 상태의 확률은 이전 상태와 관계없이 현재 상태로만 결정됩니다.

상태 간 전환 확률은 그래프 (마르코프 체인) 로 나타낼 수 있습니다.

여기에는 세 가지 상태 {1, 2,3} 가 있습니다. 해당 확률 전달 매트릭스 P 는 다음과 같습니다.