グラフ理論の視点から見るシャノンの誤り確率ゼロ容量：その定義、計算、そしてLovasz数の源流
誤り確率ゼロ容量とは：グラフ理論との意外な接点
クロード・シャノンの情報理論は、通信システムにおける情報伝送の可能性と限界を数学的に定式化しました。特に有名なのが、ノイズのある通信路における信頼性のある通信が可能となる最大のレートを示すチャネル容量の概念です。これは通常、微小な誤り確率を許容した場合の漸近的な限界として定義されます。
しかし、シャノンは後に、符号長を限りなく長くしてもなお、誤り確率を厳密にゼロに保つことが可能な最大の通信レートを考察しました。これが「誤り確率ゼロ容量」（Zero Error Capacity）$C_0$ の概念です。この概念は、彼の1957年の論文 "Zero error capacity of a noisy channel" で詳細に論じられています。そして、この $C_0$ の計算は、一見情報理論とは無関係に思えるグラフ理論と深く結びつくことになります。
本稿では、シャノンの誤り確率ゼロ容量の概念を、特にグラフ理論的な視点から掘り下げます。誤り確率ゼロ容量がどのように定義され、グラフの性質と関連付けられるのか、シャノンが直面した計算の難しさ、そしてその後の研究、特にLovasz数の導入へと繋がる道筋を追います。
誤り確率ゼロ容量の定義と混同グラフ
離散的な通信路を考えます。入力アルファベット $\mathcal{X}$、出力アルファベット $\mathcal{Y}$、そして遷移確率 $P(y|x)$ で特徴付けられるとします。通信路にはノイズが存在するため、異なる入力シンボル $x_1, x_2 \in \mathcal{X}$ に対して、出力 $y$ が $P(y|x_1) > 0$ かつ $P(y|x_2) > 0$ となる場合があります。このような場合、受信者は $y$ を観測したときに、送られたのが $x_1$ なのか $x_2$ なのかを確実に区別することはできません。
誤り確率をゼロにするためには、送られた可能性のある全ての入力シンボルについて、受信者が完全に区別できるような符号語を選択する必要があります。つまり、ある符号 $C \subseteq \mathcal{X}^n$（長さ $n$ の符号語の集合）内の任意の異なる2つの符号語 $\mathbf{x}_1, \mathbf{x}_2 \in C$ に対して、受信者はそれらを確実に区別できなければなりません。
これは、$\mathbf{x}_1$ を送ったときに出力される可能性のある全ての出力集合と、$\mathbf{x}_2$ を送ったときに出力される可能性のある全ての出力集合が、完全に互いに素でなければならないことを意味します。すなわち、ある出力系列 $\mathbf{y} \in \mathcal{Y}^n$ が存在して $P(\mathbf{y}|\mathbf{x}_1) > 0$ かつ $P(\mathbf{y}|\mathbf{x}_2) > 0$ となるような $\mathbf{x}_1, \mathbf{x}_2 \in C, \mathbf{x}_1 \ne \mathbf{x}_2$ は存在してはならないということです。
この条件をグラフ理論の言葉で表現するために、「混同グラフ」（Confusability Graph）、あるいは「混乱グラフ」（Confusion Graph）と呼ばれるグラフ $G$ を定義します。グラフ $G$ の頂点集合は入力アルファベット $\mathcal{X}$ そのものです。辺は、通信路を一回通過した際に出力が混同されうる入力シンボルのペア $(x_1, x_2)$ の間に引かれます。すなわち、$x_1, x_2 \in \mathcal{X}, x_1 \ne x_2$ の間に辺が存在するのは、ある出力 $y \in \mathcal{Y}$ が存在して $P(y|x_1) > 0$ かつ $P(y|x_2) > 0$ となる場合です。
長さ $n$ の符号語を考える場合、これは $n$ 回通信路を使用することに対応します。この場合の混同グラフは、単一の通信路の混同グラフ $G$ の $n$ 個の「積」として表現されます。シャノンは、この積として、独立に使用される通信路をモデル化する場合にはグラフの「強積（strong product）」を用いるのが適切であることを示しました。$G$ の $n$ 個の強積を $G^n$ と表記します。
誤り確率ゼロ符号 $C \subseteq \mathcal{X}^n$ の条件は、その符号語集合 $C$ がグラフ $G^n$ の独立集合（Independent Set）でなければならないことを意味します。独立集合とは、どの2つの頂点間にも辺が存在しないような頂点の集合です。独立集合内の頂点は互いに混同されないため、それぞれの頂点（符号語）に対応する出力を観測したときに、誤りなく区別できるわけです。
長さ $n$ の誤り確率ゼロ符号の最大サイズは、グラフ $G^n$ の最大独立集合のサイズ $\alpha(G^n)$ に等しくなります。符号のレートは $\frac{1}{n} \log_2 |C|$ ですから、誤り確率ゼロ容量 $C_0(G)$ は、可能な最大のレートの極限値として定義されます。
$C_0(G) = \sup_n \frac{1}{n} \log_2 \alpha(G^n) = \lim_{n \to \infty} \frac{1}{n} \log_2 \alpha(G^n)$
ここで、極限が存在することは、$\alpha(G^{m+n}) \ge \alpha(G^m) \alpha(G^n)$ という性質（強積の独立集合に関する劣乗法性）から導かれます（正確には $\log \alpha(G^n)$ に関する劣加法性 $\log \alpha(G^{m+n}) \le \log \alpha(G^m) + \log \alpha(G^n)$ ですが、この場合は積性が成り立ちます）。
容量計算の難しさ：積グラフの独立集合
誤り確率ゼロ容量 $C_0(G)$ は、グラフ $G$ の最大独立集合のサイズ $\alpha(G)$ と密接に関係していますが、$C_0(G)$ は単純に $\log_2 \alpha(G)$ ではありません。なぜなら、$\alpha(G^n)$ は一般に $\alpha(G)^n$ よりも速く成長しうるからです。
例えば、5-サイクルグラフ $C_5$ を考えます。$C_5$ は頂点が5つ連なり、両端が繋がったグラフです。独立集合の最大サイズは $\alpha(C_5) = 2$ です（互いに隣接しない最大2つの頂点を選べます）。したがって、naive に考えれば $C_0(C_5) = \log_2 2 = 1$ となりそうですが、シャノンは $C_0(C_5) = \log_2 \sqrt{5}$ であることを示しました。これは $\log_2 \alpha(C_5) = 1$ よりも大きい値です。
$C_5$ の例は、$\alpha(G^n)$ を計算することの難しさ、ひいては $C_0(G)$ の計算の難しさを浮き彫りにしました。一般のグラフ $G$ に対して $\alpha(G)$ を計算することはNP困難な問題として知られており、その積グラフ $G^n$ の独立集合数を計算することも非常に困難です。シャノンの定義は理論的には明確でしたが、具体的なグラフに対する容量の計算は困難な課題として残されました。
Lovasz数の導入とその意義
シャノンが提示した誤り確率ゼロ容量の計算問題、特に積グラフ $G^n$ の独立集合数の漸近的な振る舞いに関する課題は、その後の数学研究における重要なモチベーションとなりました。
1979年、ラースロー・ロヴァース（László Lovász）は、この問題に対して画期的な貢献をしました。彼は「Lovasz数」または「テータ関数」（$\vartheta(G)$）と呼ばれる新しいグラフ不変量を導入したのです。Lovasz数は、グラフの最大独立集合数 $\alpha(G)$ と、その補グラフ $\bar{G}$ の色数 $\chi(\bar{G})$ という、計算が困難な2つのグラフ不変量の間に位置し、以下の重要な不等式を満たします。
$\alpha(G) \le \vartheta(G) \le \chi(\bar{G})$
さらに重要なことに、Lovasz数はグラフの強積に対して乗法性（multiplicativity）を持ちます。
$\vartheta(G \times H) = \vartheta(G) \vartheta(H)$
したがって、$\vartheta(G^n) = \vartheta(G)^n$ が成り立ちます。この性質から、シャノンの誤り確率ゼロ容量の定義式において、$\alpha(G^n)$ を $\vartheta(G)^n$ で置き換えることで、積の対数の平均が Lovasz 数の対数に収束することが期待できます。
Lovaszは、このLovasz数がシャノンの誤り確率ゼロ容量と完全に一致することを証明しました。すなわち、
$C_0(G) = \log_2 \vartheta(G)$
この結果は、シャノンが定義した抽象的な概念である誤り確率ゼロ容量が、Lovaszによって導入された具体的に計算可能な（半正定値計画問題として解ける）グラフ不変量と等しいことを示した点で非常に重要です。シャノンが情報理論の文脈で提起した難問が、グラフ理論における新しい数学的概念の発見を促し、それが再び情報理論の問題を解決するという、学際的な研究の素晴らしい例と言えます。
現代における意義と応用
シャノンの誤り確率ゼロ容量とLovasz数の研究は、理論的な美しさを持つだけでなく、現代の情報科学や数理科学においても依然として意義を持っています。
- 計算複雑性理論: 最大独立集合数の計算がNP困難であるのに対し、Lovasz数は多項式時間（具体的には半正定値計画問題を解く時間）で計算可能です。このことは、NP困難問題に対する緩和手法や近似アルゴゴリズムの開発において、Lovasz数が重要な役割を果たすことを示唆しています。
- 量子情報理論: Lovasz数は、量子通信路の容量や、非局所ゲームにおける上限の計算など、量子情報理論においても重要なツールとなっています。シャノンの古典的な通信路容量の概念が量子情報においても拡張され、Lovasz数がその分析に貢献しています。
- 組合せ最適化: Lovasz数は、グラフの特性を捉える強力なツールとして、組合せ最適化の分野でも広く研究・応用されています。
シャノンが1957年に提示した誤り確率ゼロ容量の概念は、単なる情報理論の一分野に留まらず、グラフ理論、計算複雑性理論、そして量子情報理論といった幅広い分野に影響を与え、新しい数学的概念の誕生を促しました。これは、シャノンの研究が持つ根本的な深さと、異なる分野を横断する普遍性を示す好例と言えるでしょう。
結論
クロード・シャノンによる誤り確率ゼロ容量の概念は、情報伝送レートの限界を問うシャノンの探求が、グラフ理論における非自明な数学的問題、特に積グラフの独立集合数の計算へと繋がった興味深い事例です。シャノン自身はこの容量の一般的な計算方法を提示しませんでしたが、彼が提起した課題は、後にLovaszによるテータ関数（Lovasz数）の導入と、それが誤り確率ゼロ容量と一致するという画期的な結果へと発展しました。
この研究の歴史は、情報理論が確率論や代数学といった基盤的な数学分野のみならず、組合せ論やグラフ理論とも深く結びついていることを示しています。また、理論的な問題設定が、新たな数学的概念の創造を促し、それが再び元の問題を解決するという科学研究の循環的な側面を鮮やかに示しています。シャノンの誤り確率ゼロ容量に関する考察は、現代においてもなお、様々な分野の研究者にとって重要な示唆を与え続けていると言えるでしょう。