通信路の相対エントロピーと、通信の効率の理論をつなぐ上で最も重要な定理の一つがファノの不等式（ファノ限界）です。この不等式は、通信路の相対エントロピー（不確かさ）を用いて、復号誤り率の限界を与えてくれます。
送信者と受信者はやりとりしたいメッセージのパターン \(\mathcal{M} = \{1, 2, \cdots, n\}\) があるとします。
入力記号を \(\mathcal{X}\)、出力記号を \(\mathcal{Y}\)、通信路行列を \(\mathbf{P} \in \mathbb{R}^{\mathcal{X} \times \mathcal{Y}}\) とする通信路を用いて通信することを考えます。すなわち、この通信路に記号 \(x \in \mathcal{X}\) を入力すると、確率 \(\mathbf{P}_{xy} = P(Y = y \mid X = x)\) で記号 \(y \in \mathcal{Y}\) が出力されます。
符号化関数を \(f\colon \mathcal{M} \to \mathcal{X}\)、復号関数を \(g\colon \mathcal{Y} \to \mathcal{M}\) とします。送信者がメッセージ \(m \in \mathcal{M}\) を送信する際には、\(f(m)\) と入力記号に符号化し、\(f(m)\) を通信路に入力します。受信者は受信記号 \(y \in \mathcal{Y}\) に対して \(g(y)\) と復号します。\(m = g(y)\) となれば通信成功です。
この設定では、各メッセージは単一の入力記号に符号化されることに注意してください。
符号化・復号 \(f, g\) を工夫すると、通信が失敗する確率 \(P_{\text{error}} = \frac{1}{n} \sum_{m \in \mathcal{M}} p(m \neq g(y) \mid M = m)\) はどこまで小さくできるでしょうか。
ファノの不等式は以下のように、通信路の相対エントロピーを使って復号誤り率の下界を導きます。
任意の符号化関数 \(f\colon \mathcal{M} \to \mathcal{X}\)、復号関数 \(g\colon \mathcal{Y} \to \mathcal{M}\) について、$$H(X \mid Y) \le – P_{\text{error}} \log_2 P_{\text{error}} – (1 – P_{\text{error}}) \log_2 (1 – P_{\text{error}}) + P_{\text{error}} \log_2 |\mathcal{X}|$$ が成り立つ。ただし、\(0 \log_2 0 = 0\) とする。特に、任意の \(x \in [0, 1]\) について \(-x \log_2 x – (1 – x) \log_2 (1 – x) \le 1\) であるので、$$H(X \mid Y) \le 1 + P_{\text{error}} \log_2 |\mathcal{X}|$$ が成り立つ。
ファノの定理より、通信路の曖昧さ \(H(X \mid Y)\) がある程度大きいと、復号誤り率 \(P_{\text{error}}\) は小さくできないことが分かります。
また、ひとつ目の不等式より、\(P_{\text{error}} = 0\) であれば \(H(X \mid Y) = 0\) であること、つまり曖昧性は一切ない通信路である必要があることが分かります。
メッセージの確率変数を \(M\)、入力記号の確率変数を \(X = f(M)\)、出力記号の確率変数を \(Y\)、\(E\) を \(M = g(Y)\) のとき \(0\) をとり、 \(M \neq g(Y)\) のとき \(1\) をとる確率変数とする。 このとき、\(P_{\text{error}} = P(E = 1)\) である。
$$\begin{align*}H(X \mid Y) &\stackrel{(a)}{\le} H(X \mid Y) + H(E \mid X, Y) \\ &\stackrel{(b)}{=} \mathbb{E}[-\log_2 P(X \mid Y) – \log_2 P(E \mid X, Y)] \\ &\stackrel{(c)}{=} \mathbb{E}[-\log_2 \left(P(X \mid Y) P(E \mid X, Y)\right)] \\ &\stackrel{(d)}{=} \mathbb{E}[-\log_2 P(E, X \mid Y)] \\ &\stackrel{(e)}{=} \mathbb{E}[-\log_2 \left(P(X \mid E, Y) P(E \mid Y)\right)] \\ &\stackrel{(f)}{=} \mathbb{E}[-\log_2 P(X \mid E, Y)] + \mathbb{E}[- \log P(E \mid Y)] \\ &\stackrel{(h)}{=} \mathbb{E}[-\log_2 P(X \mid E, Y)] + H(E \mid Y) \\ &\stackrel{(i)}{\le} \mathbb{E}[-\log_2 P(X \mid E, Y)] + H(E) \\ &\stackrel{(j)}{=} P(E = 0) \mathbb{E}[-\log_2 P(X \mid Y, E = 0)] \\ &\qquad + P(E = 1) \mathbb{E}[-\log_2 P(X \mid Y, E = 1)] \\ & \qquad + H(E) \\ &\stackrel{(k)}{=} P(E = 0) H(X \mid Y, E = 0) \\ & \qquad + P(E = 1) H(X \mid Y, E = 1) \\ & \qquad + H(E) \\ &\stackrel{(l)}{=} 0 + P(E = 1) H(X \mid Y, E = 1) + H(E) \\ &\stackrel{(m)}{=} P_{\text{error}} H(X \mid Y, E = 1) + H(E) \\ &\stackrel{(n)}{\le} P_{\text{error}} \log |\mathcal{X}| + H(E) \\ &\stackrel{(o)}{=} – P_{\text{error}} \log_2 P_{\text{error}} – (1 – P_{\text{error}}) \log_2 (1 – P_{\text{error}}) + P_{\text{error}} \log_2 |\mathcal{X}| \end{align*}$$
ここで、(a) は エントロピーの非負性より、(b) は エントロピーの定義より、(c) は対数の性質より、(d) と (e) は確率の乗法定理より、(f) は対数の性質より、(h) はエントロピーの定義より、(i) は条件付きエントロピーとエントロピーの不等式より、(j) は条件付き期待値の展開より、(k) はエントロピーの定義より、(l) は \(E = 0\) のとき、\(X = f(g(Y))\) と決定的に定まる変数となりエントロピーが \(0\) となるため、(m) は \(P_{\text{error}} = P(E = 1)\) より、(n) は \(X\) の取りうる値が \(|\mathcal{X}|\) 種類であるため、(o) はエントロピーの定義と \(P_{\text{error}} = P(E = 1)\) より従う。
また、\(-x \log_2 x – (1 – x) \log_2 (1 – x)\) を微分すると、凹関数であり、\(x = \frac{1}{2}\) のとき最大値をとり、そのときの値が \(1\) となることが分かる。よって、$$H(X \mid Y) \le 1 + P_{\text{error}} \log_2 |\mathcal{X}|$$ が成り立つ。
- ファノの不等式は、通信路の確率分布から、復号誤り率の下界を求める不等式
