13.3 複雑性とエントロピー

13.2 節までの $𝐾 U$ は一つの自然数についての量で，分布はどこにも現れなかった．いっぽう第2章から第12章までに得た圧縮の限界は，どれも分布から作ったエントロピーで書かれている．二つは測っている相手が違うので，並べただけでは比べられない．本節は，分布 $𝑝$ の情報源が出した長さ $𝑛$ のブロックに $𝐾 U$ を当て，その平均を $1$ 文字あたりに直したものが $𝐻 (𝑝)$ に近づくことを示す．分布についての量と，一本の系列についての量が，そこで同じ値を指す．

そのためにまず，ブロックに自然数の番号を与えなければならない． $𝐾 U$ は定義 13.1.4 のとおり自然数についての量なので， $X 𝑛$ の元をそのまま渡せないからである．番号づけを置いたあと，上からの評価を第12章の型による二段符号から，下からの評価を定理 13.2.1 の数え上げと第2章の典型集合から作り，二つを挟み撃ちにする．最後に，個々のブロックについて何が言えるかを見る．

以下， $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の全点で正の分布とし，第2章 2.1 節と同じ設定で $𝑋 0, 𝑋 1, \dots$ を分布 $𝑝$ の i.i.d. 情報源， $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ と書く． $𝑝$ の $𝑛$ 重の積分布は $𝑝 𝑛$ と書く（第11章と同じ肩の書き方で， $𝑝 𝑛 ({𝑥}) : = \prod 𝑛 - 1 𝑖 = 0 𝑝 (𝑥 𝑖)$ である）．エントロピー $𝐻$ （定義 1.1.1）は，第12章と同じく分布に対して書く．すなわち $𝐻 (𝑝)$ は $𝑋 0$ のエントロピーであり，単位は 13.1 節で断ったとおりビットである．

ブロックに番号をつける

定義 13.3.1（ブロックの番号）. $X$ を空でない有限アルファベットとし， $X$ の文字に $0, 1, \dots, | X | - 1$ の番号を一つずつ与えて固定して，文字 $𝑎$ に与えた番号を $𝑐 (𝑎)$ と書く（ $𝑐$ は $X$ から ${0, 1, \dots, | X | - 1}$ への全単射である）． $𝑛 \geq 1$ と $𝑥 = (𝑥 0, \dots, 𝑥 𝑛 - 1) \in X 𝑛$ に対し

⟨ 𝑥 ⟩ : = 𝑛 - 1 \sum 𝑖 = 0 𝑐 (𝑥 𝑖) | X | 𝑖

と定める．

第10章は内積を，二つの引数をとる $⟨ \cdot, \cdot ⟩$ と書いたが，本章の $⟨ \cdot ⟩$ はつねに引数を一つとり，有限の対象を自然数に写す符号化を表す． $⟨ 𝑥 ⟩$ は， $𝑥$ の第 $𝑖$ 文字の番号を第 $𝑖$ 桁とする $| X |$ 進の数にほかならない．たとえば $X = {0, 1}$ に $𝑐 (0) = 0$ ， $𝑐 (1) = 1$ と番号を与えれば， $⟨ 𝑥 ⟩$ は $𝑥$ を下の桁から読んだ二進の数である．番号づけを一つ固定したのは， $⟨ 𝑥 ⟩$ の値が $X$ の文字の並べ方に依るからで，以下では固定した $𝑐$ についての値をいう．

形式化: encodeBlock (ソース)

命題 13.3.2. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $⟨ \cdot ⟩$ を定義 13.3.1 のとおりとする．このとき $𝑥 \mapsto ⟨ 𝑥 ⟩$ は $X 𝑛$ の上で単射であり，どの $𝑥 \in X 𝑛$ についても $⟨ 𝑥 ⟩ < | X | 𝑛$ である．

証明. 上界から示す．どの文字 $𝑎$ についても $𝑐 (𝑎) \leq | X | - 1$ だから，各項を $(| X | - 1) | X | 𝑖 = | X | 𝑖 + 1 - | X | 𝑖$ で抑えて足すと隣り合う項が打ち消し合い

⟨ 𝑥 ⟩ \leq 𝑛 - 1 \sum 𝑖 = 0 (| X | 𝑖 + 1 - | X | 𝑖) = | X | 𝑛 - 1

となる．

単射性に移る． $⟨ 𝑥 ⟩$ は $𝑥$ の $| X |$ 進表示にほかならないから，下の桁から一つずつ剥がせばもとの $𝑥$ に戻る．これを $𝑛$ についての帰納法で書く． $𝑛 = 1$ のときは $⟨ 𝑥 ⟩ = 𝑐 (𝑥 0)$ で， $𝑐$ が単射だから $⟨ 𝑥 ⟩$ から $𝑥 0$ が定まる． $𝑛 \geq 2$ のときは，定義 13.3.1 の和から第 $0$ 項を外して $| X |$ でくくると $⟨ 𝑥 ⟩ = 𝑐 (𝑥 0) + | X | ⟨ 𝑥 - ⟩$ （ $𝑥 - : = (𝑥 1, \dots, 𝑥 𝑛 - 1) \in X 𝑛 - 1$ ）であり， $𝑐 (𝑥 0)$ は $| X |$ 未満だから， $𝑐 (𝑥 0)$ は $⟨ 𝑥 ⟩$ を $| X |$ で割った余り， $⟨ 𝑥 - ⟩$ はその商として $⟨ 𝑥 ⟩$ から定まる． $𝑐$ が単射だから $𝑥 0$ が定まり，帰納法の仮定から $𝑥 -$ が定まる． $◼$

形式化: 単射性 encodeBlock_injective，上界 encodeBlock_lt (ソース)

