Lesson 7

Programming problem.

Implement a program for the same task where \(k\) can be as large as \(10^{9}\). Note that a solution that multiplies the original distribution vector \[\mathbf{r}= \left(\frac{1}{n}, \frac{1}{n}, \dotsc, \frac{1}{n}\right)^{T}\] by the transition matrix \(k\) times would not fit into the time limit. To multiply faster, note that multiplying \(\mathbf{r}\) by the transition matrix \(k\) times is the same as multiplying the vector by the \(k\)-th power of the matrix: \[(\mathbf{T}(\mathbf{T}(\mathbf{T}\mathbf{r})))=\mathbf{T}^{3}\mathbf{r}.\] Hence, one needs to compute \(\mathbf{T}^{k}\) quickly. This can be achieved using exponentiation by squaring in about \(\log_{2} k\) matrix multiplications.

5 13 1
1 2
1 3
1 5
2 1
2 3
2 4
2 5
3 1
3 4
3 5
4 2
4 5
5 4

0.11666666666666667 0.16666666666666669 0.11666666666666667 0.31666666666666665 0.2833333333333333