Compute and estimate Markov transition probabilities
Quick Overview
This question evaluates understanding of discrete-time Markov chains, multi-step transition probabilities and empirical estimation of transition matrices, testing probabilistic reasoning and matrix-based computation in the Statistics & Math domain for a Data Scientist role; it is commonly asked because it probes both theoretical grasp of stochastic processes and practical data-driven parameter estimation. At an applied algorithmic abstraction level, it requires explicit mapping of state labels to matrix indices, computing k-step transitions from a given row-stochastic matrix, estimating transition probabilities from observed one-step transitions, and addressing zero-outgoing-observation cases and any chosen smoothing policy (or justification for none).
A system is modeled as a discrete-time Markov chain over m states S = {s1, s2, ..., sm}.
Part A (multi-step probabilities):
-
You are given a row-stochastic transition matrix
Pof shape(m x m), whereP[i][j] = P(X_{t+1}=sj | X_t=si). -
For several queries
(start_state=a, end_state=b, steps=k), computeP(X_{t+k}=b | X_t=a).
Part B (estimate transition matrix from observations):
-
You are given a list of observed one-step transitions, e.g.
[(s1,s2), (s2,s3), (s1,s3), (s1,s2), ...]. -
Estimate the transition probability matrix
\hat{P}using empirical transition frequencies.
Requirements/notes:
- Clearly define how you map state labels to matrix indices.
- Handle states that may have zero outgoing observations in Part B.
- State any smoothing you choose (or justify not using smoothing).