13.6 二部記述と最小記述長

13.4 節と 13.5 節は，一つに固定した機械 $V$ について，記述長・重み・停止の三つを調べてきた．本節は記述の作り方のほうに戻る．第12章定義 12.2.1 の型による二段符号は，系列を「まず型を送り，次に型類の中の位置を送る」と分けて書いた．前半が系列の型を，後半が型だけでは決まらないぶんを担う．同じ分け方を，分布も情報源も持たない一つの自然数に当てるのが本節である．型にあたるのは $𝑥$ を含む有限集合 $𝑆$ で，位置にあたるのは $𝑆$ の中での $𝑥$ の番号である．

分け方を変えても記述の長さは変えられない，というのが本節の結論である．どんな $𝑆$ をとっても，二つに分けた記述は定数のぶんを除いて $𝐾 V (𝑥)$ より短くならず（定理 13.6.3），いちばんうまい $𝑆$ をとれば $𝐾 V (𝑥)$ と定数の差まで縮む（定理 13.6.7）．そのうえで， $𝑆$ が $𝑥$ をどこまで説明していると言えるかを，定数のゆるみを許して定める．定めるのは枠だけである．モデルの大きさや記述長に制限を課したときにどの $𝑆$ が残るかは，本節では扱わない．

有限集合を記述する

定義 13.6.1（有限集合の符号とモデルの記述長）. 自然数の有限列に自然数を対応させる符号化を一つ固定する．有限列から自然数を求める手続きと，自然数から有限列を復元する手続きがどちらも書き下せるようなものをとる（たとえば，各項の二進表示の自己限定形（定義 13.4.3）をこの順につなぎ，先頭にもう一つ $1$ を置いたビット列が表す自然数でよい）． $𝑆 \subseteq ℕ$ を空でない有限集合とし， $𝑆$ の要素を小さい順に並べた有限列に，固定した符号化が与える自然数を $⟨ 𝑆 ⟩$ と書く（定義 13.3.1 と同じ役どころの，別の符号化である．本節の $⟨ \cdot ⟩$ はつねに有限集合を引数にとり，定義 13.3.1 のそれはつねに系列を引数にとる）． $𝐾 V (⟨ 𝑆 ⟩)$ を $𝑆$ の モデルの記述長 と呼ぶ．

形式化: 符号 modelCode，モデルの記述長 modelComplexity (ソース)

形式化上の注記. 形式化が固定した符号化は，括弧の中に挙げたものではなく，Mathlib がもつ自然数の有限列の標準の符号化である．定義 13.6.1 が符号化に課しているのはどちらの向きの手続きも書き下せることだけで，本節の主張の証明もそれしか使わないから，どちらをとっても主張は成り立つ．符号化に依るのは，主張に現れる定数の値だけである．

括弧の中に挙げた符号化が実際に読み解けることは，定義 13.4.3 で見たとおりである．自己限定形はどこで終わるかを自分で告げるので，つないだ列を先頭から順に区切っていける．先頭にもう一つ $1$ を置いたのは，全体を一つの自然数の二進表示として読むためで，そうしないと先頭の $0$ の並びが読み落とされる． $𝑆$ の要素を小さい順に並べたのは，同じ集合に二つの列が対応しないようにするためである．

二部記述の長さは，考えとしては， $𝑆$ を書く長さに $𝑆$ の中での位置を書く桁を足したものである．位置は $0$ 以上 $| 𝑆 |$ 未満の自然数だから，桁は $⌈ l o g 2 | 𝑆 | ⌉$ で足りる．

定義 13.6.2（二部記述の長さ）. $𝑆 \subseteq ℕ$ を空でない有限集合とし

ℓ 2 P (𝑆) : = 𝐾 V (⟨ 𝑆 ⟩) + 4 ⌈ l o g 2 | 𝑆 | ⌉

と定め， $𝑆$ による 二部記述の長さ と呼ぶ（ $⌈ \cdot ⌉$ は 4.4 節の天井関数である）．

