Compute multi-step Markov probabilities and estimate transitions

Problem (Markov Chain)

Assume a discrete-time Markov chain over a finite set of states $S = \{s_1, \dots, s_n\}$.

Part A — Multi-step transition probabilities

You are given a 1-step transition probability matrix $P \in \mathbb{R}^{n \times n}$, where $P_{ij} = \Pr(X_{t+1}=s_j \mid X_t=s_i)$.

Answer queries of the form:

• $\Pr(X_{t+k}=s_j \mid X_t=s_i)$ for various $i, j, k$ .

You may use matrix multiplication (e.g., matmul) in your solution.

Part B — Estimate the transition matrix from observed transitions

You are given a list of observed consecutive transitions (state pairs), e.g.:

[(s1, s2), (s2, s3), (s1, s3), (s1, s2), ...]

Construct an estimated transition matrix $\hat P$ using transition frequencies:

• $\hat P_{ij} = \frac{\#(s_i \to s_j)}{\sum_{j'} \#(s_i \to s_{j'})}$

Requirements / Edge cases to address

• How to handle states that appear in the state list but have zero outgoing transitions in the data.
• Ensure each row of $\hat P$ is a valid probability distribution (sums to 1 where defined).