情報理論
概要
情報理論（information theory）とは、情報源と通信路を確率で表し、エントロピーや相互情報量を使って、情報をどこまで短く表せるか（圧縮）と、雑音のある通信路でどれだけの速さで正確に送れるか（通信）の限界を研究する数学の分野である。圧縮の限界はエントロピーで与えられ、無記憶な通信路では、通信路容量 $C=\max I(X;Y)$ を超える速さの符号は、Fano の不等式により誤りの確率を $0$ に近づけられない（通信路符号化定理の逆）。誤り訂正符号、統計学、確率論と深く結びついている。
情報理論（information theory）は、情報の量を確率で測り、情報をどこまで短く表せるか（圧縮）と、雑音のある通信路を通してどれだけの速さで正確に送れるか（通信）の限界を研究する数学の分野である。中心の量は、確率分布の不確かさを測るエントロピーと、2 つの確率変数が共有する情報を測る相互情報量であり、圧縮の限界はエントロピーで、通信の限界は相互情報量の最大値（通信路容量）で与えられる。
この記事では、エントロピー・相互情報量・通信路・通信路容量を定義し、情報理論の主な問いと代表的な定理を記事とともに一覧にする。続いて、「通信路容量を超える速さでは、どう工夫しても誤りの確率を小さくできない」という通信路符号化定理の逆を、Fano の不等式とともに完全に証明する。2 値対称通信路の容量も計算する。最後に、学ぶ順に記事を並べた道筋を示す。
定義
以下、確率変数はすべて有限集合に値をとるとし、$\log$ は自然対数、$0\log0:=0$ とする（単位は nat。$\log2$ で割ると bit になる）。$p(x):=P(X=x)$ などと書く。
- $X$ の エントロピーを $H(X):=-\sum_xp(x)\log p(x)$ で定める。組 $(X,Y)$ のエントロピーを $H(X,Y)$ と書く。
- $X$ が与えられたときの $Y$ の 条件付きエントロピーを $H(Y\mid X):=\sum_{x:\,p(x)>0}p(x)\,H(Y\mid X=x)$ で定める。$H(Y\mid X=x)$ は、$X=x$ のもとでの $Y$ の条件付き分布のエントロピーである。
- 相互情報量を $I(X;Y):=H(X)+H(Y)-H(X,Y)$ で定める。
これは エントロピー の定義「エントロピー」「同時・条件付きエントロピーと相互情報量」と同じであり、以下では同記事の次の定理を使う。値が $m$ 個なら $0\le H(X)\le\log m$ で、右の等号は一様分布のときに限る（定理「エントロピーの範囲」）。連鎖律 $H(X,Y)=H(X)+H(Y\mid X)$、$I(X;Y)\ge0$（等号は独立のとき）、$H(Y\mid X)\le H(Y)$、関数 $f$ について $H(f(X))\le H(X)$ が成り立つ（定理「連鎖律と劣加法性」）。連鎖律から $I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X)$ である。$X$ の値と $(X,f(X))$ の値は 1 対 1 に対応するので $H(X,f(X))=H(X)$ である。
有限集合 $\mathcal X$（入力）・$\mathcal Y$（出力）と、$W(y\mid x)\ge0$、$\sum_{y}W(y\mid x)=1$（各 $x\in\mathcal X$）を満たす数の族 $W=(W(y\mid x))$ を通信路という。入力 $X$ の分布を $p$ とし、$P(X=x,Y=y)=p(x)W(y\mid x)$ で出力 $Y$ を定める。
$$
C:=\max_pI(X;Y)
$$
を通信路 $W$ の通信路容量という（$p$ は $\mathcal X$ 上のすべての確率分布を動く）。
$I(X;Y)$ は $p$ の連続関数（$t\log t$ の有限和）で、確率分布の全体は $\mathbb R^{\mathcal X}$ の有界閉集合なので、最大値は存在する（この定義は Mac03 の式 (9.10)、p. 150）。通信路を $n$ 回使うとき、入力の列 $x^n=(x_1,\dots,x_n)$ に対して出力の列 $y^n$ が確率
$$
W^n(y^n\mid x^n):=\prod_{i=1}^nW(y_i\mid x_i)
$$
で出るとき、通信路は無記憶であるという。各回の雑音が互いに独立で、過去の入出力によらない場合である。
情報理論とは、情報源・通信路を確率で表し、エントロピー・相互情報量などの量を使って、情報の表現・圧縮・伝送とその限界を研究する分野である。
$0\le\varepsilon\le1$ とし、$\mathcal X=\mathcal Y=\{0,1\}$、$W(y\mid x)=1-\varepsilon$（$y=x$）、$W(y\mid x)=\varepsilon$（$y\ne x$）とする（各ビットが確率 $\varepsilon$ で反転する通信路）。$h(t):=-t\log t-(1-t)\log(1-t)$ とおくと、通信路容量は
$$
C=\log2-h(\varepsilon)
$$
である。実際、$X=x$ のもとで $Y$ の分布は $(1-\varepsilon,\varepsilon)$ の並べ替えなので $H(Y\mid X=x)=h(\varepsilon)$、したがって $H(Y\mid X)=h(\varepsilon)$ で、$I(X;Y)=H(Y)-h(\varepsilon)\le\log2-h(\varepsilon)$ である。$X$ を一様分布にとると $P(Y=0)=\frac12(1-\varepsilon)+\frac12\varepsilon=\frac12$ で $H(Y)=\log2$ となり、等号が成り立つ。たとえば $\varepsilon=0.1$ なら $C\approx0.693147-0.325083=0.368064$ nat、すなわち約 $0.531$ bit である。$\varepsilon=\frac12$ なら $C=0$ で、出力は入力と独立になる。
情報理論の主な問い
- 情報の量を測る。 不確かさをエントロピーで、2 つの量が共有する情報を相互情報量で、2 つの分布の違いを Kullback–Leibler 情報量で測る。基本性質はすべて Gibbs の不等式（Kullback–Leibler 情報量は $0$ 以上）から出る（エントロピー）。
- どこまで圧縮できるか（情報源符号化）。 接頭符号の符号語の長さは、二分木の葉の深さの不等式（二分木 の定理「葉の深さの不等式」）に従い、ここから 1 記号あたりの平均の長さはエントロピー（bit 単位）以上で、まとめて符号化すればいくらでもそれに近づけられる（エントロピー の定理「記号ごとの符号の平均の長さ」と系）。独立な試行の結果は、ほぼ確実に約 $e^{nH}$ 個の「典型的な列」のどれかになる（同記事の定理「典型的な列の個数」）。
- 雑音のある通信路でどれだけ送れるか（通信路符号化）。 無記憶な通信路では、通信路容量より小さい速さなら誤りの確率をいくらでも小さくでき、容量より大きい速さではできない。後半は下で証明する。
- 誤りをどう直すか（符号の構成）。 符号語どうしの Hamming 距離を大きくとると誤りを訂正できる。Hamming 符号はその基本例である（誤り訂正符号）。
- 確率・統計との関係。 エントロピーは大数の法則を通じて典型的な列の個数を数え、Kullback–Leibler 情報量は分布の推定や検定で 2 つの分布の見分けやすさを測る（統計学）。
代表的な定理
| 定理 | 主張の要点 | 記事 |
|---|---|---|
| Gibbs の不等式 | Kullback–Leibler 情報量は $0$ 以上で、$0$ になるのは 2 つの分布が等しいときに限る | エントロピー |
| 連鎖律と劣加法性 | $H(X,Y)=H(X)+H(Y\mid X)\le H(X)+H(Y)$ | エントロピー |
| 葉の深さの不等式（Kraft の不等式） | 二分木の葉の深さ $d_i$ は $\sum_i2^{-d_i}\le1$ を満たし、逆にこれを満たす深さは葉の深さとして実現される（接頭符号の符号語の長さの条件） | 二分木 |
| 情報源符号化 | 接頭符号の平均の長さは $H_2$ 以上で、$H_2+1$ 未満にできる | エントロピー |
| 典型的な列 | 独立な $n$ 回の試行の結果は確率 $1-\frac{\sigma^2}{n\varepsilon^2}$ 以上で典型的な列になり、その個数は $e^{n(H+\varepsilon)}$ 以下、$(1-\frac{\sigma^2}{n\varepsilon^2})e^{n(H-\varepsilon)}$ 以上 | エントロピー |
| Fano の不等式 | 推定の誤りの確率が小さければ、推定値のもとでの条件付きエントロピーも小さい | この記事 |
| 通信路符号化定理の逆 | 容量 $C$ を超える速さでは、誤りの確率は $0$ に近づかない | この記事 |
| 通信路符号化定理（Shannon） | 容量未満の速さなら、誤りの確率をいくらでも小さくできる | この記事で言明のみ |
| Hamming 符号 | 長さ $7$・符号語 $16$ 個の符号で、最小距離が $3$ なので 1 か所の誤りを訂正できる | 誤り訂正符号 |
通信路符号化定理の前半（容量未満の速さで誤りを小さくできること）は、ランダムに選んだ符号の誤りの確率の平均を評価して証明される。その言明と証明は Mac03 §10.1（p. 162）以降の第 10 章にあり、この記事では証明しない。
代表例：通信路符号化定理の逆
符号と誤りの確率
$M\ge2$ 個のメッセージ $\{1,\dots,M\}$ を、無記憶な通信路 $W$ を $n$ 回使って送る。符号とは、符号化の写像 $F\colon\{1,\dots,M\}\to\mathcal X^n$ と復号の写像 $g\colon\mathcal Y^n\to\{1,\dots,M\}$ の組である。メッセージ $U$ を $\{1,\dots,M\}$ 上の一様分布に従う確率変数とし、$X^n:=F(U)$ を送り、受け取った $Y^n$ から $\hat U:=g(Y^n)$ と推定する。ここで
$$
P(U=u,\ Y^n=y^n)=\frac1M\,W^n\bigl(y^n\mid F(u)\bigr)
$$
である。$P_e:=P(\hat U\ne U)$ を誤りの確率、$R:=\frac{\log M}n$（nat）を符号の速さという。速さは、通信路を 1 回使うごとに送れる情報の量である。
2 つの補題
$A,B$ を確率変数、$g$ を関数とすると、$H(A\mid B)\le H(A\mid g(B))$ である。
$Z:=g(B)$ とおき、$P(Z=z)>0$ となる $z$ を固定する。条件付き確率 $Q:=P(\cdot\mid Z=z)$ のもとで エントロピー の定理「連鎖律と劣加法性」の 3 を使うと
$$
\sum_{b:\,g(b)=z,\ P(B=b)>0}Q(B=b)\,H_Q(A\mid B=b)\le H_Q(A)=H(A\mid Z=z)
$$
である（$H_Q$ は $Q$ のもとで計算したエントロピー）。$g(b)=z$ なら $\{B=b\}\subset\{Z=z\}$ なので、$Q$ のもとでの $B=b$ に関する条件付き分布は $P$ のもとでのものと同じで、$H_Q(A\mid B=b)=H(A\mid B=b)$、$Q(B=b)=P(B=b)/P(Z=z)$ である。両辺に $P(Z=z)$ を掛けて $z$ について足すと、左辺は $\sum_{b:\,P(B=b)>0}P(B=b)H(A\mid B=b)=H(A\mid B)$、右辺は $H(A\mid Z)$ になる。$\square$
$U,\hat U$ を $M$ 個（$M\ge2$）の元からなる同じ集合に値をとる確率変数とし、$P_e:=P(\hat U\ne U)$ とする。このとき
$$
H(U\mid\hat U)\le h(P_e)+P_e\log(M-1)\le\log2+P_e\log(M-1)
$$
である。ここで $h(t)=-t\log t-(1-t)\log(1-t)$ である。
$E$ を、$\hat U\ne U$ なら $1$、$\hat U=U$ なら $0$ とする確率変数とする。$E$ は $(U,\hat U)$ の関数なので $H(U,\hat U)=H(U,\hat U,E)$ であり、連鎖律を 2 回使うと
$$
H(U\mid\hat U)=H(U,\hat U,E)-H(\hat U)=\bigl[H(E,\hat U)-H(\hat U)\bigr]+H(U\mid E,\hat U)=H(E\mid\hat U)+H(U\mid E,\hat U)
$$
である。第 1 項は $H(E\mid\hat U)\le H(E)=h(P_e)$ である。第 2 項は $\sum_{(e,v)}P(E=e,\hat U=v)\,H(U\mid E=e,\hat U=v)$ であり、$e=0$ なら $U=v$ に決まるので $H(U\mid E=0,\hat U=v)=0$、$e=1$ なら $U$ は $v$ 以外の $M-1$ 個の値しかとらないので $H(U\mid E=1,\hat U=v)\le\log(M-1)$ である（エントロピー の定理「エントロピーの範囲」）。よって第 2 項は $P(E=1)\log(M-1)=P_e\log(M-1)$ 以下である。最後に $h(P_e)\le\log2$（同じ定理を値が 2 個の $E$ に使う）。$\square$
推定の誤りが少なければ、推定値を知ったあとに残る不確かさ $H(U\mid\hat U)$ も小さい、というのが Fano の不等式の意味である。
定理と証明
通信路容量 $C$ の無記憶な通信路を $n$ 回使う、メッセージ $M\ge2$ 個の符号について、一様分布のメッセージに対する誤りの確率は
$$
P_e\ge1-\frac{nC+\log2}{\log M}=1-\frac CR-\frac{\log2}{nR}
$$
を満たす（$R=\frac{\log M}n$）。とくに、$R_0>C$ を固定し、$n=1,2,\ldots$ について速さが $R_0$ 以上の符号を選ぶと、それらの誤りの確率は $\liminf_{n\to\infty}P_e\ge1-\frac C{R_0}>0$ を満たし、$0$ に近づかない。
1. 相互情報量で書く。 $U$ は一様分布なので $H(U)=\log M$ であり、$\log M=H(U\mid Y^n)+I(U;Y^n)$ である。
2. 復号は情報を増やさない。 $\hat U=g(Y^n)$ なので、lem-it-coarsen により $H(U\mid Y^n)\le H(U\mid\hat U)$ であり、thm-it-fano と $\log(M-1)< \log M$ から $H(U\mid Y^n)\le\log2+P_e\log M$ である。
3. 符号化は $X^n$ を通してしか効かない。 $U=u$ のもとでの $Y^n$ の分布は $W^n(\cdot\mid F(u))$ で、$F(u)$ だけで決まる。$\{X^n=x^n\}$ は $F(u)=x^n$ となる $u$ についての $\{U=u\}$ の和なので、$P(X^n=x^n)>0$ なら $X^n=x^n$ のもとでの $Y^n$ の分布も $W^n(\cdot\mid x^n)$ である。よって $\phi(x^n):=H(Y^n\mid X^n=x^n)$ とおくと $H(Y^n\mid U=u)=\phi(F(u))$ であり、
$$
H(Y^n\mid U)=\sum_u\frac1M\phi(F(u))=\sum_{x^n}P(X^n=x^n)\,\phi(x^n)=H(Y^n\mid X^n)
$$
である。したがって $I(U;Y^n)=H(Y^n)-H(Y^n\mid U)=H(Y^n)-H(Y^n\mid X^n)=I(X^n;Y^n)$ である。
4. 無記憶なら 1 回ずつの和で抑えられる。 $X^n=x^n$ のもとで $Y_1,\dots,Y_n$ は互いに独立で、$Y_i$ の分布は $W(\cdot\mid x_i)$ である（$W^n$ が積の形だから）。独立な組のエントロピーは和になる（エントロピー の定理「連鎖律と劣加法性」の 2 の等号の場合を繰り返し使う）ので、$\psi(x):=-\sum_yW(y\mid x)\log W(y\mid x)$ とおくと $\phi(x^n)=\sum_i\psi(x_i)$ であり、
$$
H(Y^n\mid X^n)=\sum_{i=1}^n\sum_xP(X_i=x)\,\psi(x)=\sum_{i=1}^nH(Y_i\mid X_i)
$$
である（$W^n$ を $y_j$（$j\ne i$）について足すと $P(X_i=x,Y_i=y)=P(X_i=x)W(y\mid x)$ となるので、$X_i=x$ のもとでの $Y_i$ の分布は $W(\cdot\mid x)$）。一方、劣加法性を繰り返し使うと $H(Y^n)\le\sum_iH(Y_i)$ である。よって
$$
I(X^n;Y^n)\le\sum_{i=1}^n\bigl[H(Y_i)-H(Y_i\mid X_i)\bigr]=\sum_{i=1}^nI(X_i;Y_i)\le nC
$$
である。最後の不等号は、$(X_i,Y_i)$ の同時分布が $P(X_i=x)W(y\mid x)$ の形なので、容量の定義から $I(X_i;Y_i)\le C$ となることによる。
5. まとめる。 1〜4 から $\log M\le\log2+P_e\log M+nC$、すなわち $(1-P_e)\log M\le nC+\log2$ である。$\log M>0$ で割れば主張の不等式になる。速さが $R\ge R_0$ なら右辺は $1-\frac C{R_0}-\frac{\log2}{nR_0}$ 以上で、これは $n\to\infty$ で $1-\frac C{R_0}$ に近づく。$\square$
ex-it-bsc の $\varepsilon=0.1$ の 2 値対称通信路では $C\approx0.531$ bit なので、1 回あたり $1$ bit（$R=\log2$）で送ろうとすると、どんな符号でも誤りの確率は $n$ が大きいとき $1-0.531=0.469$ 程度より小さくできない。
仮定を外すと崩れること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 通信路が無記憶 | $\mathcal X=\mathcal Y=\{0,1\}$ で、確率 $\frac12$ で $0$ か $1$ になる 1 個の $Z$ を全回に共通に使い、$Y_i:=X_i+Z\bmod2$ とする | 1 回ずつ見ると $\varepsilon=\frac12$ の 2 値対称通信路で $C=0$ だが、$x_1=0$ を送って $Z=Y_1$ を知れば、残り $n-1$ 回で $M=2^{n-1}$ 個のメッセージを誤りなく送れる。$n\ge3$ で $P_e=0< 1-\frac{\log2}{(n-1)\log2}$ |
| メッセージが一様分布 | $P(U=1)=1-\delta$ で残りの $M-1$ 個は同じ確率、$g$ はつねに $1$ を返す | 通信路によらず $P_e=\delta$ だが、不等式の右辺は $M\to\infty$ で $1$ に近づく |
1 行目では、雑音が全回で同じなので、1 回目の出力が以後の雑音を教えてしまう。各回の容量だけでは $n$ 回分の相互情報量を抑えられず、手順 4 が成り立たない。2 行目では $H(U)$ が $\log M$ よりずっと小さく、手順 1 の等式 $H(U)=\log M$ が成り立たない。
学ぶ順の道筋
情報理論は、次の順に記事をたどると学べる。
- 準備：確率変数・期待値・条件付き確率、対数関数・凸関数・Jensenの不等式、大数の法則。
- 情報の量：エントロピー（Gibbs の不等式・連鎖律・典型的な列・圧縮の限界）。
- 符号：二分木（葉の深さの不等式と接頭符号）→ 誤り訂正符号（Hamming 距離と Hamming 符号）。有限体の上の線形代数は 有限体。
- 通信：この記事の通信路容量・Fano の不等式・通信路符号化定理の逆。
- 関係する分野：確率論、統計学、Markov連鎖（記憶のある情報源のモデル）。
上の代表例の定理は、2 の エントロピー の基本定理だけから証明できる。
歴史
情報理論は、C. E. Shannon の 1948 年の論文「A Mathematical Theory of Communication」（Bell System Technical Journal 27）に始まり、この論文で分野が作られると同時に、その基本的な問題の多くが解かれた（Mac03 §1.3、p. 14）。誤りの確率と速さのどの組が実現できるかという問いはこの論文が立てたものであり、容量に迫る具体的な符号の構成は、その後の符号理論の中心の問題になった。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