形式化: twoPartLength (ソース)

$ℓ 2 P$ は有限集合を引数にとる．第12章定義 12.2.1 の $ℓ T 𝑛$ は系列を引数にとり添字 $𝑛$ を持つので，二つは別の量である．第 $1$ 項がモデルの記述長（定義 13.6.1）で，第 $2$ 項が位置を書く長さにあたるが，そこに現れるのは桁数そのものではなく，その $4$ 倍である．本書の $V$ に記述を渡す単位では，位置の桁に倍率が二度かかるからである．一度目は，位置とモデルの記述の切れ目が読む側に分かるように位置を自己限定形（定義 13.4.3）にするところ，二度目は，組み立てた記述を $V$ に渡すところで，どちらも長さを $2$ 倍にする．次の定理の証明がその二段である．

定理 13.6.3（二部記述による上界）. 定数 $𝜒 \in ℕ$ があって，すべての $𝑥 \in ℕ$ と， $𝑥$ を含むすべての有限集合 $𝑆 \subseteq ℕ$ について

𝐾 V (𝑥) \leq ℓ 2 P (𝑆) + 𝜒

が成り立つ．

証明. 復元する手続きを先に書き下す． $M (𝑧, 𝑦)$ を，位置を読む・モデルを復元する・その位置の要素を返す，の三段で次のように定める（第 $2$ 引数は使わない）．位置を読むところでは， $𝑧$ の二進表示から先頭の $1$ を落とした列を $𝑢$ とし， $𝑢$ の先頭から最初の $0$ までの $1$ の個数を $𝑚$ として，その $0$ の直後の $𝑚$ ビットを二進表示として読んだ自然数を $𝑖$ とする．モデルを復元するところでは， $𝑢$ の残りのビット列を $𝑒$ として $U (𝑒, 0)$ を求め，その値に固定した符号化の復元を当てて自然数の有限列を得る．最後に，その列の先頭を位置 $0$ と数えて，位置 $𝑖$ にある項を返す．以上のどこかで形が合わなければ， $M (𝑧, 𝑦)$ は値を持たないとする（形が合わないのは， $𝑧$ の二進表示が空列である， $𝑢$ に $0$ が現れない， $𝑢$ の長さが $𝑚$ ビットに足りない， $U (𝑒, 0)$ から自然数の有限列が得られない，列の項の個数が $𝑖$ 以下である，の五つの場合である）．この対応は，有限個の場合分けと， $U$ を走らせるところと，固定した符号化から列を復元するところからなり，どれも計算の手続きで書き下せるから，Church–Turing のテーゼより部分計算可能であり，とくに定義 13.1.3 の意味で機械である．定理 13.1.7 をこの $M$ に当てて定数 $𝑏 \in ℕ$ をとり， $𝜒 : = 2 𝑏 + 4$ と置く．

$𝑥 \in ℕ$ と， $𝑥$ を含む有限集合 $𝑆 \subseteq ℕ$ をとる． $𝑥 \in 𝑆$ だから $𝑆$ は空でなく， $⟨ 𝑆 ⟩$ と $ℓ 2 P (𝑆)$ が定まる． $𝑆$ の要素を小さい順に並べたときの $𝑥$ の位置を，先頭を $0$ と数えて $𝑖$ とすると $0 \leq 𝑖 < | 𝑆 |$ である．命題 13.1.5 を $𝑦 : = 0$ に当てて， $| 𝑒 | = 𝐾 U (⟨ 𝑆 ⟩)$ かつ $U (𝑒, 0) = ⟨ 𝑆 ⟩$ を満たすビット列 $𝑒$ をとる． $𝑢$ を， $𝑖$ の二進表示の自己限定形（定義 13.4.3）の後ろに $𝑒$ をつないだビット列とし， $𝑠$ を $𝑢$ の先頭に $1$ を置いたビット列とする．先頭が $1$ だから，定義 13.1.2 より $𝑠$ が表す自然数の二進表示は $𝑠$ そのものであり， $M$ の手続きはそこから $𝑖$ と $𝑒$ をこの順に読み取る．よって $M (𝑠, 0) = 𝑥$ であり，長さは

