11.4 仮説検定と Stein の補題

手元に長さ $𝑛$ の系列が一つある．それが分布 $𝑃$ から出たのか，分布 $𝑄$ から出たのかを当てたい．二つの分布はどちらも分かっていて，分からないのはどちらが真かだけである．この形の問題を 仮説検定 と呼ぶ．二つの候補のうち，はじめは正しいものとして置き，捨てるには証拠が要るとみなす側を 帰無仮説，もう一方を 対立仮説 と呼ぶ．どちらを帰無仮説にとるかで二つの分布の扱いは非対称になり，本節は $𝑃$ の側を帰無仮説にとる．前節までの道具はそのまま使える．系列を見て決めるとは $X 𝑛$ を二つに分けることであり，どちらの誤りも分けた片方の確率を $𝑃 𝑛$ か $𝑄 𝑛$ で測ったものだから，分ける側を型類の合併にとれば前節までの評価がそのまま効く．

答え方を決めると，間違え方は二通り出る．真が $𝑃$ なのに $𝑄$ と答える誤りと，真が $𝑄$ なのに $𝑃$ と答える誤りである． $𝑃$ が全点で正であるかぎりどちらも $0$ にはできない（例 11.4.2）ので，一方を一定の水準に抑えたうえで他方を最小にする，という形に問題を立て直す．抑えるほうを固定すると， $𝑃$ と $𝑄$ が違う分布であるかぎり，最小にしたほうは $𝑛$ とともに指数で落ちる．その指数を下から $𝐷 (𝑃 ‖ 𝑄)$ で押さえるのが Stein の補題（Chernoff–Stein の補題とも呼ぶ）の達成可能性で，上から押さえるのがその逆である．本節はこの二つを示す．

相対エントロピーの三つめの読み方がここで出る．1.6 節では「 $𝑞$ だと思い込んで符号化したために余計に払う符号長」，前節では「 $𝑄$ から見て型 $𝑃$ の系列が出にくい度合い」だった．本節では「 $𝑃$ と $𝑄$ を見分ける難しさ」になる． $𝐷 (𝑃 ‖ 𝑄)$ が大きいほど二つは見分けやすく，第二種の誤りは速く落ちる．本節の主張がその速さを測る．

本章の残る三つの節は，一本の曲線の三つの場所を測る．第一種の誤りの落ちる速さを横軸に，第二種の誤りの落ちる速さを縦軸にとると，横軸が $0$ の端，すなわち第一種の誤りに指数での減り方を求めない端の高さが，本節で測る指数と同じ値になる．二つの速さが等しくなる点に現れるのが 11.5 節の Chernoff 情報であり，曲線の全体が 11.6 節の誤りの指数のトレードオフ関数である．この絵は例 11.6.10 で数値になって戻ってくる．

検定と 2 種類の誤り

定義 11.4.1（検定と 2 種類の誤り）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の分布， $𝑃 𝑛$ ， $𝑄 𝑛$ をそれぞれの $𝑛$ 重の積分布とし， $𝑛 \geq 1$ とする．部分集合 $A 𝑛 \subseteq X 𝑛$ を一つ決め，系列 $𝑥$ が $A 𝑛$ に属するときに $𝑃$ を，属さないときに $𝑄$ を答えることにする．この $A 𝑛$ を 受容域，答え方そのものを検定と呼ぶ．検定の 第一種の誤り と 第二種の誤り を

𝛼 𝑛 (A 𝑛) : = 𝑃 𝑛 (A c 𝑛), 𝛽 𝑛 (A 𝑛) : = 𝑄 𝑛 (A 𝑛)

で定める（ $A c 𝑛 : = X 𝑛 ∖ A 𝑛$ ）．

第一種の誤りは，真の分布が $𝑃$ であるのに $𝑄$ と答えてしまう確率であり，第二種の誤りは，真の分布が $𝑄$ であるのに $𝑃$ と答えてしまう確率である．受容域を広げれば $𝑃$ と答えやすくなるので，第一種の誤りは大きくならず，第二種の誤りは小さくならない．二つはこの向きに引き合う．記号 $𝛼$ ， $𝛽$ は仮説検定の標準的な書き方で，第3章 3.1 節が二状態のマルコフ情報源の遷移確率に使ったものと字が重なるが，あちらはつねに裸で現れ，本章のものはつねに長さの添字と受容域の引数をとるので見分けられる．

形式化上の注記. 定義 11.4.1 が定める受容域・検定・2 種類の誤りに対応する単独の宣言は無い．第一種の誤りを水準以下に抑えるという条件と第二種の誤りの値は，どちらも steinBetaSet (InformationTheory/Shannon/Stein/OptimalExponent.lean) の要素を定める条件の中に現れる．

