11.3 Sanov の定理

前節は型を一つ指定したときの確率を挟み込んだ（定理 11.2.1）．指数に残るのは相対エントロピーだけで， $𝑄$ から見て型が $𝑃$ の系列が出る確率は $𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄)$ の前後にあった．本節は指定するものを，型一つから分布の集合に替える． $X$ 上の分布の集合 $E$ を先に決めておき，長さ $𝑛$ の系列を $𝑄$ から引いたとき，その経験分布が $E$ に落ちる確率を問う．

この確率が小さいことは，前節までの二つから見当がつく． $𝐷 (𝑃 ‖ 𝑄)$ が $0$ になるのは $𝑃 = 𝑄$ のときに限る（定理 1.6.1）ので， $𝑄$ 自身から離れたところに $E$ を置けば， $E$ に属するどの型 $𝑃$ でも $𝐷 (𝑃 ‖ 𝑄)$ は正であり，その型類の確率は定理 11.2.1 より $𝑛$ とともに指数で落ちる．落ちる速さは型ごとに違うが，型の個数は $𝑛$ の多項式で抑えられている（命題 11.1.3）．有限個の正の数の和は，最大の項以上で，最大の項に項の個数を掛けたもの以下である．したがって $1 𝑛 l o g$ をとって $𝑛$ を大きくすると多項式倍の差は消え，残るのはいちばん大きい項の指数，すなわち $𝐷 (\cdot ‖ 𝑄)$ がいちばん小さい型の指数だけになる．これが本節の主張で，Sanov の定理と呼ばれる．

示し方は上下に分ける．上界は，型の個数の多項式評価と定理 11.2.1 の上界を合わせた数え上げで出る．下界は， $E$ の中の分布を一つ選び，その型類ぶんだけで確率を下から押さえて出す．二つを合わせると，指数が一点で決まるという主張になる．

集合に属する型

定義 11.3.1（集合に属する型）. $X$ を空でない有限アルファベットとし， $E$ を $X$ 上の分布の集合とする． $𝑛 \geq 1$ に対し， $E$ に属する長さ $𝑛$ の型（定義 11.1.1）の全体を

E 𝑛 : = {𝑃 \in E : 𝑃 は長さ 𝑛 の型}

と書く．

$E$ は分布の集合であって，系列の集合ではない．系列の側でこれに対応するのは，型が $E$ に入る系列の全体 ${𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}$ である．どの系列もただ一つの型をもつ（定義 11.1.1）から，この集合は $E 𝑛$ に属する型の型類を重なりなく合わせたものにほかならない． $E$ が無限に多くの分布を含んでいてもよいが，長さ $𝑛$ の型は有限個しかない（命題 11.1.3）ので $E 𝑛$ は有限集合である． $E$ の中に長さ $𝑛$ の型が一つも無いこともあり，そのときこの系列の集合は空になる．本節が測るのは， $X$ 上の分布 $𝑄$ とその $𝑛$ 重の積分布 $𝑄 𝑛$ に対する，この集合の確率である．

上界

定理 11.3.2 の $𝛾$ は $i n f 𝑃 \in E 𝐷 (𝑃 ‖ 𝑄)$ と思って読めばよい．条件を $E 𝑛$ に属する型についてだけ課しているのは，証明が型の上の和しか使わないからである．

定理 11.3.2（Sanov の上界）. $X$ を空でない有限アルファベット， $𝑄$ を $X$ 上の全点で正の分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とし， $E$ を $X$ 上の分布の集合， $E 𝑛$ を定義 11.3.1 のとおりとする． $𝑛 \geq 1$ とし，実数 $𝛾$ が， $E 𝑛$ に属するどの型 $𝑃$ についても $𝛾 \leq 𝐷 (𝑃 ‖ 𝑄)$ を満たすとすると

𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}) \leq (𝑛 + 1) | X | 𝑒 - 𝑛 𝛾

であり，左辺が正ならば

1 𝑛 l o g 𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}) \leq - 𝛾 + | X | l o g (𝑛 + 1) 𝑛

である（ $ˆ 𝑃 𝑥$ は定義 11.1.1 の型， $𝐷$ は 1.6 節の相対エントロピー）．

