Lesson 6

Programming problem.

Implement a program for the following task. Given a directed graph with \(n\) nodes and \(m\) edges. One chooses a (uniformly) random starting node and then, at each step, selects a random outgoing edge and moves along it (if there are no outgoing edges, one stays in the current node). Compute the probability of being at each node after \(k\) steps.

• Input format.  The first line contains integers \(2 \le n \le 100\), \(1 \le m \le \binom{n}{2}\), and \(0 \le k \le 100\). Each of the following \(m\) lines specifies an edge \((u,v)\) of the graph by two integers \(1 \le u \neq v \le n\) (the nodes are indexed by \(1,\dotsc,n\)).


• Constraints.  The graph contains no self-loops or parallel edges.


• Output format.  Output the probabilities \(p_{1}, \dotsc, p_{n}\), where \(p_{i}\) is the probability to end up at the node \(i\) after \(k\) steps of the random walk. Specify each probability with at least twelve digits of precision.

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