クロード・シャノンによる誤り確率ゼロ容量：定義、グラフ理論との関連、そしてその意義
はじめに：情報伝送の究極の信頼性を求めて
情報理論におけるチャネル容量は、ノイズのある通信路を通じて信頼性高く伝送可能な情報の最大レートを示す、最も基本的な概念の一つです。クロード・シャノンは、1948年の画期的な論文「A Mathematical Theory of Communication」において、ノイズのあるチャネル符号化定理（直接定理および逆定理）を証明し、誤り確率を任意に小さくすることができるレートの上限としてチャネル容量 $C$ を定義しました。この定理は、符号語長を十分長くすれば、容量以下のレートであれば誤り確率をゼロに近づけることが可能であることを示唆しています。
しかし、シャノンは後の1957年の論文「Zero Error Capacity of a Noisy Channel」において、誤り確率を「任意に小さくする」のではなく、「厳密にゼロにする」という、より厳しい条件の下での情報伝送レートの限界を考察しました。これが「誤り確率ゼロ容量 ($C_0$)」の概念です。本稿では、この誤り確率ゼロ容量の定義、通常のチャネル容量 $C$ との違い、この概念が持つ独自の数学的構造、特にグラフ理論との深いつながり、そして情報理論におけるその後の発展に与えた影響について掘り下げていきます。
誤り確率ゼロ容量 $C_0$ の定義とその意味
通常のチャネル容量 $C$ は、符号語長 $n \to \infty$ の極限において、ブロック誤り確率 $P_e^{(n)}$ を任意に $\epsilon > 0$ 以下に小さくできる最大の伝送レート $R$ として定義されます。すなわち、任意の $\epsilon > 0$ に対して、レート $R < C$ で $P_e^{(n)} \le \epsilon$ となるような符号系列構成法が存在します。
一方、誤り確率ゼロ容量 $C_0$ は、より厳格な条件の下で定義されます。レート $R$ が誤り確率ゼロ容量以下であるとは、符号語長 $n$ が十分大きいときに、ブロック誤り確率が「厳密にゼロ」、すなわち $P_e^{(n)} = 0$ となるような符号系列構成法が存在する最大のレート $R$ を指します。
数学的に表現すると、離散無記憶チャネル (DMC) を考えます。入力アルファベット $\mathcal{X}$、出力アルファベット $\mathcal{Y}$、そして遷移行列 $P(y|x)$ で定義されます。符号語長 $n$ の符号帳は、メッセージ集合 ${1, \dots, M}$ と、各メッセージ $i$ に対応する長さ $n$ の符号語 $x^n(i) \in \mathcal{X}^n$ のペア ${ (i, x^n(i)) }{i=1}^M$ からなります。復号器は、受信系列 $y^n \in \mathcal{Y}^n$ を観測して、メッセージ $\hat{i} \in {1, \dots, M}$ を決定します。このとき、符号語 $x^n(i)$ が送信された場合に受信系列が $y^n$ となる確率 $P(y^n | x^n(i)) = \prod{k=1}^n P(y_k | x_k(i))$ を用います。
誤り確率が厳密にゼロであるとは、任意の異なるメッセージ $i \ne j$ について、符号語 $x^n(i)$ を送信した際に受信されうる系列の集合と、符号語 $x^n(j)$ を送信した際に受信されうる系列の集合が完全に分離可能であること、すなわち交差する部分がないことを意味します。具体的には、任意の $i \ne j$ に対して、$P(y^n | x^n(i)) > 0$ かつ $P(y^n | x^n(j)) > 0$ となるような $y^n$ が存在しないことです。このような条件を満たす符号帳 ${x^n(i)}$ を、「誤り確率ゼロ符号 (zero-error code)」と呼びます。
誤り確率ゼロ符号帳のサイズ $M$ が与えられたとき、そのレートは $R = \frac{1}{n} \log_2 M$ となります。誤り確率ゼロ容量 $C_0$ は、全ての符号長 $n$ について可能な誤り確率ゼロ符号帳の最大サイズ $M_n$ を考えたとき、そのレート $\frac{1}{n} \log_2 M_n$ の漸近的最大値として定義されます。 $$ C_0 = \limsup_{n \to \infty} \frac{1}{n} \log_2 M_n $$ ここで $M_n$ は、符号長 $n$ の誤り確率ゼロ符号帳として構成可能な最大語数です。
明らかに、$C_0 \le C$ が成り立ちます。誤り確率を厳密にゼロに保つという制約は、任意に小さくするという制約よりも厳しいため、伝送可能な最大レートは同等かそれ以下になるからです。
グラフ理論との関連：混同グラフと独立集合
シャノンの1957年の論文の核心的な貢献の一つは、誤り確率ゼロ容量の問題をグラフ理論の言葉で定式化したことにあります。
DMCの入力アルファベット $\mathcal{X}$ に対応する頂点集合を持つグラフ $G$ を考えます。このグラフの頂点 $x_1, x_2 \in \mathcal{X}$ の間に辺が存在しないこと（独立であること）を、送信シンボル $x_1$ と $x_2$ が「混同可能 (confusable)」であることと定義します。具体的には、$x_1$ と $x_2$ が混同可能であるとは、ある出力シンボル $y \in \mathcal{Y}$ が存在して、$P(y|x_1) > 0$ かつ $P(y|x_2) > 0$ となる場合です。逆に、辺が存在する場合、つまり $x_1$ と $x_2$ が独立でない（隣接している）場合は、任意の $y$ に対して $P(y|x_1) = 0$ または $P(y|x_2) = 0$ となり、これらのシンボルは決して混同されないことになります。このグラフ $G = (\mathcal{X}, E)$ を、チャネルの「混同グラフ (confusability graph)」と呼びます。
誤り確率ゼロ符号は、符号帳内のどの異なる符号語 $x^n(i)$ と $x^n(j)$ を取っても、受信側でそれらを確実に区別できる必要があります。符号語長 $n$ の符号語 $x^n = (x_1, \dots, x_n)$ と $y^n = (y_1, \dots, y_n)$ が混同可能であるとは、ある受信系列 $z^n$ が存在して $P(z^n | x^n) > 0$ かつ $P(z^n | y^n) > 0$ となる場合です。個々のシンボルレベルでの混同可能性を考えると、$x^n$ と $y^n$ が混同可能であることは、全ての $k=1, \dots, n$ について $x_k$ と $y_k$ がチャネル上で混同可能であることと同値になります。これは、混同グラフの言葉で言うと、ベクトル $x^n$ と $y^n$ の各成分 $(x_k, y_k)$ が混同グラフ $G$ の独立集合（辺がないペア）であること、すなわち $(x_k, y_k) \notin E$ が全ての $k$ について成り立つことと同値です。
符号帳 ${x^n(1), \dots, x^n(M)}$ が誤り確率ゼロ符号であることは、任意の $i \ne j$ に対して、$x^n(i)$ と $x^n(j)$ が混同可能でないことと同値です。これは、混同グラフ $G$ の言葉で言うと、符号語 $x^n(i)$ と $x^n(j)$ の対応するシンボルのペア $(x_k(i), x_k(j))$ の少なくとも一つが $G$ の辺で結ばれていること、すなわち $(x_k(i), x_k(j)) \in E$ となる $k$ が少なくとも一つ存在することと同値です。
ここで、誤り確率ゼロ符号帳の符号語集合 ${x^n(1), \dots, x^n(M)}$ が、長さ $n$ のベクトル空間 $\mathcal{X}^n$ における「強独立集合 (strongly independent set)」を構成することに着目します。強独立集合とは、その集合内のどの異なる2つの要素 $u, v$ についても、 $u$ と $v$ が「混同可能でない」集合のことです。これは、混同グラフ $G$ の直積（デカルト積ではない） $G \boxtimes G \boxtimes \cdots \boxtimes G$ ($n$回) における独立集合に対応します。シャノンはこの直積を「シャノン積 (Shannon product)」と呼び、 $G^n = G \boxtimes G \boxtimes \cdots \boxtimes G$ と表記しました。 $G^n$ の頂点集合は $\mathcal{X}^n$ であり、2つの頂点 $x^n=(x_1, \dots, x_n)$ と $y^n=(y_1, \dots, y_n)$ の間に辺があるのは、少なくとも一つの $k$ について $(x_k, y_k)$ が $G$ の辺である場合です。
誤り確率ゼロ符号帳の最大サイズ $M_n$ は、混同グラフ $G^n$ における最大独立集合のサイズ $\alpha(G^n)$ に等しくなります。したがって、誤り確率ゼロ容量 $C_0$ は次のように表現できます。 $$ C_0 = \limsup_{n \to \infty} \frac{1}{n} \log_2 \alpha(G^n) $$
シャノンの貢献と未解決問題
シャノンは1957年の論文で、このグラフ理論的な定式化を行い、いくつかの特定のチャネルについて $C_0$ を計算しました。例えば、ノイズのないチャネル（混同グラフが完全グラフ）、ノイズが非常に大きいチャネルなどを分析しています。
特に有名なのは、五角形チャネル (pentagon channel) あるいは $C_5$ チャネルと呼ばれる例です。入力アルファベット $|\mathcal{X}|=5$ で、隣接するシンボル同士のみが混同可能であるようなチャネルです。混同グラフは頂点5つのサイクルグラフ $C_5$ となります。
シャノンは、混同グラフ $G$ のクリーク数 $\omega(G)$（最大クリークサイズ）の対数が $C_0$ の単純な下界 $\log_2 \omega(G) \le C_0$ を与えること、および最大独立集合数 $\alpha(G)$ の対数が通常のチャネル容量 $C$ の下界 $\log_2 \alpha(G) \le C$ を与えることを示しました。
しかし、シャノンは $C_0$ の一般的な計算手法を見つけることはできませんでした。特に、混同グラフが $C_5$ の場合の $C_0$ がいくらになるかは、彼の論文発表当時は未解決問題でした。直感的には、長さ1の符号では最大2つのシンボルしか誤りなく区別できないため $M_1=2$ ($R=1$), 長さ2の符号では...と考えがちですが、シャノン積 $\alpha(G^n)$ の性質が複雑で、単純に $\alpha(G)^n$ とはならないからです。
この $C_5$ チャネルの誤り確率ゼロ容量問題は、情報理論および組合せ論における有名な未解決問題となり、多くの研究者を惹きつけました。
ラヴァス数 $\vartheta(G)$ の登場
シャノンの論文発表から20年近く経った1979年、ハンガリーの数学者László Lovászが、グラフ理論における「ラヴァス数 (Lovász number)」または「シータ関数 ($\vartheta(G)$)」を導入し、この問題に画期的な進展をもたらしました。Lovászは、グラフ $G$ のラヴァス数 $\vartheta(G)$ が、最大独立集合数 $\alpha(G)$ とその相補グラフ $\bar{G}$ のクリーク数 $\omega(\bar{G})$（これは $G$ の独立集合数 $\alpha(G)$ に等しい）の間にある不等式 $\omega(\bar{G}) \le \vartheta(G) \le \alpha(G)$ を満たし、さらに重要なことに、グラフのシャノン積に対して $\vartheta(G^n) = \vartheta(G)^n$ という乗法性を持つことを示しました。
この乗法性から、シャノン容量 $C_0 = \limsup_{n \to \infty} \frac{1}{n} \log_2 \alpha(G^n)$ に対して、ラヴァス数の対数 $\log_2 \vartheta(G)$ が重要な上限となることが示されました。 $$ C_0 = \limsup_{n \to \infty} \frac{1}{n} \log_2 \alpha(G^n) \le \frac{1}{n} \log_2 (\vartheta(G)^n) = \log_2 \vartheta(G) $$ さらに、Lovászは $C_5$ グラフに対するラヴァス数が $\vartheta(C_5) = \sqrt{5}$ であることを計算しました。これにより、$C_5$ チャネルの誤り確率ゼロ容量の上限が $\log_2 \sqrt{5} = \frac{1}{2} \log_2 5$ であることが示されました。
シャノンの論文では $C_0(C_5) \ge \log_2 \omega(C_5) = \log_2 2 = 1$ という下限は示されていましたが、Lovászの上限は $\frac{1}{2} \log_2 5 \approx 1.16$ であり、よりタイトな推定値をもたらしました。
最終的に、Lovászのラヴァス数が $C_0$ の厳密な値と一致するケースがあることが示され、特にパーフェクトグラフやいくつかの特殊なグラフクラスについては $C_0 = \log_2 \vartheta(G)$ が成り立つことが証明されました。 $C_5$ グラフもこの範疇に入ることが示され、$C_0(C_5) = \log_2 \sqrt{5}$ が確立されました。
現代の情報科学における意義と関連研究
シャノンによる誤り確率ゼロ容量の導入は、情報理論における符号化限界に関する理解を深める上で非常に重要でした。通常のチャネル容量が「ほとんど誤りなく」伝送可能な最大レートを示すのに対し、$C_0$ は「完全に誤りなく」伝送可能なレートの究極的な限界を示します。この区別は、異なる信頼性基準の下での通信システムの設計において重要な意味を持ちます。
また、この概念は情報理論とグラフ理論の間の強力なつながりを確立しました。グラフの積に対する独立集合数という組合せ論的な問題が、通信路の容量という情報理論的な問題と直接的に結びついたことは、学際的な研究の強力な推進力となりました。
Lovász数 $\vartheta(G)$ は、その後、組合せ最適化、半正定値計画法 (Semidefinite Programming) など、様々な分野で応用される重要なグラフ不変量となりました。 $C_0$ の計算問題は、一般的には非常に困難な問題（NP困難であることが示されています）ですが、$\vartheta(G)$ は多項式時間で近似計算が可能であり、これは理論的な意義とともに、現実的な問題へのアプローチにおいても重要です。
誤り確率ゼロ容量の研究は、情報の信頼性保証、特に極めて高い信頼性が要求されるシステム（例：量子通信の一部の側面、安全保障関連の通信など）の理論的限界を理解する上で今日も関連性を保っています。また、グラフ理論との接点を通じて、情報理論の枠を超えた数学的な構造への洞察を提供し続けています。
結論
クロード・シャノンによる誤り確率ゼロ容量の概念は、ノイズのある通信路における情報の伝送限界に関する彼の深い探求の一例です。通常のチャネル容量が漸近的な誤り確率に着目するのに対し、$C_0$ は厳密にゼロの誤り確率を要求するという、より厳しい条件下での限界を定式化しました。
この概念の導入は、問題をグラフ理論の言葉で表現することの有効性を示し、チャネルの混同グラフとそのシャノン積における最大独立集合の問題へと帰着させました。特に五角形チャネルの例は、その後のラヴァス数 $\vartheta(G)$ の発見に繋がり、情報理論とグラフ理論、そして組合せ最適化の分野に大きな影響を与えました。
シャノンの誤り確率ゼロ容量に関する研究は、情報理論が単なる工学的な問題解決ツールに留まらず、深い数学的な構造を探求する学問分野でもあることを改めて示しています。 $C_0$ の正確な計算は一般には困難な問題ですが、この概念を通じて得られた理論的な洞察と、それがグラフ理論にもたらした発展は、現代の情報科学とその関連分野において今日も重要な意義を持っています。
本稿では、誤り確率ゼロ容量の基本的な概念とグラフ理論との関連、そしてラヴァス数による進展の概要を述べました。このテーマの数学的な深さや、特定のチャネルに対する $C_0$ の具体的な計算例（例えば、Lovászによる $C_5$ の計算の詳細など）については、専門の文献や Lovász の原論文を参照されることをお勧めします。シャノンの独創的な発想が、いかに多様な分野に影響を与え続けているかを示す好例と言えるでしょう。