証明. どの系列もただ一つの型をもつ（定義 11.1.1）から， ${𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}$ は $E 𝑛$ に属する型 $𝑃$ の型類 $T 𝑛 (𝑃)$ を重なりなく合わせたものであり

𝑄 𝑛 ({𝑥 : ˆ 𝑃 𝑥 \in E}) = \sum 𝑃 \in E 𝑛 𝑄 𝑛 (T 𝑛 (𝑃))

である．右辺の各項に定理 11.2.1 の上界を当てると $𝑄 𝑛 (T 𝑛 (𝑃)) \leq 𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄)$ であり，仮定より $𝛾 \leq 𝐷 (𝑃 ‖ 𝑄)$ であり，指数関数は単調増加（ $l o g$ の単調性と $l o g 𝑒 𝑠 = 𝑠$ から出る）だから $𝑄 𝑛 (T 𝑛 (𝑃)) \leq 𝑒 - 𝑛 𝛾$ である．項の個数は $E$ に属する長さ $𝑛$ の型の個数だから，長さ $𝑛$ の型の総数以下であり，命題 11.1.3 より $(𝑛 + 1) | X |$ 以下である．よって和は $(𝑛 + 1) | X | 𝑒 - 𝑛 𝛾$ 以下である．

第 $2$ の不等式は第 $1$ の両辺の対数をとって $𝑛$ で割ったものである．左辺が正なら対数がとれ， $l o g$ は単調だから

l o g 𝑄 𝑛 ({𝑥 : ˆ 𝑃 𝑥 \in E}) \leq | X | l o g (𝑛 + 1) - 𝑛 𝛾

であり，両辺を $𝑛$ で割れば主張を得る． $◼$

形式化上の注記. 定理 11.3.2 に対応する単独の宣言は無い．typeClassByCount_union_Qn_le_inf (InformationTheory/Shannon/Sanov/LDP.lean) が，型を有限個集めた族について，その合併の確率を「族の要素数に $𝑒 - 𝑛 𝛾$ を掛けたもの」で抑える形を与える．この族の添字は各文字の出現回数の組で，その組の全体の要素数がちょうど $(𝑛 + 1) | X |$ であることを typeCountIndex_card (InformationTheory/Shannon/Sanov/LDP.lean) が与えるから，族の要素数はこれ以下である．二つの合成である． $𝑛$ を大きくした形の系 11.3.3 のほうは単独で形式化されている．

型の個数の多項式評価は，ここで初めて本来の役目を果たす．型ごとの上界 $𝑒 - 𝑛 𝛾$ を項の個数だけ足し合わせても，掛かるのは $𝑛$ の多項式だけなので， $1 𝑛 l o g$ をとると $0$ に向かう項しか足されない．そのことを極限の形にしたのが次の系である．

系 11.3.3. $X$ を空でない有限アルファベット， $𝑄$ を $X$ 上の全点で正の分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とし， $E$ を $X$ 上の分布の集合， $E 𝑛$ を定義 11.3.1 のとおりとする．実数 $𝛾$ が，すべての $𝑛 \geq 1$ と $E 𝑛$ に属するどの型 $𝑃$ についても $𝛾 \leq 𝐷 (𝑃 ‖ 𝑄)$ を満たすとする． $𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E})$ が正であるような $𝑛$ に限って考えることにすると，どの $𝜀 > 0$ についても，ある $𝑛 0$ があって， $𝑛 \geq 𝑛 0$ を満たすそのような $𝑛$ のすべてについて

1 𝑛 l o g 𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}) \leq - 𝛾 + 𝜀

が成り立つ．

証明. 定理 11.3.2 の第 $2$ の不等式より，左辺は $- 𝛾 + | X | l o g (𝑛 + 1) 𝑛$ 以下である．したがって $| X | l o g (𝑛 + 1) 𝑛$ が $0$ に収束することを見れば，与えられた $𝜀$ に対してその収束から $𝑛 0$ がとれる．

補題 11.2.2 より $l o g (𝑛 + 1) 𝑛 \to 0$ であり， $| X |$ は $𝑛$ に依らない有限の数だから， $| X | l o g (𝑛 + 1) 𝑛 \to 0$ である． $◼$

形式化: sanov_ldp_upper_bound (ソース)

