Author: James L. Massey
publication: IEEE, 1994
Abstract: It is shown that the average number of successive guesses, \(E[G]\), required an optimum strategy until one correrctly guesses the value of a discrete random \(X\), is underbounded by the entropy \(H(X)\) in the manner \(E[G] \ge (1/4)^{H(X)} + 1\) provided that \(H(X) \ge 2\)bits. This bound is tight within a factor of \((4/e)\) when \(X\) is eometrically distributed. It is further shown that \(E(G)\) may be arbitrarily large when \(H(X)\) is an arbitrarily small positive number so that there is no interesting upper bound on \(E(G)\) in terms of \(H(X)\).
连续猜测平均值的上下限与熵的关系。
| 符号 | 符号说明 |
|---|---|
| \(X\) | 离散随机值 |
| \(G\) | 成功猜测X的最小次数 |
| \(E[G], A\) | G的期望 |
| \(p\) | 每次猜测的概率 |
| \(H(X)\) | X的熵 |
| \(P_{geom}\) | 几何分布 |
| \(h(P_{geom})\) | 几何分布的熵 |
下限的确定
对于每次猜测\(X\)的概率\(p=(p_1,p_2,p_3,...)\)满足\(p_1 > p_2 > p_3 > ...\)，此时我们 可以称其为单调分布。\(G\)的期望\(E[G] = \sum i \cdot p_i\), 期望的范围是$[1,) $.
期望的范围是\([1, \infty)\)
因为概率和\(p_1+p_2+p_3+... = 1\)，而i从1开始，因此\(\sum i \cdot p_i > 1\)
根据熵的公式\(h(p) = -\sum p_i \cdot log(p_i)\) 和参考文献[1]给出的公式\(p_i = (1/(A-1))(1-1/A)^i\) 可以推出： \[ h(P_{geom}) = log(A-1) + log(1-1/A)^{-A} \]
推导过程
\[ h(P_{geom}) = -\sum (\frac{1}{A-1})(1-\frac{1}{A})^i \cdot log(\frac{1}{A-1}) (1-\frac{1}{A})^i \\ = \frac{1}{A-1} \sum i(1-\frac{1}{A})^i \cdot log(A-1)(1-\frac{1}{A})\\ = \frac{1}{A-1} log(A-1)(1-\frac{1}{A}) \cdot \sum i(1-\frac{1}{A})^i\\ = \frac{1}{A-1} log(A-1)(1-\frac{1}{A}) \cdot \frac{1-\frac{1}{A}}{(\frac{1}{A}) ^2}\\ = A log(A-1)(1-\frac{1}{A})\\ = log(A-1) + log(1-\frac{1}{A})^-A \]
随着A的增大，上述等式的右边第二项趋近于\(log(e)\). 并且当\(A=2\)也即\(h(P_{geom}) = 2\)时，上述等式右边第二项\(log(1-\frac{1}{A})^-A = 2\)，换句话讲，当\(h(P_{geom}) \ge 2\)时， \[ A \ge (1/4) \cdot 2^{H(X)} +1 \]
推导过程
\[ h(p) \le log(A-1) +2 \\ log(A-1) \ge h(p) -2 \\ A-1 \ge 2^{h(p)-2} = (1/4) \cdot 2^{h(p)} \\ A \ge (1/4) \cdot 2^{h(p)} +1 \]
又因为\(h(P_{geom}) = log(A-1) + log(1-1/A)^{-A}\)右边第二项最小值为\(log(e)\),因此: \[ h(P_{geom}) \ge log(A-1) + log(e) \] 即: \[ A \le (1/e) \cdot 2^{h(P_{geom})} +1 \]