命題 13.3.2 の上界は，番号づけが場所を無駄にしていないことを言っている．長さ $𝑛$ のブロックは $| X | 𝑛$ 個あり，それがちょうど $0$ 以上 $| X | 𝑛$ 未満の自然数に重なりなく収まっている．したがって $⟨ 𝑥 ⟩$ の二進表示の長さは $𝑛 l o g 2 | X |$ あまりで，ブロックをそのまま書き写すのに要る長さと変わらない．番号づけそのものは何も圧縮していないということで，圧縮は次の命題 13.3.3 から始まる．

型による記述

第12章定義 12.2.1 は，系列を「まず型を送り，次に型類の中の位置を送る」二段の形で書いたときの長さを $ℓ T 𝑛$ と置いた．記号を一つ引いておく．実数 $𝑡$ に対する天井関数 $⌈ 𝑡 ⌉$ ，すなわち $𝑡$ 以上の最小の整数と，その性質 $𝑡 \leq ⌈ 𝑡 ⌉ < 𝑡 + 1$ は，第4章 4.4 節で既知としたとおりに本節でも使う． $𝑥 \in X 𝑛$ の型を $ˆ 𝑃 𝑥$ ，長さ $𝑛$ の型 $𝑃$ の型類を $T 𝑛 (𝑃)$ （どちらも定義 11.1.1）と書くと，その長さは

ℓ T 𝑛 (𝑥) = ⌈ | X | l o g 2 (𝑛 + 1) ⌉ + ⌈ l o g 2 ∣ T 𝑛 (ˆ 𝑃 𝑥) ∣ ⌉

である．第 $1$ 項が型を指すための長さ，第 $2$ 項が型類の中の位置を指すための長さで，どちらも分布を持ち出さずに系列だけから決まる．だから $ℓ T 𝑛$ はそのまま機械への指示に写せる．写した先で定理 13.1.7 を当てれば， $𝐾 U$ の上界が定数の払いで手に入る．

命題 13.3.3（型による記述の上界）. $X$ を空でない有限アルファベットとし， $⟨ \cdot ⟩$ を定義 13.3.1， $ℓ T 𝑛$ を定義 12.2.1 の型による二段符号の符号長とする．このとき定数 $𝜉 \in ℕ$ があって，すべての $𝑛 \geq 1$ とすべての $𝑥 \in X 𝑛$ について

𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛) \leq ℓ T 𝑛 (𝑥) + 𝜉

が成り立つ．

証明. $𝑛 \geq 1$ と $𝑥 \in X 𝑛$ から，長さ $ℓ T 𝑛 (𝑥) + 1$ のビット列を組み立てる． $𝐴 𝑛 : = ⌈ | X | l o g 2 (𝑛 + 1) ⌉$ と置く（定義 12.2.1 の第 $1$ 項である）．

型を書く桁を作る．各文字 $𝑎 \in X$ について $𝑁 (𝑎 ∣ 𝑥)$ （定義 2.4.1）は $0$ 以上 $𝑛$ 以下の整数だから， $𝑁 (𝑎 ∣ 𝑥)$ を第 $𝑐 (𝑎)$ 桁とする $(𝑛 + 1)$ 進の数

𝑢 : = \sum 𝑎 \in X 𝑁 (𝑎 ∣ 𝑥) (𝑛 + 1) 𝑐 (𝑎)

を作ると，命題 13.3.2 の上界と同じ打ち消しにより $𝑢 \leq (𝑛 + 1) | X | - 1$ である．いっぽう，自然数 $𝐴$ について $2 𝐴 \geq (𝑛 + 1) | X |$ であることと $𝐴 \geq l o g 2 ((𝑛 + 1) | X |) = | X | l o g 2 (𝑛 + 1)$ であることとは同値だから， $𝐴 𝑛$ は $2 𝐴 \geq (𝑛 + 1) | X |$ を満たす最小の自然数にほかならない．とくに $2 𝐴 𝑛 \geq (𝑛 + 1) | X | > 𝑢$ だから， $𝑢$ は $𝐴 𝑛$ 桁の二進表示で書ける（桁が足りなければ先頭を $0$ で埋める）．

型類の中の位置を書く桁を作る． $𝑥$ の型を $ˆ 𝑃 𝑥$ ，その型類を $T 𝑛 (ˆ 𝑃 𝑥)$ （どちらも定義 11.1.1）と書くと $𝑥 \in T 𝑛 (ˆ 𝑃 𝑥)$ である．命題 13.3.2 より $⟨ \cdot ⟩$ は $X 𝑛$ の上で単射だから， $T 𝑛 (ˆ 𝑃 𝑥)$ の元を $⟨ \cdot ⟩$ の値の小さい順に一列に並べられる．その並びでの $𝑥$ の位置を $𝑖$ とすると $0 \leq 𝑖 < | T 𝑛 (ˆ 𝑃 𝑥) |$ であり， $𝐵 : = ⌈ l o g 2 | T 𝑛 (ˆ 𝑃 𝑥) | ⌉$ と置くと $2 𝐵 \geq | T 𝑛 (ˆ 𝑃 𝑥) |$ だから， $𝑖$ は $𝐵$ 桁の二進表示で書ける．

二つをつなぐ． $𝑑$ を， $𝑢$ の $𝐴 𝑛$ 桁と $𝑖$ の $𝐵$ 桁をこの順に並べた長さ $𝐴 𝑛 + 𝐵 = ℓ T 𝑛 (𝑥)$ のビット列とし， $𝑠$ を $𝑑$ の先頭に $1$ を置いた長さ $ℓ T 𝑛 (𝑥) + 1$ のビット列とする．先頭が $1$ だから，定義 13.1.2 より $𝑠$ が表す自然数の二進表示は $𝑠$ そのものであり， $𝑠$ から $𝑑$ が読み取れる．