$𝛾$ としてどれだけ大きい値がとれるかで，系 11.3.3 の強さが決まる．とれるのは，すべての $𝑛$ の $E 𝑛$ を通して $𝐷 (\cdot ‖ 𝑄)$ を下から抑える値までである． $E$ の上で $𝐷 (\cdot ‖ 𝑄)$ を最小にする分布があれば，その値は条件を満たす $𝛾$ の一つになる．同じ値が下からの評価でも現れることを，次に見る．

下界

下界は， $E$ の中の分布を一つ選び，その型類ぶんだけを数えて出す．ただし選んだ分布がそのまま長さ $𝑛$ の型であるとは限らない．長さ $𝑛$ の型がとる値は $0, 1 / 𝑛, \dots, 1$ に限られる（定義 11.1.1）からである．そこで，選んだ分布に近い型を作って代用する．各文字について $𝑛$ 倍した値を整数に切り下げ，切り下げで足りなくなったぶんを一つの文字にまとめて押し付ければ，個数の総和が $𝑛$ になって型になる．以下， $⌊ 𝑡 ⌋$ で実数 $𝑡$ 以下の最大の整数を表す（ $⌊ 𝑡 ⌋ \leq 𝑡 < ⌊ 𝑡 ⌋ + 1$ である）．選ぶ分布は $˜ 𝑃$ と書く．ここで選ぶ分布に最適性は要らないので星印を付けない．

定義 11.3.4（丸め型）. $X$ を空でない有限アルファベット， $˜ 𝑃$ を $X$ 上の分布， $𝑎 0$ を $X$ の文字とし， $𝑛 \geq 1$ とする．

˜ 𝑃 𝑛 (𝑎) : = ⌊ 𝑛 ˜ 𝑃 (𝑎) ⌋ 𝑛 (𝑎 \neq 𝑎 0), ˜ 𝑃 𝑛 (𝑎 0) : = 1 - \sum 𝑎 \neq 𝑎 0 ⌊ 𝑛 ˜ 𝑃 (𝑎) ⌋ 𝑛

で定まる $X$ 上の関数 $˜ 𝑃 𝑛$ を， $𝑎 0$ を端数の引き受け手とする $˜ 𝑃$ の 丸め型 と呼ぶ（ $⌊ 𝑡 ⌋$ は $𝑡$ 以下の最大の整数）．

形式化上の注記. 丸め型に対応する宣言は roundedTypeIndex (InformationTheory/Shannon/Sanov/RoundedTypeSequence.lean) であるが，覆っている範囲が本文より狭い．本文は端数の引き受け手 $𝑎 0$ を選べる形にしてあるのに対し，形式化はその文字をアルファベットの中の一つに固定しており，しかもどの文字であるかを述べていない．あとの例 11.3.8 が示すとおり，丸め型が集合に入るかどうかは引き受け手の選び方で変わるので，この差は形だけのものではない．

補題 11.3.5（丸め型は長さ $𝑛$ の型であり，各文字で元の分布に収束する）. $X$ を空でない有限アルファベット， $˜ 𝑃$ を $X$ 上の分布， $𝑎 0$ を $X$ の文字とし，各 $𝑛 \geq 1$ について $˜ 𝑃 𝑛$ を $𝑎 0$ を端数の引き受け手とする $˜ 𝑃$ の丸め型（定義 11.3.4）とする．このとき，どの $𝑛 \geq 1$ でも $˜ 𝑃 𝑛$ は長さ $𝑛$ の型（定義 11.1.1）であり，どの文字 $𝑎$ についても $˜ 𝑃 𝑛 (𝑎) \to ˜ 𝑃 (𝑎)$ （ $𝑛 \to \infty$ ）である．

証明. まず $˜ 𝑃 𝑛$ が長さ $𝑛$ の型であることを見る． $𝑎 \neq 𝑎 0$ については $𝑛 ˜ 𝑃 𝑛 (𝑎) = ⌊ 𝑛 ˜ 𝑃 (𝑎) ⌋$ で，これは非負整数である． $𝑎 0$ については $𝑛 ˜ 𝑃 𝑛 (𝑎 0) = 𝑛 - \sum 𝑎 \neq 𝑎 0 ⌊ 𝑛 ˜ 𝑃 (𝑎) ⌋$ で，これも整数であり， $⌊ 𝑡 ⌋ \leq 𝑡$ と $\sum 𝑎 ˜ 𝑃 (𝑎) = 1$ から