例 11.4.2（極端な二つの検定）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の分布， $𝑛 \geq 1$ とし， $𝛼 𝑛$ ， $𝛽 𝑛$ を定義 11.4.1 のとおりとすると，次の三つが成り立つ．

$A 𝑛 : = X 𝑛$ ととると $𝛼 𝑛 (A 𝑛) = 0$ ， $𝛽 𝑛 (A 𝑛) = 1$ である．
$A 𝑛 : = \emptyset$ ととると $𝛼 𝑛 (A 𝑛) = 1$ ， $𝛽 𝑛 (A 𝑛) = 0$ である．
$𝑃$ が全点で正ならば， $𝛼 𝑛 (A 𝑛) = 0$ かつ $𝛽 𝑛 (A 𝑛) = 0$ となる $A 𝑛 \subseteq X 𝑛$ は無い．

証明.

$A 𝑛 = X 𝑛$ なら $A c 𝑛 = \emptyset$ だから $𝛼 𝑛 (A 𝑛) = 𝑃 𝑛 (\emptyset) = 0$ であり， $𝛽 𝑛 (A 𝑛) = 𝑄 𝑛 (X 𝑛) = 1$ である．
$A 𝑛 = \emptyset$ なら $A c 𝑛 = X 𝑛$ だから $𝛼 𝑛 (A 𝑛) = 𝑃 𝑛 (X 𝑛) = 1$ であり， $𝛽 𝑛 (A 𝑛) = 𝑄 𝑛 (\emptyset) = 0$ である．
$𝑃$ が全点で正であるとする．このときどの $𝑥 \in X 𝑛$ でも $𝑃 𝑛 ({𝑥}) = \prod 𝑖 < 𝑛 𝑃 (𝑥 𝑖) > 0$ である．したがって $𝛼 𝑛 (A 𝑛) = 𝑃 𝑛 (A c 𝑛) = 0$ となるのは $A c 𝑛 = \emptyset$ のとき，すなわち $A 𝑛 = X 𝑛$ のときに限る．そのとき第 $1$ の主張より $𝛽 𝑛 (A 𝑛) = 1$ であって $0$ ではない．

$◼$

第 $3$ の主張は， $𝑃$ が全点で正であるかぎり，どちらの誤りも $0$ にする検定が無いことを言っている．そこで一方を一定の水準に抑え，もう一方をできるだけ小さくする．抑えるほうを第一種の誤りにとるのが仮説検定の作法であり， $𝑃$ と $𝑄$ の扱いはこの時点で非対称になる．帰無仮説と対立仮説という名前の違いも，この非対称に対応している．

定義 11.4.3（水準 $𝜀$ の最良の第二種の誤り）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の分布， $𝑛 \geq 1$ ， $𝜀 \geq 0$ とし， $𝛼 𝑛$ ， $𝛽 𝑛$ を定義 11.4.1 のとおりとする．第一種の誤りを $𝜀$ 以下に抑える受容域すべてにわたる第二種の誤りの下限を

𝛽 * 𝑛 (𝜀) : = i n f {𝛽 𝑛 (A 𝑛) : A 𝑛 \subseteq X 𝑛, 𝛼 𝑛 (A 𝑛) \leq 𝜀}

と書き，水準 $𝜀$ の最良の第二種の誤り と呼ぶ．

下限をとる集合は空ではない．例 11.4.2 の第 $1$ の主張より $A 𝑛 = X 𝑛$ はどの $𝜀 \geq 0$ でも条件を満たすからである．水準 $𝜀$ を大きくとるほど条件を満たす受容域は増えるので， $𝛽 * 𝑛 (𝜀)$ は大きくならない．以下では水準を固定したまま $𝑛$ を大きくして，この値がどれだけ速く小さくなるかを測る．

形式化: 達成できる第二種の誤りの集合 steinBetaSet，その下限 steinOptimalBeta (ソース)

達成可能性

まず下から，すなわち $- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀)$ を $𝐷 (𝑃 ‖ 𝑄)$ にいくらでも近いところまで押し上げる検定があることを示す．受容域は型の方法で作る．長さ $𝑛$ の型 $𝑃'$ ごとに， $𝑃'$ で平均した対数尤度比 $\sum 𝑎 𝑃' (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎)$ を計算し，それが $𝐷 (𝑃 ‖ 𝑄)$ に近い型の型類だけを集める．型類の中では確率が一定である（命題 11.1.4）ので，この一つの数だけで型類全体の $𝑃 𝑛$ と $𝑄 𝑛$ の比が決まり，第二種の誤りがそのまま抑えられる．第一種の誤りのほうは，型が真の分布に近い系列の確率が $1$ に近づくこと，すなわち第2章定理 2.4.3 から出る．

