Lesson 3

For various dynamical systems, it is natural to ask whether they stabilize somewhere. In the context of Markov chains, this question can be formulated in terms of the existence of a probability distribution \(\mathbf{r}\) such that, if the system starts in this distribution, it remains unchanged after applying the transition matrix (that is, \(\mathbf{T}\mathbf{r}= \mathbf{r}\)). The resulting vector \(\mathbf{r}\) defined up to a multiplicative constant (so it is usually normalized by dividing by the sum of its components to obtain a valid probability distribution) is called a stationary distribution. Intuitively, \(\mathbf{r}\) represents a distribution of probability mass that remains stable under the transition step.

For example, in the ball drawing problem considered above, it is easy to observe that if we continue drawing balls with replacement for a long time, the probability of drawing a ball of a given color will eventually stabilize. In this case, the stationary distribution is proportional to the number of balls of each color in the bag: \(\mathbf{r}= (\frac{2}{9}, \frac{3}{9}, \frac{4}{9})\) for red, green, and blue balls, respectively. If we substitute this distribution into the equation \(\mathbf{T}\mathbf{r}= \mathbf{r}\), we can verify that it indeed satisfies the relation. \[\begin{bmatrix}1/8 & 2/8 & 2/8 \\ 3/8 & 2/8 & 3/8 \\ 4/8 & 4/8 & 3/8\end{bmatrix} \cdot \begin{bmatrix}2/9 \\ 3/9 \\ 4/9\end{bmatrix} = \begin{bmatrix}2/9 \\ 3/9 \\ 4/9\end{bmatrix}\]

Problem. Find the stationary distribution for our toy graph: output five space-separated numbers \(p_{0}, \dotsc, p_{4}\) where \(p_{i}=\Pr[v=i]\). Specify three decimal digits for each of the five numbers (for example, \(\texttt{0.333 0.008 0.333 0.275 0.050}\)).