\sum 𝑎 \neq 𝑎 0 ⌊ 𝑛 ˜ 𝑃 (𝑎) ⌋ \leq \sum 𝑎 \neq 𝑎 0 𝑛 ˜ 𝑃 (𝑎) \leq 𝑛

なので非負である．よって $(𝑛 ˜ 𝑃 𝑛 (𝑎)) 𝑎 \in X$ は総和が $𝑛$ の非負整数の組であり，各文字をその個数だけ並べた系列の型は $˜ 𝑃 𝑛$ だから， $˜ 𝑃 𝑛$ は長さ $𝑛$ の型である．

次に $˜ 𝑃 𝑛$ が各文字で $˜ 𝑃$ に収束することを見る． $𝑎 \neq 𝑎 0$ については $⌊ 𝑡 ⌋ \leq 𝑡 < ⌊ 𝑡 ⌋ + 1$ より $0 \leq ˜ 𝑃 (𝑎) - ˜ 𝑃 𝑛 (𝑎) < 1 / 𝑛$ である． $𝑎 0$ については， $˜ 𝑃 𝑛$ と $˜ 𝑃$ の総和がどちらも $1$ だから $˜ 𝑃 𝑛 (𝑎 0) - ˜ 𝑃 (𝑎 0) = \sum 𝑎 \neq 𝑎 0 (˜ 𝑃 (𝑎) - ˜ 𝑃 𝑛 (𝑎))$ であり，右辺の各項は $0$ 以上 $1 / 𝑛$ 未満だから，差の絶対値は $| X | / 𝑛$ 以下である．よってどの文字でも $˜ 𝑃 𝑛 (𝑎) \to ˜ 𝑃 (𝑎)$ である． $◻$

形式化上の注記. 補題 11.3.5 の二つの主張に対応する宣言は roundedTypeIndex_sum と roundedTypeIndex_tendsto（どちらも InformationTheory/Shannon/Sanov/RoundedTypeSequence.lean）であるが，どちらも端数の引き受け手を固定した丸め型についてのもので，覆っている範囲は本文より狭い．

定理 11.3.6（Sanov の下界）. $X$ を空でない有限アルファベット， $𝑄$ を $X$ 上の全点で正の分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とし， $E$ を $X$ 上の分布の集合， $E 𝑛$ を定義 11.3.1 のとおりとする． $˜ 𝑃$ を $X$ 上の分布， $𝑎 0$ を $X$ の文字とし，各 $𝑛 \geq 1$ について $˜ 𝑃 𝑛$ を $𝑎 0$ を端数の引き受け手とする $˜ 𝑃$ の丸め型（定義 11.3.4）とする．十分大きいすべての $𝑛$ について $˜ 𝑃 𝑛 \in E 𝑛$ であるならば，十分大きい $𝑛$ で $𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E})$ は正であり

l i m i n f 𝑛 \to \infty 1 𝑛 l o g 𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}) \geq - 𝐷 (˜ 𝑃 ‖ 𝑄)

である（ $ˆ 𝑃 𝑥$ は定義 11.1.1 の型， $𝐷$ は 1.6 節の相対エントロピー）．

証明. 補題 11.3.5 より，どの $𝑛 \geq 1$ でも $˜ 𝑃 𝑛$ は長さ $𝑛$ の型であり，どの文字でも $˜ 𝑃 𝑛 (𝑎) \to ˜ 𝑃 (𝑎)$ である．

仮定より，ある $𝑛 0$ があって $𝑛 \geq 𝑛 0$ のとき $˜ 𝑃 𝑛 \in E 𝑛$ ，とくに $˜ 𝑃 𝑛 \in E$ である．型が $˜ 𝑃 𝑛$ である系列は型が $E$ に属するから

T 𝑛 (˜ 𝑃 𝑛) \subseteq {𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}

であり，包含している側の集合の確率のほうが小さくないから $𝑄 𝑛 (T 𝑛 (˜ 𝑃 𝑛)) \leq 𝑄 𝑛 ({𝑥 : ˆ 𝑃 𝑥 \in E})$ である．左辺は定理 11.2.1 の下界より $(𝑛 + 1) - | X | 𝑒 - 𝑛 𝐷 (˜ 𝑃 𝑛 ‖ 𝑄)$ 以上で，これは正だから， $𝑛 \geq 𝑛 0$ では右辺も正である．