| 𝑠 | = (2 | 𝑖 | + 1) + 𝐾 U (⟨ 𝑆 ⟩) + 1

だから，定理 13.1.7 より $𝐾 U (𝑥) \leq 2 | 𝑖 | + 𝐾 U (⟨ 𝑆 ⟩) + 𝑏 + 2$ である．

位置の桁数を抑える． $𝐴 : = ⌈ l o g 2 | 𝑆 | ⌉$ と置くと $𝐴 \geq l o g 2 | 𝑆 |$ だから $2 𝐴 \geq | 𝑆 | > 𝑖$ である． $𝑖 = 0$ なら $| 𝑖 | = 0 \leq 𝐴$ である． $𝑖 \geq 1$ なら， $𝑖$ の二進表示の桁数を $𝑗$ として，先頭の桁が $1$ であることから $𝑖 \geq 2 𝑗 - 1$ であり， $2 𝑗 - 1 \leq 𝑖 < 2 𝐴$ と補題 8.2.5 より $𝑗 \leq 𝐴$ である．どちらの場合も $| 𝑖 | \leq 𝐴$ である．

$𝐾 V$ に直す．命題 13.4.6 を $𝑥$ と $⟨ 𝑆 ⟩$ のそれぞれに当てると $𝐾 V (𝑥) = 2 𝐾 U (𝑥) + 1$ と $2 𝐾 U (⟨ 𝑆 ⟩) = 𝐾 V (⟨ 𝑆 ⟩) - 1$ だから

𝐾 V (𝑥) \leq 2 (2 | 𝑖 | + 𝐾 U (⟨ 𝑆 ⟩) + 𝑏 + 2) + 1 = 4 | 𝑖 | + 𝐾 V (⟨ 𝑆 ⟩) + 2 𝑏 + 4

である． $| 𝑖 | \leq 𝐴$ と定義 13.6.2 より右辺は $ℓ 2 P (𝑆) + 𝜒$ 以下である． $◼$

形式化: prefixComplexity_le_twoPartLength (ソース)

定理 13.6.3 は，どんな $𝑆$ をとっても，定数のぶんを除けばその二部記述の長さで $𝑥$ を書けると言っている．裏を返せば， $𝑆$ をうまく選んでも，二部記述の長さが定数のぶんを超えて $𝐾 V (𝑥)$ を下回ることはない．

$𝑆$ の選び方には両端がある．一方の端は一点集合 $𝑆 = {𝑥}$ で，モデルが $𝑥$ そのものを書き下し，位置は何も担わない．もう一方の端は $𝑥$ を含む大きな集合で，モデルはほとんど何も言わず，位置が全部を担う．定理 13.6.3 はどちらについても上界を与えるから，どちらへ寄せても $𝐾 V (𝑥)$ を定数のぶんを超えて下回ることはない．二つの端を長さで比べることに，本節の $ℓ 2 P$ では意味がない．定義 13.6.2 が位置の桁を $4$ 倍しているので，位置が担うぶんだけが膨らみ，比べた差はその倍率を映すからである．以下では一点集合の端だけを押さえる．

命題 13.6.4. 定数 $𝜒 \in ℕ$ があって，すべての $𝑥 \in ℕ$ について $𝐾 V (⟨ {𝑥} ⟩) \leq 𝐾 V (𝑥) + 𝜒$ が成り立つ（ $⟨ \cdot ⟩$ は定義 13.6.1 のとおり）．

証明. 機械を先に作る． $M (𝑧, 𝑦)$ を次のように定める（第 $2$ 引数は使わない）． $𝑧$ の二進表示が空列なら値を持たない．そうでなければ，その二進表示から先頭の $1$ を落とした列を $𝑒$ とし， $U (𝑒, 0)$ を求めてその値を $𝑤$ とし， $⟨ {𝑤} ⟩$ を返す． $U$ を走らせるところと，一つの自然数からなる列に固定した符号化を当てるところは計算の手続きで書き下せるから，Church–Turing のテーゼより $M$ は部分計算可能であり，とくに定義 13.1.3 の意味で機械である．定理 13.1.7 をこの $M$ に当てて定数 $𝑏 \in ℕ$ をとり， $𝜒 : = 2 𝑏 + 2$ と置く．