定理 11.4.4（Stein の補題の達成可能性）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布， $𝜀 \in (0, 1)$ ， $𝛿 > 0$ とし， $𝛽 * 𝑛$ を定義 11.4.3 のとおりとする．このとき，どの $𝑛 \geq 1$ でも $𝛽 * 𝑛 (𝜀) > 0$ であり，十分大きいすべての $𝑛$ について

- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀) \geq 𝐷 (𝑃 ‖ 𝑄) - 𝛿

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. まず $𝛽 * 𝑛 (𝜀)$ が正であることを見る． $𝛼 𝑛 (A 𝑛) \leq 𝜀$ を満たす受容域 $A 𝑛$ をとると， $𝜀 < 1$ より $𝑃 𝑛 (A 𝑛) = 1 - 𝛼 𝑛 (A 𝑛) > 0$ だから $A 𝑛$ は空でなく， $𝑄$ が全点で正だから $𝛽 𝑛 (A 𝑛) = 𝑄 𝑛 (A 𝑛) > 0$ である． $X 𝑛$ の部分集合は有限個しかないので，定義 11.4.3 の下限は有限個の正の数の最小値であり，正である．

次に受容域を作る． $𝑃$ と $𝑄$ は全点で正だから，どの文字でも $l o g 𝑃 (𝑎) 𝑄 (𝑎)$ は有限な数である．長さ $𝑛$ の型 $𝑃'$ のうち

∣ \sum 𝑎 \in X 𝑃' (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎) - 𝐷 (𝑃 ‖ 𝑄) ∣ \leq 𝛿

を満たすものを集め，その型類（定義 11.1.1）を合わせたものを $A 𝑛$ とする．

第二種の誤りを抑える． $𝑥 \in A 𝑛$ をとり $𝑃' : = ˆ 𝑃 𝑥$ とおくと， $𝑃'$ は上の条件を満たす長さ $𝑛$ の型である．命題 11.1.4 を $𝑄$ について，および $𝑃$ について当てると

𝑄 𝑛 ({𝑥}) = e x p (- 𝑛 (𝐻 (𝑃') + 𝐷 (𝑃' ‖ 𝑄))), 𝑃 𝑛 ({𝑥}) = e x p (- 𝑛 (𝐻 (𝑃') + 𝐷 (𝑃' ‖ 𝑃)))

であり，比をとると $𝑄 𝑛 ({𝑥}) = 𝑃 𝑛 ({𝑥}) e x p (- 𝑛 (𝐷 (𝑃' ‖ 𝑄) - 𝐷 (𝑃' ‖ 𝑃)))$ である．相対エントロピーの定義（1.6 節）から

𝐷 (𝑃' ‖ 𝑄) - 𝐷 (𝑃' ‖ 𝑃) = \sum 𝑎 𝑃' (𝑎) l o g 𝑃' (𝑎) 𝑄 (𝑎) - \sum 𝑎 𝑃' (𝑎) l o g 𝑃' (𝑎) 𝑃 (𝑎) = \sum 𝑎 𝑃' (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎)

である（ $𝑃' (𝑎) = 0$ の文字では三つの項がすべて $0$ である）． $A 𝑛$ の定め方よりこの値は $𝐷 (𝑃 ‖ 𝑄) - 𝛿$ 以上だから， $𝑄 𝑛 ({𝑥}) \leq 𝑃 𝑛 ({𝑥}) 𝑒 - 𝑛 (𝐷 (𝑃 ‖ 𝑄) - 𝛿)$ である．これを $𝑥 \in A 𝑛$ について足し合わせ， $𝑃 𝑛 (A 𝑛) \leq 1$ を使うと

𝛽 𝑛 (A 𝑛) = 𝑄 𝑛 (A 𝑛) \leq 𝑒 - 𝑛 (𝐷 (𝑃 ‖ 𝑄) - 𝛿)

を得る．

第一種の誤りを抑える．正の実数 $𝛿'$ を一つとり，第2章の情報源の分布を $𝑃$ として，幅 $𝛿'$ の強典型集合 $𝐴 * (𝑛) 𝛿'$ （定義 2.4.1）を考える（ $𝑃$ は全点で正だから，2.4 節の設定を満たす）． $𝑥 \in 𝐴 * (𝑛) 𝛿'$ ならどの文字でも $| ˆ 𝑃 𝑥 (𝑎) - 𝑃 (𝑎) | \leq 𝛿'$ であり， $𝐷 (𝑃 ‖ 𝑄) = \sum 𝑎 𝑃 (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎)$ だから，三角不等式より