$l o g$ は単調だから， $𝑛 \geq 𝑛 0$ について

1 𝑛 l o g 𝑄 𝑛 ({𝑥 : ˆ 𝑃 𝑥 \in E}) \geq 1 𝑛 l o g 𝑄 𝑛 (T 𝑛 (˜ 𝑃 𝑛))

である． $˜ 𝑃 𝑛$ は長さ $𝑛$ の型で各文字で $˜ 𝑃$ に収束するから，系 11.2.3 より右辺は $- 𝐷 (˜ 𝑃 ‖ 𝑄)$ に収束する．よって左辺の下極限は $- 𝐷 (˜ 𝑃 ‖ 𝑄)$ 以上である． $◼$

形式化上の注記. 定理 11.3.6 に対応する宣言は sanov_ldp_lower_bound_pointwise (InformationTheory/Shannon/Sanov/LiminfBound.lean) であるが，覆っている範囲が本文より狭い．丸め型の端数の引き受け手が固定されていることに加えて，形式化は $˜ 𝑃$ が全点で正であることも仮定に持つ．

二つを合わせる

定理 11.3.7（Sanov の定理）. $X$ を空でない有限アルファベット， $𝑄$ を $X$ 上の全点で正の分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とし， $E$ を $X$ 上の分布の集合， $E 𝑛$ を定義 11.3.1 のとおりとする． $𝑃 ⋆$ を $X$ 上の分布， $𝑎 0$ を $X$ の文字とし， $𝑃 ⋆ 𝑛$ を $𝑎 0$ を端数の引き受け手とする $𝑃 ⋆$ の丸め型（定義 11.3.4）とする．次の二つが成り立つとする．

すべての $𝑛 \geq 1$ と $E 𝑛$ に属するどの型 $𝑃$ についても $𝐷 (𝑃 ⋆ ‖ 𝑄) \leq 𝐷 (𝑃 ‖ 𝑄)$ である．
十分大きいすべての $𝑛$ について $𝑃 ⋆ 𝑛 \in E 𝑛$ である．

このとき，十分大きい $𝑛$ で $𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E})$ は正であり

1 𝑛 l o g 𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}) ⟶ - 𝐷 (𝑃 ⋆ ‖ 𝑄) (𝑛 \to \infty)

である（ $ˆ 𝑃 𝑥$ は定義 11.1.1 の型， $𝐷$ は 1.6 節の相対エントロピー）．

証明. 第 $2$ の仮定から定理 11.3.6 が使えて，十分大きい $𝑛$ でこの確率は正であり，その下極限は $- 𝐷 (𝑃 ⋆ ‖ 𝑄)$ 以上である．

上からの評価には系 11.3.3 を $𝛾 : = 𝐷 (𝑃 ⋆ ‖ 𝑄)$ ととって当てる．第 $1$ の仮定がその $𝛾$ についての条件そのものだから，どの $𝜀 > 0$ についても，ある $𝑛 0$ があって， $𝑛 \geq 𝑛 0$ でこの確率が正であるかぎり

1 𝑛 l o g 𝑄 𝑛 ({𝑥 : ˆ 𝑃 𝑥 \in E}) \leq - 𝐷 (𝑃 ⋆ ‖ 𝑄) + 𝜀

である．十分大きい $𝑛$ では確率は正なのだから，上極限は $- 𝐷 (𝑃 ⋆ ‖ 𝑄) + 𝜀$ 以下であり， $𝜀 > 0$ は任意だから，上極限は $- 𝐷 (𝑃 ⋆ ‖ 𝑄)$ 以下である．

下極限が $- 𝐷 (𝑃 ⋆ ‖ 𝑄)$ 以上で，上極限が $- 𝐷 (𝑃 ⋆ ‖ 𝑄)$ 以下だから，この数列は収束して極限は $- 𝐷 (𝑃 ⋆ ‖ 𝑄)$ である． $◼$