復元する手続きを書き下す． $M (𝑧, 𝑦)$ を， $𝑧 \geq 1$ かつ $𝑦 \geq 1$ のとき，型を読む・型類を並べる・位置を拾うの三段で次のように定める．型を読むところでは， $𝑧$ の二進表示から先頭の $1$ を落とした列を $𝑑$ とし， $2 𝐴 \geq (𝑦 + 1) | X |$ を満たす最小の自然数 $𝐴$ を， $𝐴 = 0, 1, 2, \dots$ と順に試して求める．そのような $𝐴$ はあるのでこの探索は必ず停止し，求まる値は，上で見たとおり $𝐴 𝑛$ の式の $𝑛$ を $𝑦$ に替えた $𝐴 𝑦 : = ⌈ | X | l o g 2 (𝑦 + 1) ⌉$ にほかならない．続けて， $𝑑$ の先頭 $𝐴 𝑦$ 桁を二進表示として読んだ自然数 $𝑢$ を $(𝑦 + 1)$ 進の下の $| X |$ 桁に開き，第 $𝑐 (𝑎)$ 桁を文字 $𝑎$ の個数と読む．型類を並べるところでは，$a \mapsto (\text{ $𝑎$ の個数})/y$ が長さ $𝑦$ の型（定義 11.1.1）であることを使い，その型類の元を $⟨ \cdot ⟩$ の値の小さい順に一列に並べる．位置を拾うところでは， $𝑑$ の残りの桁が表す自然数をその並びでの位置として，そこにある $𝑥' \in X 𝑦$ をとり $⟨ 𝑥' ⟩$ を返す．以上のどこかで形が合わなければ， $M (𝑧, 𝑦)$ は値を持たないとする．この対応は有限個の場合分けと有限回の繰り返し，および必ず停止する探索で書き下せているから，Church–Turing のテーゼより部分計算可能であり，定義 13.1.3 の意味で機械である．

作り方から $M (𝑠, 𝑛) = ⟨ 𝑥 ⟩$ である．定理 13.1.7 をこの $M$ に当てて定数 $𝜉 0 \in ℕ$ をとると

𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛) \leq | 𝑠 | + 𝜉 0 = ℓ T 𝑛 (𝑥) + 1 + 𝜉 0

である． $𝜉 0$ は $M$ だけで決まり， $M$ は $𝑛$ にも $𝑥$ にも依らないから， $𝜉 : = 𝜉 0 + 1$ と置けば主張を得る． $◼$

形式化上の注記

命題 13.3.3 に対応する，一般のアルファベットについての単独の宣言は無い．二値の場合については，型を書く長さ $2 l o g 2 (𝑛 + 1)$ と，その系列の型の二値エントロピーを $𝑛$ 倍したものを直に足した形の上界が condComplexity_bool_block_le (InformationTheory/Shannon/Kolmogorov/Incompressible.lean) にある．一般のアルファベットについては condComplexity_block_typical_le (InformationTheory/Shannon/Kolmogorov/EntropyRate.lean) があるが，こちらは上界の形が違う．抑える相手を強典型集合（定義 2.4.1）の上に限ったうえで，系列ごとの型のエントロピーではなく，情報源の真のエントロピーに典型性の幅を足したものを $𝑛$ 倍した形で抑えており，型を書く長さにあたる項は，そこに重ねた長さに比例する余裕のほうに吸収されている．しかも可測性と全点正値性を課した情報源を置いた設定の中で，十分大きい $𝑛$ についてだけの主張である．命題 13.3.3 のほうは分布を持ち出さず，すべての $𝑛 \geq 1$ とすべての $𝑥$ について述べている．

命題 13.3.3 の定数は一つに決まらない．不等式を満たす自然数が一つあれば，それより大きい自然数もみな満たすからである．以下では，そのようなものを一つとって固定し， $𝜉$ と書く．

条件に $𝑛$ を置いたことに注意したい．この記述は，長さ $𝑛$ を知っている相手に向けて書かれている．長さを知らなければ，型の桁がどこで終わるかも，型類をどう並べるかも決まらないからである． $𝑛$ を書き添える手もあるが，本節は $𝑛$ を条件として渡す形をとり，条件を外した $𝐾 U (⟨ 𝑥 ⟩)$ については何も述べない．

平均は両側からエントロピーに寄る

長さ $𝑛$ のブロックは有限個で，命題 13.1.6 よりどの $𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛)$ も有限だから， $𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛)$ の平均

𝔼 [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛)] = \sum 𝑥 \in X 𝑛 𝑝 𝑛 ({𝑥}) 𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛)

は有限個の項の和である．これを $𝑛$ で割った量が本節の主役で，上からは命題 13.3.3 と第12章が，下からは定理 13.2.1 と第2章が抑える．

補題 13.3.4. $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の全点で正の分布とし，第2章 2.1 節と同じ設定で $𝑋 0, 𝑋 1, \dots$ を分布 $𝑝$ の i.i.d. 情報源， $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ とする． $⟨ \cdot ⟩$ を定義 13.3.1， $𝜉$ を命題 13.3.3 の定数の一つとすると，すべての $𝑛 \geq 1$ について

1 𝑛 𝔼 [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛)] \leq 𝐻 (𝑝) + | X | l o g 2 (𝑛 + 1) + 2 + 𝜉 𝑛

である（ $𝐻$ は定義 1.1.1 のエントロピー）．

証明. 第12章の族の設定を，一つの分布に潰して使う． $Θ$ を $1$ 点集合 ${𝜃 0}$ とし， $𝑃 𝜃 0 : = 𝑝$ と置くと， $Θ$ は空でない有限集合で $𝑃 𝜃 0$ は全点で正だから，これは定義 12.1.1 の情報源の族である． $𝑝$ が全点で正であることは定義 12.1.1 が族に課す条件であり，本補題の仮定でもある．積分布は $𝑃 𝑛 𝜃 0 = 𝑝 𝑛$ である．

$𝑛 \geq 1$ とする．定理 12.2.4 をこの族の $𝜃 0$ に当てると，定義 12.1.2 より

1 𝑛 (\sum 𝑥 \in X 𝑛 𝑝 𝑛 ({𝑥}) ℓ T 𝑛 (𝑥) - 𝐻 (𝑝 𝑛)) \leq | X | l o g 2 (𝑛 + 1) + 2 𝑛

