评级对到对在 H 期的转移概率：Markov 链 M^H 的单元素

实现 solution(starting_rating: int, ending_rating: int, transition_matrix: list[list[float]], horizon: int) -> float。某信用风险条线维护一张由历史迁移数据估计得到的一期评级转移矩阵 M，其中 M[i][j] 表示当前位于评级桶 i 的债务人在一期之后位于评级桶 j 的概率。该矩阵是行随机的——每一行之和为 1.0。给定起始评级 s、结束评级 e 和期数 H >= 0，返回当前位于 s 的债务人在恰好 H 期之后位于 e 的概率。数学上答案为 (M^H)[s][e]，按约定 M^0 = I（单位阵），所以 P(e | s, H=0) 在 s == e 时为 1.0、否则为 0.0。

每一步的传播公式为

new_v[j] = sum_{i in [0, K)} v[i] * transition_matrix[i][j]

把 v 初始化为起始评级处的基向量（v[s] = 1.0、其余为 0），跑 H 次矩阵-向量乘，再读 v[ending_rating]。i 是源评级（质量从哪里来）、j 是目标评级（质量落在哪里）。由于 M[i][j] 是 FROM-i-TO-j 的概率、每一行（不是每一列）之和为 1.0，把 i 和 j 调换是真正的 bug，会把分布沿时间反向传播；非对称矩阵上结果一律错。

例

solution(0, 1, [[0.85, 0.10, 0.05], [0.10, 0.80, 0.10], [0.0, 0.0, 1.0]], 2) 返回 0.165。该转移矩阵是行随机的——第 0 行 [0.85, 0.10, 0.05] 之和 = 1.0、第 1 行 [0.10, 0.80, 0.10] 之和 = 1.0、第 2 行 [0.0, 0.0, 1.0] 是吸收的违约态。从 v = [1.0, 0.0, 0.0]（starting_rating == 0 处的基向量）出发。第 1 步：new_v[0] = 1.0*0.85 + 0.0*0.10 + 0.0*0.0 = 0.85、new_v[1] = 1.0*0.10 + 0.0*0.80 + 0.0*0.0 = 0.10、new_v[2] = 1.0*0.05 + 0.0*0.10 + 0.0*1.0 = 0.05，所以 1 步后 v = [0.85, 0.10, 0.05]（恰好等于 M 的第 0 行）。第 2 步从 [0.85, 0.10, 0.05] 出发：new_v[0] = 0.85*0.85 + 0.10*0.10 + 0.05*0.0 = 0.7325、new_v[1] = 0.85*0.10 + 0.10*0.80 + 0.05*0.0 = 0.165、new_v[2] = 0.85*0.05 + 0.10*0.10 + 0.05*1.0 = 0.1025。最终 v = [0.7325, 0.165, 0.1025]（之和 = 1.0）。所求项为 v[ending_rating] = v[1] = 0.165。

行 vs 列约定的索引校验：行随机的前向公式取 tm[i][j]（FROM i TO j）、对 i 求和。如果作者误写成 new_v[j] = sum_i v[i] * tm[j][i]（这种索引互换在列随机矩阵——列和为 1.0——下才是对的），那么本例第 1 步从 v = [1, 0, 0] 算出 new_v[0] = 1.0*tm[0][0] = 0.85、new_v[1] = 1.0*tm[1][0] = 0.10、new_v[2] = 1.0*tm[2][0] = 0.0（即 v = [0.85, 0.10, 0.0]、丢了 0.05 的概率质量），第 2 步又算出另一个错误的数，不是正确的 0.165。两种索引只有在对称矩阵上才碰巧吻合。

需要明确的细节：horizon == 0 在 starting_rating == ending_rating 时返回 1.0、否则 0.0（即 M^0 的对应行），不是把转移矩阵作用一次——把转移矩阵作用一次是差一步的 bug，会让所有 H=0 边界用例错。K == 1 时矩阵必然是 [[1.0]]，唯一合法的 (s, e) 是 (0, 0)、输出为 1.0。单位转移矩阵会让 v 在传播下保持不变，所以对任意 H 答案都是 s == e 时 1.0、否则 0.0。违约吸收态 d 编码为 transition_matrix[d] = [0, 0, ..., 1.0, ..., 0]（对角线第 d 位是 1.0、其余为 0）；一旦质量进入 d 就留在 d，故 starting_rating == d 时答案为 ending_rating == d 时 1.0、否则 0.0，与 H 无关。循环里无需任何特判——吸收行就是正确的数学模型，写成防御性的"跳过吸收态"会把传播弄坏。[0, K) 之外的索引属于调用方前置条件违例，本函数不校验、不抛异常；测试集不会传入越界索引。

期望算法是简单的 O(H * K^2) 矩阵-向量传播。把基向量初始化为 v = [0.0] * K、令 v[starting_rating] = 1.0，每一步先 new_v = [0.0] * K、遍历 (i, j) 累加 new_v[j] += v[i] * tm[i][j]、步末 v = new_v。由于 K <= 8、H <= 24，总运算量约为 1536，朴素三层循环远远满足 2000 ms 上限。**每一步必须新开 new_v**——一边读 v[i] 一边原地写 v[j] 会污染本轮累加。重复平方法（矩阵幂 O(K^3 log H)）只在 H 很大时才更快；本题 H <= 24，矩阵-向量迭代就是正确选择，还省下每步分配 (K, K) 缓冲区的开销。

实现细节由 stubs/stub.py 提供。

实践背景

评级对到对的转移概率正是多步转移矩阵 M^H 的元素，可用于信用 VaR 计算和"这只 AAA 级债券到第 5 年滑落到 BB 级的概率有多大？"这类查询式问题。条线根据历史内评迁移估计一张一期转移矩阵之后，会从 M^H 中查询单条 obligor 的迁移概率，喂入压力投影面板、IFRS 9 存续期预期损失计提、CECL 当前预期信用损失准备金等下游。H == 0 取单位阵的约定至关重要：零期的转移核就是单位阵，意思是当下评级的债务人当下处于该评级的概率为 1.0、处于其它评级的概率为 0.0。违约吸收的约定也至关重要：债务人一旦违约、评级迁移模型对其后续轨迹就此止步，所有流入违约态的概率质量都留在违约态——这恰好就是"对应行除对角线 1.0 之外全 0"所编码的内容。本题返回多步转移矩阵的单个元素；本题库的姊妹题前推整张分布，下游的预期损失题把多步分布与按评级分类的风险加权资产数字结合起来。