形式化上の注記. 定理 11.3.7 に対応する宣言は sanov_ldp_equality (InformationTheory/Shannon/Sanov/TendstoSandwich.lean) である．二つの仮定の置き方は本文と同じで，第 $1$ の仮定が最小化子であること，第 $2$ の仮定が丸め型が最終的に $E 𝑛$ に入ることに対応する．ただし定理 11.3.6 と同じ理由で覆っている範囲が本文より狭い．丸め型の端数の引き受け手が固定されており， $𝑃 ⋆$ が全点で正であることも仮定に持つ．

読み方は素直である．経験分布が $E$ に落ちる確率の指数は， $E$ に属する型のうち $𝑄$ にいちばん近いもの一つで決まり，残りの型は指数の水準では何も寄与しない．第 $1$ の仮定は $𝑃 ⋆$ がその一つであること，すなわちすべての $𝑛$ の $E 𝑛$ を通した最小化子であることを求めている．第 $2$ の仮定は， $E$ が型で近づけられる形をしていることを求めている．たとえば $E$ が一点だけからなり，その一点がどの $𝑛$ でも長さ $𝑛$ の型でなければ，どの $𝑛$ でも $E 𝑛$ は空になり，第 $2$ の仮定は成り立たない．このとき系列の集合も空で，確率は $0$ である．

第 $2$ の仮定を確かめる手筋は決まっている． $E$ が凸で，境界から離れた内側の分布が一つとれるなら，最小化子をその分布のほうへ少しだけ寄せればよい．寄せた先も内側にあるから，その丸め型は十分大きい $𝑛$ で $E$ に入り，第 $2$ の仮定が成り立つ．寄せたぶん $𝐷 (\cdot ‖ 𝑄)$ の値は上がるが，寄せ幅を $0$ に近づければその損は消える．この手筋は定理 11.6.9 の証明で実際に使う．

数値で見る

例 11.3.8（コインの表が $7$ 割以上出る確率）. $X = {0, 1}$ とし， $1$ を表と読む． $𝑄$ を $𝑄 (0) = 𝑄 (1) = 1 / 2$ で定まる分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とし， $E : = {𝑃 : 𝑃 は X 上の分布で 𝑃 (1) \geq 0.7}$ とする． $ˆ 𝑃 𝑥$ を定義 11.1.1 の型， $𝐻 𝑏$ を例 1.1.2 の二値エントロピー関数とし， $𝑃 ⋆$ を $𝑃 ⋆ (0) = 0.3$ ， $𝑃 ⋆ (1) = 0.7$ で定まる分布とすると，次の四つが成り立つ．