である． $𝑝 𝑛$ は分布 $𝑝$ の i.i.d. 情報源の長さ $𝑛$ のブロックの分布だから，補題 2.3.3 より $𝐻 (𝑝 𝑛) = 𝑛 𝐻 (𝑝)$ である．これを移項して

1 𝑛 \sum 𝑥 \in X 𝑛 𝑝 𝑛 ({𝑥}) ℓ T 𝑛 (𝑥) \leq 𝐻 (𝑝) + | X | l o g 2 (𝑛 + 1) + 2 𝑛

を得る．

命題 13.3.3 の不等式に $𝑝 𝑛 ({𝑥})$ を掛けて $𝑥$ について足す．重みは非負で総和が $1$ だから

𝔼 [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛)] \leq \sum 𝑥 \in X 𝑛 𝑝 𝑛 ({𝑥}) ℓ T 𝑛 (𝑥) + 𝜉

である．両辺を $𝑛$ で割り，上の評価を入れると主張を得る． $◻$

形式化上の注記

補題 13.3.4 の形の宣言は無い．形式化が持つのは，任意の $𝜀 > 0$ について十分大きい $𝑛$ で平均が $𝐻 (𝑝) + 𝜀$ 以下になるという形の kolmogorov_entropy_rate_upper (InformationTheory/Shannon/Kolmogorov/EntropyRate.lean) で，本文が書いた $𝑛$ についての明示的な速さは含んでいない．

下からの評価に移る．上からの評価が符号を一つ作って見せたのに対し，下からの評価は符号を作らない．短い記述は本数が限られているという定理 13.2.1 の数え上げと，実際に現れるブロックはどれも確率が $2 - 𝑛 𝐻$ の近くにあるという定理 2.2.4 を，そのまま突き合わせる．

補題 13.3.5. $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の全点で正の分布とし，第2章 2.1 節と同じ設定で $𝑋 0, 𝑋 1, \dots$ を分布 $𝑝$ の i.i.d. 情報源， $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ とする． $⟨ \cdot ⟩$ を定義 13.3.1 とすると，任意の $𝜀 > 0$ について， $𝑛$ が十分大きければ

1 𝑛 𝔼 [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛)] \geq 𝐻 (𝑝) - 𝜀

である（ $𝐻$ は定義 1.1.1 のエントロピー）．

証明. $𝜀 > 0$ とする． $𝐻 (𝑝) \leq 𝜀$ のときは， $𝐾 U$ が $0$ 以上だから左辺が $0$ 以上で，右辺は $0$ 以下であり，主張は成り立つ．以下 $𝐻 (𝑝) > 𝜀$ とする．

失う量を先に割り振っておく． $𝐻 (𝑝)$ から引かれるのは次の三つで，そのそれぞれを $𝜀 / 3$ 以下に抑える．

典型集合に置く幅．
記述が短いほうへ数え落とす確率に $𝐻 (𝑝)$ を掛けたもの．これはさらに， $𝑋 𝑛$ が典型集合を外れる分と，典型集合に入ったうえで記述が短い分とに割れるので， $𝐻 (𝑝)$ を掛けたものをどちらも $𝜀 / 6$ 以下にする． $𝑚$ を選ぶのは後者のためで， $2 - 𝑚$ がその確率の上界になる．
記述の長さの下限にとる整数の端数．

割り振りに合わせて三つの数を選ぶ． $𝜀 1 : = 𝜀 / 3$ と置くと $0 < 𝜀 1 < 𝐻 (𝑝)$ である．自然数 $𝑚$ を $2 - 𝑚 𝐻 (𝑝) \leq 𝜀 / 6$ を満たすようにとる．そして $𝑛 \geq 1$ に対し， $𝑘 + 𝑚 \leq 𝑛 (𝐻 (𝑝) - 𝜀 1)$ を満たす自然数 $𝑘$ の全体を考える． $𝑛 (𝐻 (𝑝) - 𝜀 1) \to \infty$ だから， $𝑛$ が十分大きければ $𝑘 = 0$ がこれを満たしてこの集合は空でなく，しかも $𝑛 (𝐻 (𝑝) - 𝜀 1)$ が上界だから，最大の元をもつ．それを $𝑘 𝑛$ と書く．以下そのような $𝑛$ だけを見る．とり方から

𝑘 𝑛 + 𝑚 \leq 𝑛 (𝐻 (𝑝) - 𝜀 1) < 𝑘 𝑛 + 1 + 𝑚

である（右側は $𝑘 𝑛 + 1$ が上の集合に入らないことによる）．

典型集合の上で，記述の短いブロックの確率を抑える． $𝑇 (𝑛) 𝜀 1$ を定義 2.2.1 の典型集合とする．命題 13.3.2 より $𝑥 \mapsto ⟨ 𝑥 ⟩$ は $X 𝑛$ の上で単射だから， $𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛) < 𝑘 𝑛$ を満たす $𝑥 \in X 𝑛$ の個数は， $𝐾 U (𝑧 ∣ 𝑛) < 𝑘 𝑛$ を満たす自然数 $𝑧$ の個数以下であり，定理 13.2.1 より $2 𝑘 𝑛$ より小さい．いっぽう $𝑥 \in 𝑇 (𝑛) 𝜀 1$ なら定理 2.2.4 より $𝑝 𝑛 ({𝑥}) \leq 2 - 𝑛 (𝐻 (𝑝) - 𝜀 1)$ である．二つを掛け合わせ， $𝑘 𝑛 \leq 𝑛 (𝐻 (𝑝) - 𝜀 1) - 𝑚$ を使うと

P r [𝑋 𝑛 \in 𝑇 (𝑛) 𝜀 1 かつ 𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛) < 𝑘 𝑛] \leq 2 𝑘 𝑛 2 - 𝑛 (𝐻 (𝑝) - 𝜀 1) \leq 2 - 𝑚

である．