$𝑥 \in ℕ$ とする．命題 13.1.5 を $𝑦 : = 0$ に当てて， $| 𝑒 | = 𝐾 U (𝑥)$ かつ $U (𝑒, 0) = 𝑥$ を満たすビット列 $𝑒$ をとり， $𝑠$ を $𝑒$ の先頭に $1$ を置いたビット列とする．先頭が $1$ だから，定義 13.1.2 より $𝑠$ が表す自然数の二進表示は $𝑠$ そのものであり， $M (𝑠, 0) = ⟨ {𝑥} ⟩$ である．よって定理 13.1.7 より $𝐾 U (⟨ {𝑥} ⟩) \leq | 𝑠 | + 𝑏 = 𝐾 U (𝑥) + 𝑏 + 1$ である．命題 13.4.6 を $⟨ {𝑥} ⟩$ と $𝑥$ のそれぞれに当てると

𝐾 V (⟨ {𝑥} ⟩) = 2 𝐾 U (⟨ {𝑥} ⟩) + 1 \leq 2 𝐾 U (𝑥) + 2 𝑏 + 3 = 𝐾 V (𝑥) + 𝜒

である． $◼$

形式化: modelComplexity_singleton_le (ソース)

最小記述長

定義 13.6.5（最小記述長）. $𝑥 \in ℕ$ に対し

ℓ 2 P * (𝑥) : = m i n {ℓ 2 P (𝑆) : 𝑆 \subseteq ℕ は有限集合で 𝑥 \in 𝑆}

と定め， $𝑥$ の 最小記述長 と呼ぶ．

形式化: mdlComplexity (ソース)

命題 13.6.6. $𝑥 \in ℕ$ とすると， $𝑥 \in 𝑆$ かつ $ℓ 2 P (𝑆) = ℓ 2 P * (𝑥)$ を満たす有限集合 $𝑆 \subseteq ℕ$ が存在する．

証明. 一点集合 ${𝑥}$ は $𝑥$ を含む有限集合だから，定義 13.6.5 の最小をとる集合は空でない自然数の集合であり，最小元をもつ．その最小元は $ℓ 2 P * (𝑥)$ にほかならず，しかも $𝑥$ を含むある有限集合 $𝑆$ についての $ℓ 2 P (𝑆)$ だから，その $𝑆$ が求めるものである． $◼$

形式化: mdlComplexity_spec (ソース)

定理 13.6.7. 定数 $𝜒 \in ℕ$ があって，すべての $𝑥 \in ℕ$ について

ℓ 2 P * (𝑥) \leq 𝐾 V (𝑥) + 𝜒 かつ 𝐾 V (𝑥) \leq ℓ 2 P * (𝑥) + 𝜒

が成り立つ．

証明. 命題 13.6.4 の定数を $𝜒 1$ ，定理 13.6.3 の定数を $𝜒 2$ とし， $𝜒$ を $𝜒 1$ と $𝜒 2$ の大きいほうとする． $𝑥 \in ℕ$ とする．

第 $1$ の不等式を示す． $| {𝑥} | = 1$ で $l o g 2 1 = 0$ だから $⌈ l o g 2 | {𝑥} | ⌉ = 0$ であり，定義 13.6.2 より $ℓ 2 P ({𝑥}) = 𝐾 V (⟨ {𝑥} ⟩)$ である．一点集合 ${𝑥}$ は $𝑥$ を含む有限集合だから定義 13.6.5 より $ℓ 2 P * (𝑥) \leq ℓ 2 P ({𝑥})$ であり，命題 13.6.4 と合わせて $ℓ 2 P * (𝑥) \leq 𝐾 V (𝑥) + 𝜒 1 \leq 𝐾 V (𝑥) + 𝜒$ である．