$E$ に属するどの分布 $𝑃$ についても $𝐷 (𝑃 ⋆ ‖ 𝑄) \leq 𝐷 (𝑃 ‖ 𝑄)$ である（ $𝐷$ は 1.6 節の相対エントロピー）．
$𝐷 (𝑃 ⋆ ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (0.7)$ であり，その値は約 $0.0823$ ナットである．
$1 𝑛 l o g 𝑄 𝑛 ({𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 \in E}) ⟶ - (l o g 2 - 𝐻 𝑏 (0.7))$ （ $𝑛 \to \infty$ ）である．
端数の引き受け手を $𝑎 0 : = 0$ ととった $𝑃 ⋆$ の丸め型（定義 11.3.4）は， $𝑛$ が $10$ の倍数でないかぎり $E$ に属さない．とくに，その選び方では定理 11.3.7 の第 $2$ の仮定は成り立たない．

証明.

補題 11.2.5 より， $X$ 上のどの分布 $𝑃$ についても $𝐷 (𝑃 ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (𝑃 (0))$ である． $𝑃 \in E$ とすると $𝑃 (1) \geq 0.7$ だから $𝑃 (0) \leq 0.3$ であり， $0 \leq 𝑃 (0) \leq 0.3 \leq 1 / 2$ だから補題 9.3.1 の第 $3$ の主張より $𝐻 𝑏 (𝑃 (0)) \leq 𝐻 𝑏 (0.3)$ である． $𝑃 ⋆ (0) = 0.3$ だから， $l o g 2$ から引く向きに直すと $𝐷 (𝑃 ⋆ ‖ 𝑄) \leq 𝐷 (𝑃 ‖ 𝑄)$ を得る．
補題 11.2.5 を $𝑃 ⋆$ に当てると $𝐷 (𝑃 ⋆ ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (𝑃 ⋆ (1)) = l o g 2 - 𝐻 𝑏 (0.7)$ である． $𝐻 𝑏 (0.7) = - 0.7 l o g 0.7 - 0.3 l o g 0.3 = 0.61086 \dots$ ， $l o g 2 = 0.69314 \dots$ だから，差は $0.08228 \dots$ である．
定理 11.3.7 の仮定を，端数の引き受け手を $𝑎 0 : = 1$ ととって確かめる．第 $1$ の仮定は， $E 𝑛 \subseteq E$ だから第 $1$ の主張から従う．第 $2$ の仮定を見る．丸め型は $𝑃 ⋆ 𝑛 (0) = ⌊ 0.3 𝑛 ⌋ / 𝑛$ ， $𝑃 ⋆ 𝑛 (1) = 1 - ⌊ 0.3 𝑛 ⌋ / 𝑛$ である． $𝑛 𝑃 ⋆ 𝑛 (0) = ⌊ 0.3 𝑛 ⌋$ と $𝑛 𝑃 ⋆ 𝑛 (1) = 𝑛 - ⌊ 0.3 𝑛 ⌋$ はどちらも非負整数で和は $𝑛$ だから， $0$ を $⌊ 0.3 𝑛 ⌋$ 個並べたあと $1$ を並べた系列の型は $𝑃 ⋆ 𝑛$ であり， $𝑃 ⋆ 𝑛$ は長さ $𝑛$ の型である．また $⌊ 0.3 𝑛 ⌋ \leq 0.3 𝑛$ より $𝑃 ⋆ 𝑛 (0) \leq 0.3$ だから $𝑃 ⋆ 𝑛 (1) \geq 0.7$ であり， $𝑃 ⋆ 𝑛 \in E$ である．よってどの $𝑛 \geq 1$ でも $𝑃 ⋆ 𝑛 \in E 𝑛$ で，第 $2$ の仮定も成り立つ． $𝑄$ は全点で正だから定理 11.3.7 が使えて，第 $2$ の主張と合わせて結論を得る．
端数の引き受け手を $𝑎 0 : = 0$ にとると丸め型は $𝑃 ⋆ 𝑛 (1) = ⌊ 0.7 𝑛 ⌋ / 𝑛$ である． $0.7 𝑛 = 7 𝑛 / 10$ は， $7$ と $10$ が互いに素だから $𝑛$ が $10$ の倍数のときに限り整数であり，整数でなければ $⌊ 0.7 𝑛 ⌋ < 0.7 𝑛$ だから $𝑃 ⋆ 𝑛 (1) < 0.7$ で， $𝑃 ⋆ 𝑛 \notin E$ である． $10$ の倍数でない $𝑛$ はいくらでも大きくとれるから，「十分大きいすべての $𝑛$ で $𝑃 ⋆ 𝑛 \in E 𝑛$ 」は成り立たない．

$◼$

第 $3$ と第 $4$ の主張は，端数の引き受け手の選び方が仮定の成否を左右することを示している．制約 $𝑃 (1) \geq 0.7$ が緩む側の文字に端数を押し付ければ丸め型は $E$ に入り，きつくなる側に押し付ければ入らない． $𝑛 = 11$ が後者の例で， $⌊ 7.7 ⌋ / 11 = 7 / 11$ は $0.7$ より小さい．

指数の値 $0.0823$ が言っているのは， $1 𝑛 l o g$ をとった量が $- 0.0823$ に近づくということであって，有限の $𝑛$ での確率そのものを与えるものではない．公平なコインを投げて表が $7$ 割以上出るのはめったに起きないが，その「めったに」の速さは，表の割合を $0.7$ に固定した分布が公平なコインからどれだけ隔たっているかだけで決まる．

形式化上の注記. 例 11.3.8 の数値に対応する宣言は無い．形式化には，具体的な分布を入れて Sanov の指数を計算した実例が置かれていない．

本節は，経験分布が指定した集合に落ちる確率を測った．測ったのは $𝑄$ から引いた系列についてであり，集合 $E$ は $𝑄$ とは関わりなく先に決めておいた．次節は $E$ にあたるものを，二つの分布のどちらが真かを当てるという目的から決める．そこでも指数に現れるのは相対エントロピーで，型の方法がそのまま効く．

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