平均情報量の逆算

「ミリバイト (mili byte)」みたいな概念って考えられるんだろうか。

https://mathtod.online/@cmplstofB/111051925559841823

とのことで、1millibyteの平均情報量を持つ2事象からなる情報源を計算してみます。

平均情報量

平均情報量は以下の式で定義されます。単位をビットに合わせるために $\log 2$ で割っています。

$$H(X) = - \frac{1}{\log 2} \sum_{x \in X} p(x)\log p(x)$$

2事象からなる情報源の場合、片方の事象が起きる確率を $p$ とおくともう一方は $1-p$ となり、以下の式で求められます。

$$H(p) = - \frac{1}{\log 2} (p\log p + (1 - p)\log (1-p))$$

この関数の定義域は $(0, 1)$ ですが、 $H(0) = H(1) = 0$ とすることで $[0, 1]$ に連続に拡張されます。

定義域を $[0, \frac{1}{2}]$ に制限すれば単調となり、逆関数 $H^{-1}\colon [0, 1] \to [0, \frac{1}{2}]$ が定義されます。

平均情報量の微分

log側の微分が2項で打ち消し合い、以下の結果になります。 (定義域は $(0, 1)$)

$$H'(p) = - \frac{1}{\log 2} (\log p - \log (1 - p))$$

ただ、これをそのままNewton法に突っ込むと定義域からはみ出してしまって困るので、別の方法を考えます。

$H(\exp(t))$ で計算

定義域を広げるために指数関数をはさみます。つまり、 $H(p) = b$ となる $p \in [0, \frac{1}{2}]$ を計算するために、まず $H(\exp(t)) = b$ となる $t \in [-\infty, -\log 2]$ をNewton法で求めることを考えます。この関数の微分は

$$H(\exp(t)) = H'(\exp(t))H(\exp(t))$$

なので容易に計算可能です。またこの関数は今回のように小さい目的値に関してはいい感じに振る舞います。

Newton法をサクッと回す

手近な道具で書いてみます。答えが求まればいいので色々適当です。

なお、最初に与えられたお題は "millibyte" のため、求めるべきビット数は 8 / 1024 = 1/128 bit です。

def info(p)
  return 0.0 if p == 0.0 || p == 1.0

  -(p * Math.log2(p) + (1 - p) * Math.log2(1 - p))
end

def info_d(p)
  -(Math.log2(p) - Math.log2(1 - p))
end

# (info(exp(x)))' = info_d(exp(x)) * info(exp(x))

def inv_info(b)
  logx = Math.log(0.25)

  loop do
    logx1 = logx - (info(Math.exp(logx)) - b) / (info_d(Math.exp(logx)) * info(Math.exp(logx)))
    # p [logx, logx1]
    break if (logx - logx1).abs < logx.abs * 1e-15

    logx = logx1
  end
  Math.exp(logx)
end

p inv_info(8.0 / 1024)

0.0006493695901470175 が出力されました。この確率でtrueを返す情報源の平均情報量はおよそ1millibyteということになります。