第 $2$ の不等式を示す．命題 13.6.6 より $𝑥 \in 𝑆$ かつ $ℓ 2 P (𝑆) = ℓ 2 P * (𝑥)$ を満たす有限集合 $𝑆$ がある．定理 13.6.3 をこの $𝑥$ と $𝑆$ に当てて $𝐾 V (𝑥) \leq ℓ 2 P (𝑆) + 𝜒 2 = ℓ 2 P * (𝑥) + 𝜒 2 \leq ℓ 2 P * (𝑥) + 𝜒$ である． $◼$

形式化: mdlComplexity_sub_prefixComplexity_le (ソース)

定理 13.6.7 は，記述を二つに分けても損も得もしないと言っている．どんな分け方をしても，定数のぶんを除いて $𝐾 V (𝑥)$ より短くはならず，いちばんよい分け方をとれば定数の差まで届く．したがって，二部記述に意味があるとすれば長さそのものではなく，どの $𝑆$ がその長さを実現するかのほうである． $𝑆$ は $𝑥$ について言えることを集めた対象であり，位置のほうは $𝑆$ を知ってもなお残るばらつきである．

一致するのは定数の差までであって，値そのものではない． $𝐾 V$ の値を返す手続きが無いことは定理 13.5.1 で見たが， $ℓ 2 P *$ についても同じだ，とは定理 13.6.7 からは出ない．本書は $ℓ 2 P *$ の計算可能性を述べない．

次の定義は，定数のゆるみを許して「 $𝑆$ が $𝑥$ を説明しきっている」という条件を書く．

コルモゴロフ十分統計量

定義 13.6.8（コルモゴロフ十分統計量）. $𝜒, 𝑥 \in ℕ$ とする．有限集合 $𝑆 \subseteq ℕ$ が $𝑥$ の ゆるみ $𝜒$ のコルモゴロフ十分統計量 であるとは， $𝑥 \in 𝑆$ かつ $ℓ 2 P (𝑆) \leq 𝐾 V (𝑥) + 𝜒$ が成り立つことをいう．

形式化: IsSufficientStatistic (ソース)

語を一つ断っておく．第1章 1.9 節が十分と呼んだのは，確率変数 $𝑋$ を要約する統計量 $𝑇$ であった．本節が十分と呼ぶのは自然数を含む有限集合であって，確率変数でも統計量でもない．同じ「十分」を冠していても別の対象についての語なので，混ぜて読まないこと．読み方のほうは通じている．第1章では $𝑇 (𝑋)$ を知れば $𝜃$ について $𝑋$ 以上のことは分からない，というのが十分の内容だった．本節では， $𝑆$ を知ったあとに残るのは $𝑆$ の中での位置だけで，その位置を書くのに要る長さは $𝑆$ の記述と合わせてもゆるみ $𝜒$ の範囲で最短に収まっている，というのが内容である．どちらも「これ以上絞れるものは残っていない」という条件である．

命題 13.6.9. 定数 $𝜒 \in ℕ$ があって，すべての $𝑥 \in ℕ$ について，一点集合 ${𝑥}$ は $𝑥$ のゆるみ $𝜒$ のコルモゴロフ十分統計量である．

証明. 命題 13.6.4 の定数を $𝜒$ とし， $𝑥 \in ℕ$ とする． $𝑥 \in {𝑥}$ である．また $| {𝑥} | = 1$ で $l o g 2 1 = 0$ だから $⌈ l o g 2 | {𝑥} | ⌉ = 0$ であり，定義 13.6.2 より $ℓ 2 P ({𝑥}) = 𝐾 V (⟨ {𝑥} ⟩)$ である．命題 13.6.4 より右辺は $𝐾 V (𝑥) + 𝜒$ 以下だから，定義 13.6.8 の二つの条件が満たされる． $◼$

