概率 Entropy Fair Die

问题分析

A fair six-sided die is rolled. Each face has an equal probability of landing face up. Calculate the Shannon entropy of the outcome, expressed in bits. The Shannon entropy $H(X)$ is defined as: $H(X) = - \sum p_i \log_2 p_i$, where $p_i$ is the probability of outcome $i$.

解法

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

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

验证

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

复杂度与边界

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

英文解析

Analysis

A fair six-sided die is rolled. Each face has an equal probability of landing face up. Compute the Shannon entropy of the outcome, expressed in bits. The Shannon entropy H(X) is defined as: H(X) = - sum p_i * log2(p_i), where p_i is the probability of outcome i. For a fair die, p_i = 1/6 for each face.

Solution

double shannonEntropyFairDie() {
    double p = 1.0 / 6.0;  // Equal probability for each face
    double H = 0;
    for (int i = 0; i < 6; ++i) {
        H -= p * std::log2(p);  // H = -sum(p_i * log2(p_i))
    }
    return H;  // = log2(6) ≈ 2.585 bits
}

Complexity & Edge Cases

• Time complexity: O(N) where N = number of outcomes (6 for die)
• Space complexity: O(1)
• Edge cases: (1) Fair coin (2 outcomes) has entropy = 1 bit (2) Deterministic outcome has entropy = 0 (3) Maximum entropy for N outcomes is log2(N)

Verification

Compute log2(6) = 2.58496... bits. Verify entropy equals log2(number of equally likely outcomes). Test that unfair die (unequal probabilities) yields lower entropy.

Key Considerations

Shannon entropy measures the average information content of a random variable. In market microstructure, entropy quantifies the unpredictability of trade direction - a market where buys and sells are equally likely has maximum entropy (1 bit), while a market dominated by one direction has lower entropy and more predictable order flow.