記述が短くない確率を下から抑える．事象 ${𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛) < 𝑘 𝑛}$ は， $𝑋 𝑛$ が典型集合に入らない場合と，入ったうえで記述が短い場合に分かれるから

P r [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛) \geq 𝑘 𝑛] \geq P r [𝑋 𝑛 \in 𝑇 (𝑛) 𝜀 1] - 2 - 𝑚

である．定理 2.2.3 より $P r [𝑋 𝑛 \in 𝑇 (𝑛) 𝜀 1] \to 1$ だから， $𝑛$ が十分大きければ $(1 - P r [𝑋 𝑛 \in 𝑇 (𝑛) 𝜀 1]) 𝐻 (𝑝) \leq 𝜀 / 6$ にできる．

平均を下から抑える． $𝐾 U$ は $0$ 以上で $𝑘 𝑛$ も $0$ 以上だから， $𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛) < 𝑘 𝑛$ の側の項を落として

𝔼 [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛)] \geq 𝑘 𝑛 P r [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛) \geq 𝑘 𝑛]

である． $𝑘 𝑛 / 𝑛 \leq 𝐻 (𝑝) - 𝜀 1 < 𝐻 (𝑝)$ だから，右辺を $𝑛$ で割った値は

𝑘 𝑛 𝑛 - 𝑘 𝑛 𝑛 (1 - P r [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛) \geq 𝑘 𝑛]) \geq 𝑘 𝑛 𝑛 - 𝐻 (𝑝) ((1 - P r [𝑋 𝑛 \in 𝑇 (𝑛) 𝜀 1]) + 2 - 𝑚)

以上である．いま $𝑚$ のとり方と直前の段から，右端の括弧に $𝐻 (𝑝)$ を掛けたものは $𝜀 / 3$ 以下である．また $𝑘 𝑛$ のとり方の右側の不等式より $𝑘 𝑛 / 𝑛 > 𝐻 (𝑝) - 𝜀 1 - (1 + 𝑚) / 𝑛$ だから， $𝑛$ を $(1 + 𝑚) / 𝑛 \leq 𝜀 / 3$ となるまで大きくとれば，全体は $𝐻 (𝑝) - 𝜀 1 - 𝜀 / 3 - 𝜀 / 3 = 𝐻 (𝑝) - 𝜀$ 以上である． $◻$

形式化: kolmogorov_entropy_rate_lower (ソース)

定理 13.3.6（複雑性とエントロピー）. $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の全点で正の分布とし，第2章 2.1 節と同じ設定で $𝑋 0, 𝑋 1, \dots$ を分布 $𝑝$ の i.i.d. 情報源， $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ とする． $⟨ \cdot ⟩$ を定義 13.3.1 とすると

1 𝑛 𝔼 [𝐾 U (⟨ 𝑋 𝑛 ⟩ ∣ 𝑛)] ⟶ 𝐻 (𝑝) (𝑛 \to \infty)

である（ $𝐻$ は定義 1.1.1 のエントロピー）．

証明. $𝜀 > 0$ とする．補題 13.3.5 より， $𝑛$ が十分大きければ左辺は $𝐻 (𝑝) - 𝜀$ 以上である．

上からは補題 13.3.4 が $𝐻 (𝑝) + (| X | l o g 2 (𝑛 + 1) + 2 + 𝜉) / 𝑛$ を与える．この第 $2$ 項は $0$ に収束する．本章の底で読むと補題 11.2.2 より $l o g 2 (𝑛 + 1) / 𝑛 \to 0$ であり， $| X |$ は $𝑛$ に依らない有限の数だからその $| X |$ 倍も $0$ に収束し， $(2 + 𝜉) / 𝑛$ も $0$ に収束するからである．よって $𝑛$ が十分大きければ左辺は $𝐻 (𝑝) + 𝜀$ 以下である．

二つの「十分大きい」の大きいほうをとれば，それ以上の $𝑛$ について左辺と $𝐻 (𝑝)$ の差は $𝜀$ より大きくならない． $◼$

形式化: kolmogorov_entropy_rate (ソース)

注記

形式化の上半は，強典型集合（定義 2.4.1）の上と外に平均を分け，それぞれを別の上界で抑えて組み立てており，本文が引く定理 12.2.4 は使っていない．下半は本文と同じく，記述の短い対象の数え上げと典型集合（定義 2.2.1）による．保証しているのは定理の正しさであって，紙の証明手順の一致ではない．

定理 13.3.6 が，本節のはじめに述べた二つの量を結んでいる．左辺は，情報源が実際に出した一本のブロックを，分布を知らない機械に書き出させる長さの平均である．右辺は，分布だけから決まる量である．第2章の情報源符号化定理も同じ値を両側から挟んだが，あちらの符号は分布 $𝑝$ を知って作られていた．こちらの $𝐾 U$ は分布を一度も見ていない．それでも $1$ 文字あたりの長さは同じところへ行く．

分布を見ないことの代償は補題 13.3.4 の右辺に出ている．右辺が $𝐻 (𝑝)$ を超える分は $(| X | l o g 2 (𝑛 + 1) + 2) / 𝑛$ に $𝜉 / 𝑛$ を足したもので，前半は第12章定理 12.2.4 が型による二段符号に与えた冗長度の上界そのもの，後半が，機械を一つ固定して一本の系列を測るようにしたぶんである． $| X | = 2$ ， $𝑛 = 1000$ なら，前半は第12章例 12.2.7 が計算した $0.02193 \dots$ ビットで，後半は $𝜉 / 1000$ ビットである．

$𝜉$ をどう思えばよいかを書いておく． $𝜉$ は命題 13.3.3 の証明のとおり定理 13.1.7 の定数から来ており，定理 13.1.7 の証明が与える定数は，当てた機械に番号づけが与えた番号に $2$ を足したものだった．命題 13.3.3 の証明はそれにさらに $1$ を足すので， $𝜉$ は，型と型類から系列を復元する手続きに番号づけが与えた番号に $3$ を足した値でとれる．すなわち，番号づけの中でこの復元器が早い番号を持てば $𝜉$ は小さく，遅い番号しか持たなければ大きい．どの手続きに何番を与えるかは番号づけの取り方に依る．13.1 節の $𝑏$ が番号づけに依るのと同じことである．第12章例 12.2.7 の $0.02193 \dots$ ビットのほうは，番号づけを持ち出さずに書けた数だった．

