AI: Predict a Markov chain

Predict the future distribution of a process that changes randomly.

What to build

A program that computes the distribution of a Markov chain after k steps.

Requirements

  • Row r of the transition matrix gives the probabilities of moving from state r to each state.
  • Print STATE: P for each state in order, with four decimal places.

Input

Line 1: the state names. Then n rows of the transition matrix. Then the initial distribution. Last line: k.

Output

n lines.

Constraints

n ≤ 10, k ≤ 100.

Example

Input:

Sunny Rainy
0.9 0.1
0.5 0.5
1 0
1

Output:

Sunny: 0.9000
Rainy: 0.1000

Why it works

Each step spreads every state's probability over its possible next states, so applying the transition model k times gives the distribution k steps ahead.

Examples

Example 1 · Input
Sunny Rainy
0.9 0.1
0.5 0.5
1 0
1
Expected output
Sunny: 0.9000
Rainy: 0.1000
Example 2 · Input
Sunny Rainy
0.9 0.1
0.5 0.5
0.3 0.7
0
Expected output
Sunny: 0.3000
Rainy: 0.7000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

One step: new[s] = Σ over r of old[r] × T[r][s].

Hint 2

Repeat the step k times.

Solution

Show one correct solution (try it yourself first)
states = input().split()
n = len(states)
T = [list(map(float, input().split())) for _ in range(n)]
dist = list(map(float, input().split()))
for _ in range(int(input())):
    dist = [sum(dist[r] * T[r][s] for r in range(n)) for s in range(n)]
for s, p in zip(states, dist):
    print(f"{s}: {p:.4f}")

Lesson: Hidden Markov models →