∣ \sum 𝑎 ˆ 𝑃 𝑥 (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎) - 𝐷 (𝑃 ‖ 𝑄) ∣ = ∣ \sum 𝑎 (ˆ 𝑃 𝑥 (𝑎) - 𝑃 (𝑎)) l o g 𝑃 (𝑎) 𝑄 (𝑎) ∣ \leq 𝛿' \sum 𝑎 ∣ l o g 𝑃 (𝑎) 𝑄 (𝑎) ∣

である．右端は $𝛿'$ に比例し，和は $𝑃$ と $𝑄$ だけで決まる有限の数だから， $𝛿'$ を小さくとれば右端を $𝛿$ 以下にできる．そのような $𝛿'$ を一つ選んでおく．すると $𝑥 \in 𝐴 * (𝑛) 𝛿'$ の型 $ˆ 𝑃 𝑥$ は $A 𝑛$ を定める条件を満たすので $𝑥 \in T 𝑛 (ˆ 𝑃 𝑥) \subseteq A 𝑛$ であり， $𝐴 * (𝑛) 𝛿' \subseteq A 𝑛$ である．第2章定理 2.4.3 より $𝑃 𝑛 (𝐴 * (𝑛) 𝛿') \to 1$ だから

𝛼 𝑛 (A 𝑛) = 𝑃 𝑛 (A c 𝑛) \leq 𝑃 𝑛 ((𝐴 * (𝑛) 𝛿') c) ⟶ 0

であり，十分大きい $𝑛$ で $𝛼 𝑛 (A 𝑛) \leq 𝜀$ である．

その $𝑛$ については $A 𝑛$ が定義 11.4.3 の下限をとる範囲に入るから

𝛽 * 𝑛 (𝜀) \leq 𝛽 𝑛 (A 𝑛) \leq 𝑒 - 𝑛 (𝐷 (𝑃 ‖ 𝑄) - 𝛿)

である． $𝛽 * 𝑛 (𝜀)$ は正だから対数がとれ， $l o g$ は単調だから $l o g 𝛽 * 𝑛 (𝜀) \leq - 𝑛 (𝐷 (𝑃 ‖ 𝑄) - 𝛿)$ であり，両辺を $- 𝑛$ で割れば主張を得る． $◼$

形式化: 正であること steinOptimalBeta_pos (ソース)

形式化上の注記. 本文の証明は受容域を型の方法で作り，第一種の誤りを第2章定理 2.4.3 で押さえた．形式化は別の道筋をとる．対数尤度比の相加平均に大数の強法則を当て，その平均が $𝐷 (𝑃 ‖ 𝑄)$ に近い系列の全体 steinTypicalSet (InformationTheory/Shannon/Stein/Achievability.lean) を受容域にとる．指数の下界を述べる宣言は steinOptimalBeta_log_ge_of_achievability (InformationTheory/Shannon/Stein/OptimalExponent.lean) であるが，これは情報源を確率変数の列として受け取る形で述べられており，その列が独立で同分布であること，各項の像が $𝑃$ であること，列全体の像が積分布になることなど，本文の定理 11.4.4 に無い仮定を七つ持つ．結論の式に現れるのは $𝛽 * 𝑛 (𝜀)$ だけで，確率変数の列はどこにも現れない．そこでこの宣言は本文の主張そのものの形式化とはみなさず，ポインタには挙げないことにした．正であることの宣言のほうにはこの七つの仮定は無い．

右辺に $𝜀$ が現れないことに注意しておく．水準を $0$ より大きい範囲でどれだけ厳しくとっても， $- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀)$ は $𝐷 (𝑃 ‖ 𝑄)$ にいくらでも近いところまで下から押さえられる，というのが定理 11.4.4 である．水準 $𝜀$ が効くのは，この不等式が成り立ちはじめる $𝑛$ の大きさのほうである． $𝜀$ が指数そのものに効かないのは，第二種の誤りを抑える段で $𝜀$ を一度も使っていないからである．

逆

達成可能性は，指数 $𝐷 (𝑃 ‖ 𝑄)$ に届く検定があることを言った．逆は，どの検定もそれを大きくは超えられないことを言う．道具は定理 1.8.1，すなわち像測度をとると相対エントロピーは増えない，である．受容域に入るかどうかだけを見る写像で $X 𝑛$ を二点に潰すと，二点の上の相対エントロピーが $𝐷 (𝑃 𝑛 ‖ 𝑄 𝑛)$ 以下になる．右辺を先に計算しておく．

補題 11.4.5. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布， $𝑃 𝑛$ ， $𝑄 𝑛$ をそれぞれの $𝑛$ 重の積分布とし， $𝑛 \geq 1$ とすると

𝐷 (𝑃 𝑛 ∥ 𝑄 𝑛) = 𝑛 𝐷 (𝑃 ‖ 𝑄)

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. $𝑃$ と $𝑄$ は全点で正だから，どの $𝑥 \in X 𝑛$ でも $𝑃 𝑛 ({𝑥}) = \prod 𝑖 < 𝑛 𝑃 (𝑥 𝑖)$ と $𝑄 𝑛 ({𝑥})$ は正で，どの対数も有限な数である．積の対数は和だから，相対エントロピーの定義（1.6 節）より

𝐷 (𝑃 𝑛 ∥ 𝑄 𝑛) = \sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) 𝑛 - 1 \sum 𝑖 = 0 l o g 𝑃 (𝑥 𝑖) 𝑄 (𝑥 𝑖) = 𝑛 - 1 \sum 𝑖 = 0 \sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) l o g 𝑃 (𝑥 𝑖) 𝑄 (𝑥 𝑖)

