【徹底解説】マクミランの不等式

本記事は情報理論の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

概要

マクミランの不等式は，クラフトの不等式と同じ形をしています。ですが，クラフトの不等式が与えられた符号長から瞬時符号の存在を判定するものであったのに対し，マクミランの不等式は与えられた符号長から一意復号可能な符号の存在を判定します。

Sardinas-Pattersonの定理が具体的な符号が与えられたときに一意復号可能かを判定する必要十分条件であったのに対し，マクミランの不等式は具体的な符号は与えられず，符号長が与えられた際の定理であることに注意してください。改めて，マクミランの不等式を以下に示します。

証明

必要性

まず，必要性（$\Leftarrow$）に関してです。クラフトの不等式より長さ$l_i$の$q$元瞬時符号が存在します。したがって，これは一意復号可能です。

十分性

十分性の証明は，複素関数を使った証明と展開式を使った証明の2通りがありますが，今回は簡単な展開式を使った証明を行っていきたいと思います。複素関数を使った証明は[1]を参照ください。展開式を使った証明は，最終的に指数関数と線形関数の発散の速さを比較することによりマクミランの不等式が得られます。

全体の流れは，まずマクミランの不等式の左辺を$T$とおき，以下のように$T^n$を線形関数$f(n)$で上からおさえます。

$T > 1$とすると，$n$を十分大きくしていくとき，左辺は指数関数のオーダーで増大しますが，右辺は線形関数のオーダーでしか増大しません。したがって，$T \leq 1$になります。これは，マクミランの不等式を表しています。

さて，ここからは$T^n$を上からおさえる線形関数$f(n)$を具体的に見つけていきます。これは，実際に$T^n$を展開してみると求めることができます。多項定理の展開を参考にすると，以下のように計算することができます。

ただし，$m = \min \sum_{i=1}^K l_i$，$l = \max \sum_{i=1}^K l_i$とおきました。少し補足しておきます。シグマの範囲が$d=mn, \cdots, ln$となっていますが，これは展開式における$l^{-1}$の指数を考えたときに，$n$個の$(l_1 + \cdots + l_n)$から全て最小値$m$を選択した場合の指数が$mn$，全て最大値$l$を選択した場合が$ln$になるということです。

さて，ここで$N_{d}$に対して考察してみましょう。$\calC$が一意復号可能という条件をこいつに適用することで，$N_{d}$を上からおさえることができ，結果として$T^K$を上からおさえることができます。そもそも$N_d$というのは，展開式における$l^{-1}$の指数を考えたとき，$n$個の$(l_1 + \cdots + l_n)$から掛け合わせる項を選択した結果，指数の合計が$d$になる組み合わせの個数です。

これは言い換えれば，$\calC$の含まれる$n$個の符号語の列$\vt = w_1, \ldots, w_n$の長さが$d$である，つまり$|\vt| = d$となる組み合わせの総数になります。$\calC$が一意復号可能であることから，$|\vt| = d$となる組み合わせの総数は$\vt$以外から作り出されることはありません。長さ$d$の符号語$\vt$が$q$元符号であることから，$N_d$は$q^d$に等しいか小さいということになります。したがって，以下が成り立ちます。

したがって，以下のように$T^n$を上から線形関数$f(n)$おさえることができます。

したがって，冒頭で説明した通り，$T^n \leq 1$でなければならず，これはマクミランの不等式そのものを表しています。

[1] McMillan, Brockway. "Two inequalities implied by unique decipherability." IRE Transactions on Information Theory 2.4 (1956): 115-116.