形式化: exists_isSufficientStatistic_singleton (ソース)

命題 13.6.9 は，定義 13.6.8 の退化した場合である．一点集合は $𝑥$ そのものを書き下しているだけなのに，ある定数のゆるみをとればつねに十分統計量になる．定義 13.6.8 は単独では何も絞らない，ということである．

では，どういう $𝑆$ を見たいのか．見たいのは，モデルの記述長が $𝐾 V (𝑥)$ よりずっと短く，それでいて十分であるような $𝑆$ である．そういう $𝑆$ があれば， $𝑥$ の記述は「短く書けるモデル」と「その中での位置」に割れていて，前者が $𝑥$ の中の規則的な部分を，後者がモデルを知ってもなお残るばらつきを担う，と読める．第12章の型による二段符号で，前半が系列の型を，後半が型だけでは決まらないぶんを担っていたのと同じ構図である．本書はこの読みを主張にはしない．

系 13.6.10. 定数 $𝜒 \in ℕ$ があって，すべての $𝑥 \in ℕ$ について

- l o g 2 𝑃 V (𝑥) - 𝜒 \leq ℓ 2 P * (𝑥) \leq 2 (- l o g 2 𝑃 V (𝑥)) + 1 + 𝜒

が成り立つ．

証明. 定理 13.6.7 の定数を $𝜒$ とし， $𝑥 \in ℕ$ とする．左の不等式は，定理 13.4.10 の左の不等式と定理 13.6.7 の第 $2$ の不等式をつないで

- l o g 2 𝑃 V (𝑥) \leq 𝐾 V (𝑥) \leq ℓ 2 P * (𝑥) + 𝜒

とし， $𝜒$ を移項すれば出る．右の不等式は，定理 13.6.7 の第 $1$ の不等式と定理 13.4.10 の右の不等式をつないで

ℓ 2 P * (𝑥) \leq 𝐾 V (𝑥) + 𝜒 \leq 2 (- l o g 2 𝑃 V (𝑥)) + 1 + 𝜒

とすれば出る． $◼$

形式化上の注記. 系 13.6.10 に対応する単独の宣言は無い．定理 13.4.10 に紐付けた二つの宣言と定理 13.6.7 に紐付けた宣言をつなげば得られる．三つはどれも同じ prefixComplexity を経由するので，つなぐときに対象を取り替える必要はない．

本章が $𝐾 V$ を抑えた式を並べておく．命題 13.4.6 の $2 𝐾 U (𝑥) + 1$ は等式だから，いちばん細かい．定理 13.4.10 は $- l o g 2 𝑃 V (𝑥)$ とその $2$ 倍に $1$ を足したもので挟んだ．定理 13.6.7 は $ℓ 2 P * (𝑥)$ と定数の差で一致することを言う．系 13.6.10 は後の二つを直接比べたもので，最小記述長と $- l o g 2$ をとった万能確率も，やはり係数 $2$ と定数のゆるみの範囲で互いを決める．三つのどれも，値を求める役には立たない．定理 13.2.3 のとおり $𝐾 U$ を求める手続きは無く，定理 13.5.1 のとおり $𝐾 V$ についても同じだからである．それでも三つが互いを定数と係数の範囲で決め合うことには意味がある．記述の短さ，でたらめなプログラムが当てる重みの大きさ，そして二つに分けた記述の短さが，同じ一つのことを測っているからである．

本章の出発点は，一本の系列の単純さを分布によらずに測ることだった．13.1 節から 13.3 節は素朴な記述長でそれを測り，1 文字あたりの平均がエントロピーに一致することを見た．13.4 節から本節までは機械を語頭のない形に取り替え，記述長が重みとも二部記述とも定数倍の範囲で同じものを測ることを見た．いっぽう，値を求める手続きが無いことを本章が示したのは， $𝐾 U$ （定理 13.2.3）， $𝐾 V$ （定理 13.5.1）， $Ω$ （定理 13.5.8）の三つである．測り方が定まっているのに測れない，というのが本章の残す形である．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．