である（有限個の項の和なので順序を入れ替えてよい）． $𝑖$ を一つ固定し，内側の和を $𝑥 𝑖$ の値で分類する． $𝑥 𝑖 = 𝑎$ を満たす $𝑥$ にわたる $𝑃 𝑛 ({𝑥})$ の和は， $𝑃 (𝑎)$ に残りの座標についての和 $\prod 𝑗 \neq 𝑖 \sum 𝑏 𝑃 (𝑏) = 1$ を掛けたもの，すなわち $𝑃 (𝑎)$ である．よって内側の和は

\sum 𝑎 \in X 𝑃 (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎) = 𝐷 (𝑃 ‖ 𝑄)

に等しい．これが $𝑖$ に依らないので， $𝑖$ について足すと $𝑛 𝐷 (𝑃 ‖ 𝑄)$ になる． $◻$

形式化: klDiv_pi_eq_n_smul (ソース)

定理 11.4.6（Stein の補題の逆）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布， $𝜀 \in (0, 1)$ ， $𝑛 \geq 1$ とし， $𝛽 * 𝑛$ を定義 11.4.3 のとおりとする． $𝛽 * 𝑛 (𝜀)$ は正であり（定理 11.4.4），

- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀) \leq 𝐷 (𝑃 ‖ 𝑄) 1 - 𝜀 + l o g 2 𝑛 (1 - 𝜀)

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. まず， $𝛼 𝑛 (A 𝑛) \leq 𝜀$ を満たす受容域 $A 𝑛 \subseteq X 𝑛$ を一つ固定し， $𝛽 𝑛 (A 𝑛)$ について同じ形の不等式を示す．

$A 𝑛 = X 𝑛$ のときは $𝛽 𝑛 (A 𝑛) = 1$ で $- 1 𝑛 l o g 𝛽 𝑛 (A 𝑛) = 0$ であり，右辺は定理 1.6.1 より非負だから不等式は成り立つ．以下 $A 𝑛 \neq X 𝑛$ とする． $𝛼 𝑛 (A 𝑛) \leq 𝜀 < 1$ より $𝑃 𝑛 (A 𝑛) = 1 - 𝛼 𝑛 (A 𝑛) > 0$ だから $A 𝑛$ は空でなく， $𝑄$ が全点で正だから $𝑄 𝑛 (A 𝑛)$ と $𝑄 𝑛 (A c 𝑛)$ はどちらも正である．

受容域に入るかどうかだけを見る写像 $𝑓 : X 𝑛 \to {0, 1}$ を， $𝑥 \in A 𝑛$ のとき $𝑓 (𝑥) : = 1$ ，そうでないとき $𝑓 (𝑥) : = 0$ で定める．像測度（定理 1.8.1）は ${0, 1}$ 上の分布で， $𝑓 * 𝑃 𝑛$ は $1$ に $𝑃 𝑛 (A 𝑛)$ ， $0$ に $𝑃 𝑛 (A c 𝑛)$ を与え， $𝑓 * 𝑄 𝑛$ は $1$ に $𝑄 𝑛 (A 𝑛)$ ， $0$ に $𝑄 𝑛 (A c 𝑛)$ を与える．定理 1.8.1 と補題 11.4.5 より

𝑃 𝑛 (A 𝑛) l o g 𝑃 𝑛 (A 𝑛) 𝑄 𝑛 (A 𝑛) + 𝑃 𝑛 (A c 𝑛) l o g 𝑃 𝑛 (A c 𝑛) 𝑄 𝑛 (A c 𝑛) = 𝐷 (𝑓 * 𝑃 𝑛 ∥ 𝑓 * 𝑄 𝑛) \leq 𝐷 (𝑃 𝑛 ∥ 𝑄 𝑛) = 𝑛 𝐷 (𝑃 ‖ 𝑄)