いっぽう補題 13.3.5 と定理 13.3.6 には $𝜉$ が現れない．下からの評価は機械を作らずに数え上げだけで出ており，極限のほうは $𝜉$ を $𝑛$ で割って消してしまうからである．

圧縮できないブロック

定理 13.3.6 は平均についての主張で，一本一本のブロックについては何も言っていない．そこで，個々のブロックのうち，これ以上短く書けないものを取り出して調べる．アルファベットは ${0, 1}$ にとり，番号は $𝑐 (0) = 0$ ， $𝑐 (1) = 1$ と与えて固定する．

定義 13.3.7（圧縮できないブロック）. $𝑛 \geq 1$ とする． $𝑥 \in {0, 1} 𝑛$ が 圧縮できない とは

𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛) \geq 𝑛

が成り立つことをいう（ $⟨ \cdot ⟩$ は定義 13.3.1 を $X = {0, 1}$ ， $𝑐 (0) = 0$ ， $𝑐 (1) = 1$ に当てたものである）．

13.2 節は「 $𝑘$ ビット未満では書き出せない」ことを指して同じ言葉を地の文で使ったが，ここで名前を与えるのは，長さ $𝑛$ のブロックについて $𝑘$ を $𝑛$ ととった場合である．この条件は長さ $𝑛$ のブロック一つについてのもので，長さを伸ばしながら同じ条件を課しても，無限に続く列そのものについての性質を定めたことにはならない．本書は無限列についての同種の概念を扱わない．

命題 13.3.8. 各 $𝑛 \geq 1$ に $𝑥 (𝑛) \in {0, 1} 𝑛$ を対応させて，どの $𝑛 \geq 1$ についても $𝑥 (𝑛)$ が定義 13.3.7 の意味で圧縮できないようにできる．

証明. $𝑛 \geq 1$ を固定する．定理 13.2.1 を $𝑦 : = 𝑛$ ， $𝑘 : = 𝑛$ に当てると， $𝐾 U (𝑧 ∣ 𝑛) < 𝑛$ を満たす自然数 $𝑧$ は $2 𝑛$ 個より少ない．いっぽう ${0, 1} 𝑛$ の要素数は $2 𝑛$ であり，命題 13.3.2 より $𝑥 \mapsto ⟨ 𝑥 ⟩$ はその上で単射だから， ${⟨ 𝑥 ⟩ : 𝑥 \in {0, 1} 𝑛}$ は $2 𝑛$ 個の相異なる自然数からなる．したがってそのすべてが $𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛) < 𝑛$ を満たすことはなく，圧縮できない $𝑥 \in {0, 1} 𝑛$ が少なくとも一つある．各 $𝑛 \geq 1$ についてそのようなものを一つ選んで $𝑥 (𝑛)$ とすればよい． $◼$

形式化: exists_incompressible_bool_seq (ソース)

圧縮できないブロックがあることは分かった．では，そのようなブロックはどんな見た目をしているだろうか．手がかりは命題 13.3.3 にある．型による記述の長さは型類の要素数で決まり，型類は $0$ と $1$ の個数が偏るほど小さくなる．したがって個数の偏ったブロックには短い記述があり，圧縮できないブロックにはその短さが無いのだから，個数は偏っていないことになる．次の定理はこの筋を不等式にしたものである．

定理 13.3.9（圧縮できないブロックの $1$ の頻度）. $𝛿 > 0$ とする． $𝑛$ が十分大きければ，定義 13.3.7 の意味で圧縮できないどの $𝑥 \in {0, 1} 𝑛$ についても

∣ 𝑁 (1 ∣ 𝑥) 𝑛 - 12 ∣ < 𝛿

である（ $𝑁 (1 ∣ 𝑥)$ は定義 2.4.1 の， $𝑥$ に含まれる $1$ の個数）．

証明. $𝑁 (1 ∣ 𝑥) / 𝑛$ は $0$ 以上 $1$ 以下だから， $𝛿 > 1 / 2$ のときは左辺が $1 / 2$ 以下で主張が成り立つ．以下 $0 < 𝛿 \leq 1 / 2$ とする．

型による上界を二値に当てる． $X : = {0, 1}$ とし， $𝜉$ を命題 13.3.3 の定数の一つとする． $𝑛 \geq 1$ と $𝑥 \in {0, 1} 𝑛$ をとり， $𝑟 : = 𝑁 (1 ∣ 𝑥) / 𝑛$ と置く．天井関数の性質 $⌈ 𝑡 ⌉ < 𝑡 + 1$ （4.4 節）を定義 12.2.1 の二つの項に当てると

ℓ T 𝑛 (𝑥) < 2 l o g 2 (𝑛 + 1) + 2 + l o g 2 ∣ T 𝑛 (ˆ 𝑃 𝑥) ∣

である．

型類の要素数を本章の底で読む．第11章は $l o g$ の底を自然対数にとっているので，定理 11.1.8 の上界はそこで測ったエントロピーを $e$ の肩に乗せた形をしているが，本章の底で読めば $| T 𝑛 (𝑃) | \leq 2 𝑛 𝐻 (𝑃)$ である（読み替えは第12章 12.2 節が置いたものと同じである）． $𝑃 : = ˆ 𝑃 𝑥$ ととって両辺の $l o g 2$ をとると $l o g 2 | T 𝑛 (ˆ 𝑃 𝑥) | \leq 𝑛 𝐻 (ˆ 𝑃 𝑥)$ である．また定義 11.1.1 より $ˆ 𝑃 𝑥 (1) = 𝑟$ ， $ˆ 𝑃 𝑥 (0) = 1 - 𝑟$ だから，例 1.1.2 より $𝐻 (ˆ 𝑃 𝑥) = 𝐻 𝑏 (𝑟)$ である．

