Your question is Markov Chains and Steady State. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Upstart models application states with a finite Markov chain, where each row of a transition matrix gives the next-state probabilities. Given an initial distribution, simulate transitions until the distribution converges to the chain's steady-state distribution.
Implement find_steady_state, returning the converged probability distribution. Use an L1 distance between consecutive distributions to determine convergence.
Input consists of:
matrix, an n x n list of lists where matrix[i][j] is the probability of transitioning from state i to state j.initial_distribution, a length-n probability vector.max_iterations, the maximum number of matrix-vector updates.tolerance, the required maximum L1 distance between successive distributions.Return a length-n list representing the steady-state distribution. Round returned values to 10 decimal places. The matrix is guaranteed to describe an irreducible, aperiodic Markov chain, so the steady state is unique and iterative simulation converges within max_iterations.
def find_steady_state(matrix, initial_distribution, max_iterations, tolerance):