Lesson 6

Suppose that in a Markov chain \(\{\alpha_{i}\}_{i=0}^{\infty}\), the set of states is finite. Then, at a given time \(t\), we can find, for each pair of states \((i,j)\), the probability \[\Pr[\alpha_{t+1}= i \mid \alpha_{t} = j].\] Collecting these probabilities into a matrix \(\mathbf{T}^{t}\), we obtain the transition matrix of the chain at time \(t\). Transition matrices have an interesting property: the product of several consecutive transition matrices \(\mathbf{T}^{r-1}\mathbf{T}^{r-2}\cdots \mathbf{T}^{l} = \mathbf{T}^{l \to r}\) gives the transition matrix from time \(l\) to time \(r\). In other words, \[\mathbf{T}^{l \to r}[i,j] = \Pr[\alpha_{r} = i \mid \alpha_{l} = j].\] This can be shown by induction.