である．

左辺を下から抑える． $𝑄 𝑛 (A c 𝑛) \leq 1$ だから第 $2$ 項は $𝑃 𝑛 (A c 𝑛) l o g 𝑃 𝑛 (A c 𝑛)$ 以上であり，第 $1$ 項は $𝑃 𝑛 (A 𝑛) l o g 𝑃 𝑛 (A 𝑛) - 𝑃 𝑛 (A 𝑛) l o g 𝑄 𝑛 (A 𝑛)$ に等しい． $𝑃 𝑛 (A c 𝑛) = 1 - 𝑃 𝑛 (A 𝑛)$ だから，二つを合わせると左辺は

- 𝐻 𝑏 (𝑃 𝑛 (A 𝑛)) - 𝑃 𝑛 (A 𝑛) l o g 𝑄 𝑛 (A 𝑛)

以上である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）． $𝐻 𝑏$ の値は $2$ 点の上の分布のエントロピーだから定理 1.1.5 より $l o g 2$ 以下であり，よって

- 𝑃 𝑛 (A 𝑛) l o g 𝑄 𝑛 (A 𝑛) \leq 𝑛 𝐷 (𝑃 ‖ 𝑄) + l o g 2

である．

$𝑄 𝑛 (A 𝑛) \leq 1$ より $- l o g 𝑄 𝑛 (A 𝑛) \geq 0$ であり， $𝑃 𝑛 (A 𝑛) = 1 - 𝛼 𝑛 (A 𝑛) \geq 1 - 𝜀 > 0$ だから

(1 - 𝜀) (- l o g 𝑄 𝑛 (A 𝑛)) \leq - 𝑃 𝑛 (A 𝑛) l o g 𝑄 𝑛 (A 𝑛) \leq 𝑛 𝐷 (𝑃 ‖ 𝑄) + l o g 2

である．両辺を $𝑛 (1 - 𝜀)$ で割ると， $𝛽 𝑛 (A 𝑛) = 𝑄 𝑛 (A 𝑛)$ だから

- 1 𝑛 l o g 𝛽 𝑛 (A 𝑛) \leq 𝐷 (𝑃 ‖ 𝑄) 1 - 𝜀 + l o g 2 𝑛 (1 - 𝜀)

を得る．

最後に $𝛽 * 𝑛 (𝜀)$ に移る． $X 𝑛$ の部分集合は有限個しかないから，定義 11.4.3 の下限は最小値であり， $𝛼 𝑛 (A 𝑛) \leq 𝜀$ を満たすある $A 𝑛$ で $𝛽 𝑛 (A 𝑛) = 𝛽 * 𝑛 (𝜀)$ となる．その $A 𝑛$ に上で示したことを当てればよい． $◼$

形式化: steinOptimalBeta_log_le_of_converse (ソース)

上界には因子 $1 1 - 𝜀$ が残っている．出どころは，第一種の誤りを $𝜀$ まで許したために， $- l o g 𝑄 𝑛 (A 𝑛)$ に掛かる重み $𝑃 𝑛 (A 𝑛)$ が $1$ から $1 - 𝜀$ まで下がりうることである．水準を緩めるほどこの因子は大きくなり，上界は $𝐷 (𝑃 ‖ 𝑄)$ から離れる．達成可能性の側（定理 11.4.4）が $𝜀$ に依らなかったのと対照的である．

系 11.4.7（水準 $𝜀$ での指数の挟み込み）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布， $𝜀 \in (0, 1)$ とし， $𝛽 * 𝑛$ を定義 11.4.3 のとおりとすると

𝐷 (𝑃 ‖ 𝑄) \leq l i m i n f 𝑛 \to \infty (- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀)) \leq l i m s u p 𝑛 \to \infty (- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀)) \leq 𝐷 (𝑃 ‖ 𝑄) 1 - 𝜀

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. 定理 11.4.4 より，どの $𝛿 > 0$ についても，十分大きいすべての $𝑛$ で $- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀) \geq 𝐷 (𝑃 ‖ 𝑄) - 𝛿$ である．よって下極限は $𝐷 (𝑃 ‖ 𝑄) - 𝛿$ 以上であり， $𝛿 > 0$ は任意だから $𝐷 (𝑃 ‖ 𝑄)$ 以上である．