圧縮できないことを不等式にする． $𝑥$ が圧縮できないとすると，定義 13.3.7 と命題 13.3.3 と上の二つから

𝑛 \leq 𝐾 U (⟨ 𝑥 ⟩ ∣ 𝑛) \leq ℓ T 𝑛 (𝑥) + 𝜉 < 2 l o g 2 (𝑛 + 1) + 2 + 𝜉 + 𝑛 𝐻 𝑏 (𝑟)

であり， $𝑛$ で割って移項すると

1 - 𝐻 𝑏 (𝑟) < 2 l o g 2 (𝑛 + 1) + 2 + 𝜉 𝑛

を得る．

頻度が $1 / 2$ から離れていると左辺が正の定数以上になることを見る． $| 𝑟 - 1 / 2 | \geq 𝛿$ とする．補題 9.3.1 の第 $1$ の主張（二値エントロピー関数の対称性）より $𝐻 𝑏 (𝑟) = 𝐻 𝑏 (1 - 𝑟)$ だから， $𝑟$ を $1 - 𝑟$ に取り替えて $𝑟 \leq 1 / 2 - 𝛿$ としてよい．すると $0 \leq 𝑟 \leq 1 / 2 - 𝛿 \leq 1 / 2$ だから，補題 9.3.1 の第 $3$ の主張（区間 $[0, 1 / 2]$ での単調性）より $𝐻 𝑏 (𝑟) \leq 𝐻 𝑏 (1 / 2 - 𝛿)$ である．いっぽう定理 1.1.5 を $𝑀 = 2$ に当てると $𝐻 𝑏 (1 / 2 - 𝛿) \leq l o g 2 2 = 1$ で，等号は分布が一様のとき，すなわち $1 / 2 - 𝛿 = 1 / 2$ のときに限るが， $𝛿 > 0$ だからそうではない．よって $1 - 𝐻 𝑏 (1 / 2 - 𝛿) > 0$ である．

二つを突き合わせる．いま見たとおり，圧縮できない $𝑥$ が $| 𝑟 - 1 / 2 | \geq 𝛿$ を満たすなら

0 < 1 - 𝐻 𝑏 (12 - 𝛿) \leq 1 - 𝐻 𝑏 (𝑟) < 2 l o g 2 (𝑛 + 1) + 2 + 𝜉 𝑛

である．右辺は，本章の底で読んだ補題 11.2.2 より $𝑛 \to \infty$ で $0$ に収束するから， $𝑛$ を十分大きくとれば $1 - 𝐻 𝑏 (1 / 2 - 𝛿)$ 以下になる．そのような $𝑛$ については上の不等式が成り立ちようがないので，圧縮できないどの $𝑥$ も $| 𝑟 - 1 / 2 | < 𝛿$ を満たす． $◼$

形式化: incompressible_freq_near_half (ソース)

系 13.3.10. 各 $𝑛 \geq 1$ に $𝑥 (𝑛) \in {0, 1} 𝑛$ を一つずつ与え， $𝑛$ が十分大きいところでは $𝑥 (𝑛)$ が定義 13.3.7 の意味で圧縮できないとする．このとき

𝑁 (1 ∣ 𝑥 (𝑛)) 𝑛 ⟶ 12 (𝑛 \to \infty)

である（ $𝑁 (1 ∣ \cdot)$ は定義 2.4.1 の，系列に含まれる $1$ の個数）．

証明. $𝜀 > 0$ とする．定理 13.3.9 を $𝛿 : = 𝜀$ に当てると， $𝑛$ が十分大きければ，圧縮できないどの $𝑥 \in {0, 1} 𝑛$ についても $| 𝑁 (1 ∣ 𝑥) / 𝑛 - 1 / 2 | < 𝜀$ である．仮定より $𝑛$ が十分大きいところで $𝑥 (𝑛)$ は圧縮できないから，二つの「十分大きい」の大きいほうをとれば，それ以上の $𝑛$ について $| 𝑁 (1 ∣ 𝑥 (𝑛)) / 𝑛 - 1 / 2 | < 𝜀$ である． $◼$

形式化: incompressible_seq_freq_tendsto_half (ソース)

定理 13.3.9 の証明が $𝑛$ に要求しているのは， $(2 l o g 2 (𝑛 + 1) + 2 + 𝜉) / 𝑛$ が $1 - 𝐻 𝑏 (1 / 2 - 𝛿)$ 以下になることだけである．この量は $𝑛$ とともに $0$ へ向かうが，向かい方は $l o g 2 𝑛$ を $𝑛$ で割った速さでしかないので， $𝛿$ を小さくとると要求が満たされる $𝑛$ はすぐに大きくなる．数で見ておく．

例 13.3.11（頻度が効きはじめる規模）. $𝛿 = 1 / 10$ とし， $𝜉$ を命題 13.3.3 の定数の一つとする．定理 13.3.9 の証明が $𝑛$ に要求する不等式

2 l o g 2 (𝑛 + 1) + 2 + 𝜉 𝑛 \leq 1 - 𝐻 𝑏 (25)

の右辺は $0.0290494 \dots$ である．左辺を $𝜉 = 0$ として読んでも， $𝑛 = 722$ ではその値が $0.0290799 \dots$ で不等式は成り立たず， $𝑛 = 723$ では $0.0290452 \dots$ となって成り立つ．また $𝑛 = 1000$ でこの不等式が成り立つのは $𝜉 \leq 7$ のときに限る．

証明. 右辺を計算する． $l o g 2 5 = 2.3219280 \dots$ ， $l o g 2 3 = 1.5849625 \dots$ だから $l o g 2 (2 / 5) = 1 - l o g 2 5 = - 1.3219280 \dots$ ， $l o g 2 (3 / 5) = l o g 2 3 - l o g 2 5 = - 0.7369655 \dots$ であり，例 1.1.2 より

