概率 Markov Chain Stationary Distribution

问题分析

Consider a simplified model of a stock's price movement, represented as a two-state Markov chain: State A (high price) and State B (low price). The probability of transitioning from State A to State B is 0.3, and the probability of transitioning from State B to State A is 0.5. Assuming this Markov c

解法

根据题目要求实现相应功能。核心逻辑需要：

// 核心数据结构和方法——根据题目 API 约定实现
// 1. 确定状态表示——选择支持所需操作的数据结构
// 2. 实现核心算法——确保 O(·) 时间复杂度和正确性
// 3. 处理边界条件——空输入、极值参数、并发访问

验证

用具体输入验证：构造已知输入的测试用例，确认输出匹配预期结果。

复杂度与边界

• 时间复杂度：取决于选用的算法
• 空间复杂度：取决于数据规模
• 关键边界条件：空输入、极值参数、并发场景下的正确性保证

英文解析

Analysis

Consider a simplified model of a stock's price movement, represented as a two-state Markov chain: State A (high price) and State B (low price). The probability of transitioning from State A to State B is 0.3, and the probability of transitioning from State B to State A is 0.5. Assuming this Markov chain is irreducible and aperiodic, we can find the stationary distribution pi = (pi_A, pi_B) by solving the balance equations: pi_A * 0.3 = pi_B * 0.5 and pi_A + pi_B = 1.

Solution

struct StationaryDist { double pi_A, pi_B; };
StationaryDist computeStationary(double p_AB = 0.3, double p_BA = 0.5) {
    // Balance equations: pi_A * p_AB = pi_B * p_BA
    // pi_A + pi_B = 1
    // => pi_A = p_BA / (p_AB + p_BA)
    double pi_A = p_BA / (p_AB + p_BA);  // = 0.5/0.8 = 0.625
    double pi_B = p_AB / (p_AB + p_BA);  // = 0.3/0.8 = 0.375
    return {pi_A, pi_B};
}

Complexity & Edge Cases

• Time complexity: O(1) for 2-state, O(N^3) for N-state (matrix solve)
• Space complexity: O(N^2) for general case
• Edge cases: (1) Chain must be irreducible (all states reachable) (2) Must be aperiodic (no cyclic patterns) (3) Self-transition probabilities must be positive

Verification

Compute pi_A = 0.625, pi_B = 0.375. Verify: pi_A * P(A->B) = 0.625 * 0.3 = 0.1875, pi_B * P(B->A) = 0.375 * 0.5 = 0.1875. Balance achieved. Simulate chain and verify long-run proportions converge to stationary distribution.

Key Considerations

Stationary distributions describe long-run behavior of Markov chains. In quantitative finance, regime-switching models use Markov chains to model market states (bull/bear/sideways). The stationary distribution gives the expected time spent in each regime, affecting long-term portfolio allocation and risk management decisions.