Stationary City Population Shares
IMC Trading● MediumFULLTIMENEW GRADPHONE SCREENProblem statement
A population moves among n cities once per day. A person in city i chooses the next city according to the probabilities represented by transitionWeights[i].
Return the stationary population share for each city: the unique nonnegative vector pi with total one and pi[j]=sum(i,pi[i]*P[i][j]). For this exercise, assume positive off-diagonal weights make the chain irreducible. This is its equilibrium share vector, including when a particular initial population oscillates in a periodic chain.
For this exercise, assume a general city count and integer row weights are supplied as inputs. Complete stationaryCityShares(transitionWeights). Answers within 1e-9 absolute error per entry are accepted.
Function
stationaryCityShares(transitionWeights: int[][]) → double[]Examples
Example 1
transitionWeights = [[2,1,1],[1,0,1],[1,1,2]]return = [0.4,0.2,0.4]In NYC, Nashville, SF order, equilibrium is [0.4,0.2,0.4]. The report supplies this transition table for the separate arrival-time follow-up; reusing it here is an authored stationary example.
Example 2
transitionWeights = [[1]]return = [1.0]All population stays in the only city.
Example 3
transitionWeights = [[0,1],[1,0]]return = [0.5,0.5]The population changes city daily. This periodic chain still has stationary shares [0.5,0.5].
Example 4
transitionWeights = [[0,3],[1,2]]return = [0.25,0.75]City zero always moves to city one; city one returns with probability one third. Balance pi[0]=pi[1]/3 gives [0.25,0.75].
Constraints
- For this exercise, assume a square matrix of
1 <= n <= 10cities, with integer weights from0through100. - For
n>1, every off-diagonal weight is at least one; diagonal weights may be zero. For one city, its sole weight is positive. - Each row is normalized independently:
P[i][j]=transitionWeights[i][j]/sum(transitionWeights[i]). - For this exercise, assume outputs follow input city order and inputs are not modified.