𝐻 𝑏 (25) = 25 \times 1.3219280 \dots + 35 \times 0.7369655 \dots = 0.9709505 \dots

である．よって右辺は $0.0290494 \dots$ である．

左辺に移る． $𝜉$ は自然数だから左辺は $𝜉$ について単調に増え， $𝜉 = 0$ のときがいちばん小さい． $l o g 2 723 = 9.4978518 \dots$ だから $𝑛 = 722$ でのその値は $(2 \times 9.4978518 \dots + 2) / 722 = 0.0290799 \dots$ で，右辺より大きい． $l o g 2 724 = 9.4998458 \dots$ だから $𝑛 = 723$ でのその値は $(2 \times 9.4998458 \dots + 2) / 723 = 0.0290452 \dots$ で，右辺より小さい．

$𝑛 = 1000$ を見る． $l o g 2 1001 = 9.9672262 \dots$ だから左辺は $(21.9344525 \dots + 𝜉) / 1000$ であり，これが右辺以下であることは $𝜉 \leq 7.1149 \dots$ と同じで， $𝜉$ が自然数であることと合わせて $𝜉 \leq 7$ と同じである． $◼$

例 13.3.11 の $𝛿 = 1 / 10$ は粗い要求で，頻度が $0.4$ から $0.6$ のあいだにあれば満たされる．それでも，定数を $𝜉 = 0$ と最も甘く見積もってさえ $𝑛 = 722$ では要求が満たされず， $𝑛 = 1000$ で満たされるのは $𝜉$ が $7$ 以下のときに限る．定理 13.3.9 と系 13.3.10 は $𝑛 \to \infty$ での主張であって，手元の長さのブロックについて頻度を保証するものではない．

本節が結んだものを並べておく．平均については定理 13.3.6 で，分布から決まる $𝐻 (𝑝)$ と，分布を見ない機械が一本の系列に払う長さの平均が， $1$ 文字あたりで一致した．個々のブロックについては定理 13.3.9 で，圧縮できないブロックの $1$ の頻度が $1 / 2$ に近いことが分かった．後者は一方向だけの主張である．頻度が $1 / 2$ に近いことは圧縮できないことの帰結であって，逆は成り立たない．

例 13.3.12（交互に並ぶブロック）. 偶数 $𝑛 \geq 2$ に対し， $𝑥 (𝑛) \in {0, 1} 𝑛$ を，第 $𝑖$ 文字が $𝑖$ を $2$ で割った余りであるもの，すなわち $0101 \dots 01$ とする．このとき $𝑁 (1 ∣ 𝑥 (𝑛)) / 𝑛 = 1 / 2$ である（ $𝑁 (1 ∣ \cdot)$ は定義 2.4.1 の，系列に含まれる $1$ の個数）．また定数 $𝑤 \in ℕ$ があって，すべての偶数 $𝑛 \geq 2$ について $𝐾 U (⟨ 𝑥 (𝑛) ⟩ ∣ 𝑛) \leq 𝑤$ である． $𝑤$ は $𝑛$ に依らないから， $𝑛 > 𝑤$ を満たす偶数 $𝑛$ については $𝑥 (𝑛)$ は定義 13.3.7 の条件を満たさない．

証明. $𝑛 = 2 𝑘$ と書く． $𝑥 (𝑛)$ の第 $𝑖$ 文字が $1$ であるのは $𝑖$ が奇数のときで， $0$ 以上 $𝑛$ 未満の奇数は $1, 3, \dots, 2 𝑘 - 1$ の $𝑘$ 個だから $𝑁 (1 ∣ 𝑥 (𝑛)) = 𝑘 = 𝑛 / 2$ である．

上界に移る． $M (𝑧, 𝑦)$ を， $𝑦$ が $2$ 以上の偶数のとき $⟨ 𝑥 (𝑦) ⟩$ とし，そのほかでは値を持たないと定める（第 $1$ 引数は使わない）． $⟨ 𝑥 (𝑦) ⟩$ を求めるには定義 13.3.1 の和を $𝑦$ 項だけ足せばよいので，この対応は有限個の場合分けと有限回の繰り返しで書き下せており，Church–Turing のテーゼより部分計算可能で，定義 13.1.3 の意味で機械である．定理 13.1.7 をこの $M$ に当てて定数 $𝑤 \in ℕ$ をとる．偶数 $𝑛 \geq 2$ について，空列 $𝑠$ をとると $M (𝑠, 𝑛) = ⟨ 𝑥 (𝑛) ⟩$ であり， $| 𝑠 | = 0$ だから $𝐾 U (⟨ 𝑥 (𝑛) ⟩ ∣ 𝑛) \leq 𝑤$ である．

最後の主張は， $𝑤 < 𝑛$ のとき定義 13.3.7 の $𝐾 U (⟨ 𝑥 (𝑛) ⟩ ∣ 𝑛) \geq 𝑛$ が成り立たないことによる． $◼$

例 13.3.12 の列は， $1$ の頻度がちょうど $1 / 2$ でありながら，長さによらない定数ビットの指示で書き出せる．長さ $𝑛$ が条件として渡されているので，指示のほうは「交互に並べろ」とだけ言えばよく， $𝑛$ を書き添える必要がないからである．定理 13.3.9 が言っているのは，圧縮できないブロックが偏った頻度を持ちえないというところまでで，頻度が $1 / 2$ に近いブロックの中には，このように短い記述を持つものがある．

ここまでの $𝐾 U$ は，対象のほうに長さを与える量だった．次節は向きを変え，記述の長さのほうから対象に重みを与える．でたらめに書いた指示がその対象を出す確率として読める重みで，そのためには機械を一つ取り替えなければならない． $U$ のままでは，その重みを全部足したものが $1$ を超えてしまうからである．

情報理論入門（Lean による形式証明つき）・GitHub