Lesson 4

To find the stationary distribution \(\mathbf{r}\), it is sufficient to solve the system of equations defined by the conditions \(\mathbf{T}\mathbf{r}= \mathbf{r}\), \(\sum_{i} \mathbf{r}_{i} = 1\). \[\begin{cases}\dfrac14\ \mathbf{r}_1 + \dfrac13\ \mathbf{r}_2 = \mathbf{r}_0, \\ \dfrac13\ \mathbf{r}_0 + \dfrac12\ \mathbf{r}_3 = \mathbf{r}_1, \\ \dfrac13\ \mathbf{r}_0 + \dfrac14\ \mathbf{r}_1 = \mathbf{r}_2, \\ \dfrac14\ \mathbf{r}_1 + \dfrac13\ \mathbf{r}_2 + \mathbf{r}_4 = \mathbf{r}_3, \\ \dfrac13\ \mathbf{r}_0 + \dfrac14\ \mathbf{r}_1 + \dfrac13\ \mathbf{r}_2 + \dfrac12\ \mathbf{r}_3 = \mathbf{r}_4, \\ \mathbf{r}_0 + \mathbf{r}_1 + \mathbf{r}_2 + \mathbf{r}_3 + \mathbf{r}_4 = 1\end{cases} \;\Rightarrow\; \begin{cases}\mathbf{r}_0 = \dfrac{1}{13} = 0.077, \\ \mathbf{r}_1 = \dfrac{8}{39} = 0.205, \\ \mathbf{r}_2 = \dfrac{1}{13} = 0.077, \\ \mathbf{r}_3 = \dfrac{14}{39} = 0.359, \\ \mathbf{r}_4 = \dfrac{11}{39} = 0.282\end{cases}\] You may also observe that for large values of \(k\), the probabilities of reaching each vertex after \(k\) steps of the random walk become very close to the stationary distribution. For example, after \(k=100\) steps of a random walk, one obtains the following probabilities:

import numpy as np
import networkx as nx

edges = ['01', '02', '04', '10', '12', '13', '14', '20', '23', '24', '31', '34', '43']
graph = nx.DiGraph([(int(e[0]), int(e[1])) for e in edges])
n = graph.number_of_nodes()

A = nx.stochastic_graph(graph)
T = nx.to_numpy_array(A, nodelist=sorted(graph.nodes())).T
r = [1 / n] * n

print(*np.linalg.matrix_power(T, 100) @ r)

0.07692307692307661 0.20512820512820565 0.07692307692307661 0.3589743589743573 0.28205128205128227