定理 11.4.6 より，どの $𝑛 \geq 1$ についても $- 1 𝑛 l o g 𝛽 * 𝑛 (𝜀) \leq 𝐷 (𝑃 ‖ 𝑄) 1 - 𝜀 + l o g 2 𝑛 (1 - 𝜀)$ である．第 $2$ 項は $𝑛 \to \infty$ で $0$ に収束するから，上極限は $𝐷 (𝑃 ‖ 𝑄) 1 - 𝜀$ 以下である．下極限が上極限以下であることと合わせて，三つの不等式を得る． $◼$

形式化上の注記. 系 11.4.7 の両側の不等式は定理 11.4.4 と定理 11.4.6 の形でそれぞれ単独に形式化されているが，二つを合わせた挟み込みに対応する単独の宣言は無い．上端が $𝜀$ に依らず $𝐷 (𝑃 ‖ 𝑄)$ になる形も形式化されていない．それに近いのは steinOptimalBeta_log_le_of_strong_converse (InformationTheory/Shannon/StrongStein.lean) で，こちらは $𝜀$ で割る因子を持たないかわりに，任意にとれる $𝛿 > 0$ ぶんの余裕と，第一種の誤りに関わる補正項とが結論の右端に残る．この宣言も情報源を確率変数の列として受け取る形で述べられており，達成可能性の側の下界と同じ七つの仮定を持つ．

本書が示したのは，水準 $𝜀$ を固定したときのこの挟み込みまでである．上端が $𝐷 (𝑃 ‖ 𝑄)$ に一致すること，すなわち Stein の補題の通常の述べ方は示していない．そこまで詰めるには，第一種の誤りを $𝜀$ まで許したままの検定についても，第二種の誤りの指数が $𝐷 (𝑃 ‖ 𝑄)$ を超えないことを示す必要がある．本書がとったのはデータ処理不等式の経路で，定理 11.4.6 の証明が $- l o g 𝑄 𝑛 (A 𝑛)$ に掛かる重みを $1 - 𝜀$ で下から抑えるところで因子が入るから，この経路のままでは因子は消えない． $𝜀$ を $0$ に近づけると右端は $𝐷 (𝑃 ‖ 𝑄)$ に近づくので，水準を厳しくとるほど上下の隔たりは狭くなる．

数値で見る

例 11.4.8（二値の Stein の指数の数値）. $X = {0, 1}$ とし， $𝑃$ を $𝑃 (0) = 0.1$ ， $𝑃 (1) = 0.9$ で定まる分布， $𝑄$ を $𝑄 (0) = 𝑄 (1) = 1 / 2$ で定まる分布， $𝜀 : = 0.05$ とする． $𝑃 𝑛$ ， $𝑄 𝑛$ をそれぞれの $𝑛$ 重の積分布， $ˆ 𝑃 𝑥$ を定義 11.1.1 の型， $𝛼 𝑛$ ， $𝛽 𝑛$ を定義 11.4.1 のとおり， $𝛽 * 𝑛$ を定義 11.4.3 のとおりとすると，次の四つが成り立つ．

$𝐷 (𝑃 ‖ 𝑄)$ の値は約 $0.3681$ ナットである．
$𝐷 (𝑃 ‖ 𝑄) \leq l i m i n f 𝑛 (- 1 𝑛 l o g 𝛽 * 𝑛 (0.05)) \leq l i m s u p 𝑛 (- 1 𝑛 l o g 𝛽 * 𝑛 (0.05)) \leq 𝐷 (𝑃 ‖ 𝑄) / 0.95$ であり，右端の値は約 $0.3874$ である．
$𝑛 = 100$ のときの定理 11.4.6 の右辺の値は約 $0.3947$ である．
$A 100 : = {𝑥 \in X 100 : | 100 ˆ 𝑃 𝑥 (0) - 10 | \leq 6}$ ととると， $𝛼 100 (A 100)$ の値は約 $0.0284$ で $0.05$ 以下であり， $𝛽 100 (A 100) = 2 - 100 \sum 16 𝑘 = 4 (100 𝑘)$ で，その値は約 $1.30 \times 10 - 12$ である．とくに $- 1100 l o g 𝛽 * 100 (0.05) \geq 0.2736$ である．

証明.

