Lesson 8

Homogeneous Markov chains are a special class of Markov chains that do not depend on time. Formally, a chain \(\alpha_{i}\) is called homogeneous if the transition probabilities satisfy \[\Pr[\alpha_{t+1}= i \mid \alpha_{t} = j] = \Pr[\alpha_{s+1}= i \mid \alpha_{s} = j] \quad \text{for all }t, s \ge 0 \text{ and all states }i,j.\] It is easy to see that, for such chains, the transition matrix \(\mathbf{T}^{t}\) is identical at all time steps \(t\). In the following, we will restrict our attention exclusively to homogeneous chains.

A Markov chain can also be represented as a graph, where the vertices correspond to the states of the chain, and the weighted, directed edges represent the transition probabilities between states. In this context, we can now see that the transition matrices of the graphs we discussed earlier can be interpreted as a homogeneous Markov chain. Such a graph is stochastic, since for any current vertex \(j\), transition probabilities to all possible next vertices \(i\) form a probability distribution: \[\sum_{i}\Pr[\alpha_{t+1}= i \mid \alpha_{t} = j] = 1.\] In other words, a graph with weighted directed edges is called stochastic if the sum of the weights of all outgoing edges from each vertex \(j\) equals \(1\).

What is the advantage of such a graph? Just as before, we can multiply a probability vector \(\mathbf{r}\) by the transition matrix \(\mathbf{T}\) to obtain the distribution at the next step (\(\mathbf{r}_{\text{next}}= \mathbf{T}\mathbf{r}\)) or apply it repeatedly to obtain the distribution after multiple steps. Moreover, this representation allows us to exploit certain properties of Markov chains, which will be discussed in more detail later.