A cleaning robot moves between the rooms of an office. Every minute it leaves its current room a for room b with probability P[a][b] (a missing entry means 0, each row adds up to 1, and a row may send the robot back to the same room). The robot can get from every room to every other room, possibly in several moves. The facilities manager wants to know what fraction of its time the robot spends in each room in the long run: the distribution pi with
pi[b] = sum over a of pi[a] * P[a][b] for every room b,
whose entries add up to 1 (there is exactly one such distribution for a chain like this).
Write long_run(P) that returns pi as a dict with an entry for every room, each accurate to within 1e-8.
The setup provides office_rooms(n, seed), which returns the table of a random office with n rooms.
Examples
Input: P = {"hall": {"hall": 0.7, "desk": 0.2, "lab": 0.1},
"desk": {"hall": 0.3, "desk": 0.4, "lab": 0.3},
"lab": {"hall": 0.2, "desk": 0.4, "lab": 0.4}}
Output: {"hall": 0.46153846153846156, "desk": 0.3076923076923077, "lab": 0.23076923076923078}
Explanation: 6/13, 4/13 and 3/13; one more step leaves these shares unchanged.
Input: P = {0: {1: 1.0}, 1: {0: 0.5, 2: 0.5}, 2: {1: 0.5, 3: 0.5}, 3: {2: 1.0}}
Output: {0: 0.16666666666666666, 1: 0.3333333333333333, 2: 0.3333333333333333, 3: 0.16666666666666666}
Explanation: a corridor of four rooms. The robot alternates between even and odd
rooms, so the distribution after n minutes keeps swinging, but the long-run
fractions of time are well defined.
Constraints
1 <= len(P) <= 40, room names are strings or whole numbers- every room can be reached from every other room
- floats are compared with a tolerance of
1e-6; results must not depend on the clock
Goals
- Find the distribution that one more step of a chain leaves unchanged
- Iterate a distribution until it stops changing, with a sensible stopping rule
- Handle chains where the plain iteration oscillates forever