補題 11.2.5 より $𝐷 (𝑃 ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (𝑃 (0)) = l o g 2 - 𝐻 𝑏 (0.1)$ である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）． $𝐻 𝑏 (0.1) = 0.32508 \dots$ ， $l o g 2 = 0.69314 \dots$ だから，値は $0.36806 \dots$ である．
$𝑃$ と $𝑄$ はどちらも全点で正で $0.05 \in (0, 1)$ だから，系 11.4.7 を $𝜀 : = 0.05$ ととって当てると挟み込みを得る．右端の値は第 $1$ の主張より $0.36806 \dots / 0.95 = 0.38743 \dots$ である．
定理 11.4.6 の右辺は $𝐷 (𝑃 ‖ 𝑄) 0.95 + l o g 2 100 \times 0.95 = 0.38743 \dots + 0.00729 \dots = 0.39473 \dots$ である．
この $A 100$ は，定理 11.4.4 の証明が $𝛿 : = 0.14$ ととって作る受容域にほかならない．実際，長さ $100$ の型 $𝑃'$ について $𝑃' (0) = 𝑘 / 100$ と書くと，相対エントロピーの定義（1.6 節）と $l o g 0.2 - l o g 1.8 = l o g 19 = - l o g 9$ から

\sum 𝑎 𝑃' (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎) - 𝐷 (𝑃 ‖ 𝑄) = (𝑘 100 - 0.1) (l o g 0.2 - l o g 1.8) = l o g 9 100 (10 - 𝑘)

であり， $l o g 9 = 2.19722 \dots$ だから，この絶対値が $0.14$ 以下であることは $| 𝑘 - 10 | \leq 100 \times 0.14 / l o g 9 = 6.371 \dots$ と同値で， $𝑘$ は整数だからこれは $| 𝑘 - 10 | \leq 6$ と同値である．系列 $𝑥$ に含まれる $0$ の個数を $𝑘 (𝑥)$ と書くと $ˆ 𝑃 𝑥 (0) = 𝑘 (𝑥) / 100$ だから， $A 100$ は $4 \leq 𝑘 (𝑥) \leq 16$ を満たす系列の全体である． $0$ の個数が $𝑘$ である長さ $100$ の系列は， $100$ 個の位置から $0$ を置く $𝑘$ 個を選ぶ選び方の数だけあるので $(100 𝑘)$ 個であり，そのどれについても $𝑃 100 ({𝑥}) = 0.1 𝑘 0.9 100 - 𝑘$ ， $𝑄 100 ({𝑥}) = 2 - 100$ である．よって

𝛼 100 (A 100) = 3 \sum 𝑘 = 0 (100 𝑘) 0.1 𝑘 0.9 100 - 𝑘 + 100 \sum 𝑘 = 17 (100 𝑘) 0.1 𝑘 0.9 100 - 𝑘, 𝛽 100 (A 100) = 2 - 100 16 \sum 𝑘 = 4 (100 𝑘)

であり，どちらも有限個の項の和で，計算すると前者は $0.02843 \dots$ ，後者は $1.30296 \dots \times 10 - 12$ である．前者は $0.05$ 以下だから $A 100$ は定義 11.4.3 の下限をとる範囲に入り， $𝛽 * 100 (0.05) \leq 𝛽 100 (A 100)$ である． $𝛽 * 100 (0.05)$ は定理 11.4.4 より正で， $l o g$ は単調だから，対数をとって $- 100$ で割ると $- 1100 l o g 𝛽 * 100 (0.05) \geq 0.27366 \dots$ を得る． $◼$

この $𝑃$ は例 11.2.6 と同じ偏ったコインである．系 11.4.7 が指数に与える上下の隔たりは $0.02$ ほどで，水準 $𝜀$ を $0.05$ より緩めるとこの隔たりは広がる．有限の $𝑛$ での上界（第 $3$ の主張）が極限の上界より大きいのは定理 11.4.6 の第 $2$ 項のぶんで， $𝑛$ を大きくすればその差は $0$ に向かう．第 $4$ の主張は，型で切った検定を一つ実際に作って $𝑛 = 100$ での値を出したものである． $0$ の個数が $10$ の前後 $6$ 以内という受容域だけで，第一種の誤りは $0.05$ を下回り，第二種の誤りは $10 - 12$ の桁まで落ちる．そこから $- 1100 l o g 𝛽 * 100 (0.05) \geq 0.2736$ が出て，第 $3$ の主張の上界 $0.3947$ と挟むと， $𝑛 = 100$ での指数はこの二つの数のあいだにある．幅が広いのは， $𝛿$ を $0.14$ ととったぶん受容域を広めに作ったからで， $𝛿$ を小さくとって $𝑛$ を大きくすれば下からの評価は $𝐷 (𝑃 ‖ 𝑄)$ に近づく（定理 11.4.4）．

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

本節は第一種の誤りを水準で抑え，第二種の誤りだけを小さくした．二つの誤りを同時に小さくしたいときには，どちらか一方を優先する理由がなくなり，指数も $𝐷 (𝑃 ‖ 𝑄)$ ではない別の量になる．それを次節で扱う．

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