マルコフ連鎖
初期状態i から時刻n で状態j に移る確率は、
p i j ( n ) = Pr ( X n = j ∣ X 0 = i ) {\displaystyle p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,}
で定義され、単一段階の遷移は
p i j = Pr ( X 1 = j ∣ X 0 = i ) {\displaystyle p_{ij}=\Pr(X_{1}=j\mid X_{0}=i)\,}
で定義される。n-段階遷移は、任意の 0<k<n に対して次のチャップマン・コルモゴロフの等式を満たす:
p i j ( n ) = ∑ r ∈ S p i r ( k ) p r j ( n − k ) {\displaystyle p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}}
時刻n での状態に関する確率(周辺確率)は次のように書ける:
Pr ( X n = j ) = ∑ r ∈ S p r j Pr ( X n − 1 = r ) = ∑ r ∈ S p r j ( n ) Pr ( X 0 = r ) {\displaystyle \Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r)}
ここで右上付き添え字 ( n ) {\displaystyle (n)} は整数値である。もしマルコフ連鎖が時間に対して定常的ならば、この添え字は"n乗"という意味にとってもよい(下記参照)。