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: Pfor 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}")