11.5 Bayes 誤り確率と Chernoff 情報

前節は二つの誤りを対等に扱わなかった．第一種の誤りを一定の水準で抑え，そのうえで第二種の誤りだけを小さくしたからである．どちらを帰無仮説にするかを決める理由がないときには，この非対称を持ち込みたくない．そこで立て方を変える．真の分布が $𝑃$ と $𝑄$ のどちらであるかを先に確率 $1 / 2$ ずつで選んでおき，出てきた系列を見てそれを当てる．誤る確率は二種類の誤りを $1 / 2$ ずつの重みで足したものになり，これを小さくすることが目標になる．本節はこの誤り確率も， $𝑃$ と $𝑄$ が違う分布であれば $𝑛$ とともに指数で落ちること，そしてその指数が $𝐷 (𝑃 ‖ 𝑄)$ とは別の量になることを示す．

答え方を一つ決める．事前確率が等しいのだから，系列 $𝑥$ を見て $𝑃 𝑛 ({𝑥})$ と $𝑄 𝑛 ({𝑥})$ を比べ，大きいほうの仮説を答えることにする．真が $𝑃$ で $𝑄$ と答えてしまうのは $𝑃 𝑛 ({𝑥}) < 𝑄 𝑛 ({𝑥})$ となる $𝑥$ が出たときで，その確率は $𝑃 𝑛$ で測る．真が $𝑄$ で $𝑃$ と答えてしまうのは $𝑃 𝑛 ({𝑥}) \geq 𝑄 𝑛 ({𝑥})$ となる $𝑥$ が出たときで，その確率は $𝑄 𝑛$ で測る．どちらの場合でも， $𝑥$ が誤りに寄与させるのは $𝑃 𝑛 ({𝑥})$ と $𝑄 𝑛 ({𝑥})$ の小さいほうである．事前確率の $1 / 2$ を掛けて $𝑥$ について足すと，次の形になる．

Bayes 誤り確率

定義 11.5.1（Bayes 誤り確率）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の分布， $𝑃 𝑛$ ， $𝑄 𝑛$ をそれぞれの $𝑛$ 重の積分布とし， $𝑛 \geq 1$ とする．真の分布が $𝑃$ と $𝑄$ から事前確率 $1 / 2$ ずつで選ばれるとし，系列 $𝑥 \in X 𝑛$ に対して $𝑃 𝑛 ({𝑥}) \geq 𝑄 𝑛 ({𝑥})$ ならば $𝑃$ を，そうでなければ $𝑄$ を答える決定を考える．この決定の Bayes 誤り確率 を

𝑃 (𝑛) 𝑒 : = 12 \sum 𝑥 \in X 𝑛 m i n (𝑃 𝑛 ({𝑥}), 𝑄 𝑛 ({𝑥}))

で定める．

右辺の各項は，その系列が出たときに払う誤りの確率である（添字の $𝑒$ は誤りを表す固定の文字で，本節の後半で置く中間分布 $𝑃 𝜆$ （定義 11.5.9）のように実数のパラメータを添えたものではない）． $𝑃$ と $𝑄$ が離れているほど，どの系列でも二つの確率の一方が他方より格段に小さくなり，小さいほうだけを足した和は小さくなる．逆に $𝑃 = 𝑄$ なら各項は $𝑃 𝑛 ({𝑥})$ そのもので，その総和は $1$ だから $𝑃 (𝑛) 𝑒 = 1 / 2$ である．すなわち，二つの仮説がまったく同じで見分けようがないときの誤り確率が，当てずっぽうと同じ $1 / 2$ になる．この決定がほかのどの決定よりも誤り確率が小さいことは本書では示さない．示すには決定の全体をわたって最小をとる形に問題を立て直す必要があり，本節が測るのは上の決定の誤り確率である．形式化にもその形の宣言は無い．

形式化: bayesErrorMinPmf (ソース)

実数の指数をもつべき乗

このあと置く量の式には，実数の指数をもつべき乗が現れる．底が $0$ になる場合まで含めて，先に定めておく．

定義 11.5.2（実数の指数をもつべき乗）. 正の実数 $𝑢$ と実数 $𝑠$ に対し

𝑢 𝑠 : = 𝑒 𝑠 l o g 𝑢

と定める（本章の底は自然対数なので， $𝑒$ のべき乗は指数関数そのものである）．また非負の実数 $𝑠$ に対し $0 𝑠$ を， $𝑠 > 0$ のとき $0$ ， $𝑠 = 0$ のとき $1$ と定める．負の $𝑠$ に対する $0 𝑠$ は定めない．

定め方から，正の $𝑢$ については $l o g (𝑢 𝑠) = 𝑠 l o g 𝑢$ である．また指数法則 $𝑒 𝑠 + 𝑠' = 𝑒 𝑠 𝑒 𝑠'$ から，正の $𝑢$ について $𝑢 𝑠 𝑢 𝑠' = 𝑢 𝑠 + 𝑠'$ と $(𝑢 𝑠) 𝑠' = 𝑢 𝑠 𝑠'$ が従う． $00 = 1$ と定めたのは， $𝑠 = 0$ のとき $𝑢 𝑠$ が正の $𝑢$ でつねに $1$ になるので，底を $0$ まで動かしてもその値を保つためである．

Chernoff の分配和

誤り確率の各項を上から抑えるところから始める． $m i n (𝑃 𝑛 ({𝑥}), 𝑄 𝑛 ({𝑥}))$ は，どの $𝜆 \in [0, 1]$ でも $𝑃 𝑛 ({𝑥}) 1 - 𝜆 𝑄 𝑛 ({𝑥}) 𝜆$ 以下である（補題 11.5.4）．この右辺は座標ごとの積だから， $𝑥 \in X 𝑛$ について足すと $1$ 文字ぶんの和の $𝑛$ 乗になる（補題 11.5.5）．つまり誤り確率の上界は， $1$ 文字ぶんの和ひとつで決まり，しかも $𝑛$ 乗の形で決まる．その $1$ 文字ぶんの和が次に定める $Z (𝜆)$ であり， $𝜆$ を上界がいちばん小さくなるように選んだときの指数が，本節の主役である Chernoff 情報になる．

定義 11.5.3（Chernoff の分配和と Chernoff 情報）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし，べき乗を定義 11.5.2 のとおりとする．実数 $𝜆$ に対し

Z (𝜆) : = \sum 𝑎 \in X 𝑃 (𝑎) 1 - 𝜆 𝑄 (𝑎) 𝜆

を Chernoff の分配和 と呼ぶ． $Z (𝜆)$ は正の数の有限和だから正であり， $l o g Z (𝜆)$ が定まる． $𝑃$ と $𝑄$ の Chernoff 情報 を

𝐶 * (𝑃, 𝑄) : = - i n f 0 \leq 𝜆 \leq 1 l o g Z (𝜆)

で定める．

$Z (𝜆)$ は，各文字で $𝑃$ と $𝑄$ の値を重み $1 - 𝜆$ と $𝜆$ で幾何的に混ぜ，足し合わせたものである． $𝜆$ を $0$ から $1$ へ動かすと重みは $𝑃$ の側から $𝑄$ の側へ移り， $𝜆$ を止めるごとに，混ぜた値を $Z (𝜆)$ で割って総和を $1$ にした分布が一つ定まる（花文字の $Z$ は，第10章定義 10.2.1 の分配関数 $𝑍$ とは別の記号である．分母という役割は同じで，違いは重みを付ける基準が一様分布ではなく $𝑃$ であることである）．その分布が定義 11.5.9 の中間分布であり，本節の後半で主役になる．本節の $𝜆$ は，こうして $𝑃$ と $𝑄$ を混ぜる度合いを表す実数である（第10章 10.4 節が Lagrange 乗数に使う $𝜆$ とも，補題 1.1.9 や第9章補題 9.3.1 が凸結合の重みに使う $𝜆$ とも別である．本章では凸結合の重みには $𝜃$ を当てる）．定義 11.5.3 の下限が実際に最小値として達成されること，したがって $𝐶 * (𝑃, 𝑄)$ が実数として定まることは命題 11.5.7 で示す（星が付く $𝐶 *$ は，第6章定義 6.1.4 の通信路容量 $𝐶 (𝑊)$ や第8章定義 8.2.1 のガウス通信路の容量とは別の量である）．

形式化: chernoffZSum，chernoffInfo (ソース)

二つの道具

補題 11.5.4（加重相加相乗平均と最小値の上界）. $𝑢 \geq 0$ ， $𝑣 \geq 0$ を実数， $𝜃 \in [0, 1]$ とし，べき乗を定義 11.5.2 のとおりとすると

𝑢 1 - 𝜃 𝑣 𝜃 \leq (1 - 𝜃) 𝑢 + 𝜃 𝑣

である．また $m i n (𝑢, 𝑣) \leq 𝑢 1 - 𝜃 𝑣 𝜃$ である．

証明. どちらの主張も $𝑢$ か $𝑣$ が $0$ の場合を先に片づける． $𝜃 = 0$ のときは左辺が $𝑢 1 𝑣 0 = 𝑢$ ，右辺が $𝑢$ で，第 $1$ の主張は等号として成り立ち， $m i n (𝑢, 𝑣) \leq 𝑢$ より第 $2$ の主張も成り立つ． $𝜃 = 1$ のときも同様である． $𝜃 \in (0, 1)$ で $𝑢 = 0$ または $𝑣 = 0$ のときは，定義 11.5.2 より $𝑢 1 - 𝜃 𝑣 𝜃 = 0$ であり，右辺は非負の数の和だから第 $1$ の主張が成り立ち， $m i n (𝑢, 𝑣) = 0$ だから第 $2$ の主張も成り立つ．

以下 $𝑢 > 0$ ， $𝑣 > 0$ とする．1.1 節で認めた $l o g$ の狭義凹性から出た有限 Jensen の不等式（補題 1.1.9）を， $2$ 点 $𝑢$ ， $𝑣$ と重み $1 - 𝜃$ ， $𝜃$ に当てると

(1 - 𝜃) l o g 𝑢 + 𝜃 l o g 𝑣 \leq l o g ((1 - 𝜃) 𝑢 + 𝜃 𝑣)

である．左辺は $l o g (𝑢 1 - 𝜃) + l o g (𝑣 𝜃) = l o g (𝑢 1 - 𝜃 𝑣 𝜃)$ に等しい．ここで，二つの正の数について対数の値が $\leq$ ならもとの数も $\leq$ である．というのも，もとの数が真に大きければ対数も真に大きいからである．これを当てて第 $1$ の主張を得る．

第 $2$ の主張に移る． $𝑢 \leq 𝑣$ の場合を見れば足りる． $𝑢$ と $𝑣$ を入れ替えて $𝜃$ を $1 - 𝜃$ に取り替えると主張の両辺が同じ形になるので， $𝑣 \leq 𝑢$ の場合はそこから出るからである． $𝑢 \leq 𝑣$ なら $l o g 𝑢 \leq l o g 𝑣$ であり， $𝜃 \geq 0$ を掛けて $(1 - 𝜃) l o g 𝑢$ を足すと

l o g 𝑢 = (1 - 𝜃) l o g 𝑢 + 𝜃 l o g 𝑢 \leq (1 - 𝜃) l o g 𝑢 + 𝜃 l o g 𝑣 = l o g (𝑢 1 - 𝜃 𝑣 𝜃)

となる．ふたたび対数の値の大小からもとの数の大小に移して $𝑢 \leq 𝑢 1 - 𝜃 𝑣 𝜃$ であり， $m i n (𝑢, 𝑣) = 𝑢$ だから主張を得る． $◻$

形式化上の注記. 補題 11.5.4 の第 $2$ の主張に対応する宣言は min_le_rpow_mul_rpow (InformationTheory/Shannon/Chernoff/Basic.lean) である．そちらは本文とは道筋が違い，最小値そのもののべき乗を経由して直接示している．第 $1$ の主張に対応する本プロジェクトの宣言は無い．Mathlib には $2$ 点版が Real.geom_mean_le_arith_mean2_weighted，有限個の項の版が Real.geom_mean_le_arith_mean_weighted としてあり，形式化は後者を別の箇所で使っている．

補題 11.5.5. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布， $𝑃 𝑛$ ， $𝑄 𝑛$ をそれぞれの $𝑛$ 重の積分布とし， $𝑛 \geq 1$ ， $𝜆 \in [0, 1]$ とする．べき乗を定義 11.5.2， $Z$ を定義 11.5.3 のとおりとすると

\sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) 1 - 𝜆 𝑄 𝑛 ({𝑥}) 𝜆 = Z (𝜆) 𝑛

である．

証明. 有限個の正の数の積のべき乗は，べき乗の積である（両辺の対数をとると，どちらも指数と各因子の対数の積の和になる）． $𝑃$ と $𝑄$ は全点で正だから $𝑃 𝑛 ({𝑥}) = \prod 𝑖 < 𝑛 𝑃 (𝑥 𝑖)$ の因子はどれも正で，この規則が使えて

𝑃 𝑛 ({𝑥}) 1 - 𝜆 𝑄 𝑛 ({𝑥}) 𝜆 = 𝑛 - 1 \prod 𝑖 = 0 𝑃 (𝑥 𝑖) 1 - 𝜆 𝑄 (𝑥 𝑖) 𝜆

である．これを $𝑥 \in X 𝑛$ について足す．分配法則を $𝑛$ 回使うと（ $𝑛$ についての帰納法），座標ごとに独立に和をとった形になり

\sum 𝑥 \in X 𝑛 𝑛 - 1 \prod 𝑖 = 0 𝑃 (𝑥 𝑖) 1 - 𝜆 𝑄 (𝑥 𝑖) 𝜆 = 𝑛 - 1 \prod 𝑖 = 0 \sum 𝑎 \in X 𝑃 (𝑎) 1 - 𝜆 𝑄 (𝑎) 𝜆 = Z (𝜆) 𝑛

を得る． $◻$

形式化: sum_prod_rpow_eq_Z_pow (ソース)

Chernoff 限界

定理 11.5.6（Chernoff 限界）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし， $𝑛 \geq 1$ ， $𝜆 \in [0, 1]$ とする． $𝑃 (𝑛) 𝑒$ を定義 11.5.1， $Z$ を定義 11.5.3 のとおりとすると

𝑃 (𝑛) 𝑒 \leq 12 Z (𝜆) 𝑛

である．

証明. 定義 11.5.1 の各項に補題 11.5.4 の第 $2$ の主張を， $𝑢 : = 𝑃 𝑛 ({𝑥})$ ， $𝑣 : = 𝑄 𝑛 ({𝑥})$ ，重みを $𝜃 : = 𝜆$ として当てると

m i n (𝑃 𝑛 ({𝑥}), 𝑄 𝑛 ({𝑥})) \leq 𝑃 𝑛 ({𝑥}) 1 - 𝜆 𝑄 𝑛 ({𝑥}) 𝜆

である． $𝑥 \in X 𝑛$ について足し，補題 11.5.5 を当てると右辺の和は $Z (𝜆) 𝑛$ になる．両辺に $1 / 2$ を掛ければ主張を得る． $◼$

形式化: bayesErrorMinPmf_le_half_Z_pow (ソース)

この不等式はどの $𝜆 \in [0, 1]$ でも成り立つから，いちばんよい $𝜆$ を選んでよい． $Z (𝜆) 𝑛 = 𝑒 𝑛 l o g Z (𝜆)$ だから，選ぶべきは $l o g Z (𝜆)$ を最小にする $𝜆$ であり，そのときの上界の指数が定義 11.5.3 の $𝐶 * (𝑃, 𝑄)$ である．その最小値が実際に達成されることを次に確かめる．そこで最大値定理を借りる．

Weierstrass の最大値定理を借りる. 借りるのは「有限次元の実ベクトル空間の空でない有界閉集合の上の実数値連続関数は最大値をとる」という形である．直接当てる相手は二つで，一つは閉区間 $[0, 1] \subseteq ℝ$ の上の実数値関数 $𝜆 \mapsto - l o g Z (𝜆)$ （命題 11.5.7），もう一つは，実ベクトル空間 $ℝ X$ の部分集合である確率単体の閉部分集合の上の実数値関数 $˜ 𝑃 \mapsto - 𝐷 (˜ 𝑃 ‖ 𝑄)$ （11.6 節の定理 11.6.2）である．第6章 6.1 節が通信路容量の達成（定理 6.1.5）のために，第9章 9.1 節がレート歪み関数の下限が最小値であること（命題 9.1.8）のために借りたのと同じ定理である．本書はこの最大値定理を証明しないが，形式化されていないわけではない．定理 11.6.2 の形式化は，Mathlib にある無条件の機械検証済みのこの定理をそのまま呼び出しているからである．

以下，微積分の計算規則（一次結合・積・商・合成・有限和が連続性と微分可能性を保つこと，和の法則・積の法則・商の法則・合成関数の微分の法則，本章の底のもとでの $(𝑒 𝑠)' = 𝑒 𝑠$ と $(l o g 𝑠)' = 1 / 𝑠$ ，微分係数が差分商の極限であり極限が広義の不等号を保つこと）は既知とする．

命題 11.5.7. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし， $Z$ ， $𝐶 *$ を定義 11.5.3 のとおりとする．このとき $Z (0) = Z (1) = 1$ である．また $𝜆 \mapsto l o g Z (𝜆)$ は $[0, 1]$ の上で連続かつ凸であり， $[0, 1]$ の上で最小値をとる．とくに定義 11.5.3 の下限は最小値として達成され， $𝐶 * (𝑃, 𝑄) \geq 0$ である．

証明. 両端の値から見る．定義 11.5.2 より $𝑄 (𝑎) 0 = 1$ ， $𝑃 (𝑎) 1 = 𝑃 (𝑎)$ だから $Z (0) = \sum 𝑎 𝑃 (𝑎) = 1$ であり，同じく $Z (1) = \sum 𝑎 𝑄 (𝑎) = 1$ である．

連続性を見る． $𝑃$ は全点で正だから，定義 11.5.2 と指数法則より

𝑃 (𝑎) 1 - 𝜆 𝑄 (𝑎) 𝜆 = 𝑃 (𝑎) e x p (𝜆 l o g 𝑄 (𝑎) 𝑃 (𝑎))

である．右辺は $𝜆$ の $1$ 次式に指数関数を合成したものに定数を掛けたもので， $Z$ はその有限和だから，微積分の計算規則より $Z$ は連続である． $Z (𝜆) > 0$ だから， $l o g$ との合成もふたたび連続である．

凸性に移る． $Z$ は上の書き換えのとおり指数関数の重み付き和だから， $l o g Z$ は第10章命題 10.4.2 が凸性を示した対数分配関数と同じ形をしている．ただし第10章の示し方（ $2$ 階導関数が分散に等しいので非負であること）に使う判定法を本節は借りていないので，以下は補題 11.5.4 の第 $1$ の主張を当てて， $2$ 点についての不等式として直接確かめる． $𝜆$ ， $𝜆'$ を $[0, 1]$ の数， $𝜃 \in [0, 1]$ とし，各文字 $𝑎$ について $𝑐 𝑎 : = 𝑃 (𝑎) 1 - 𝜆 𝑄 (𝑎) 𝜆$ ， $𝑑 𝑎 : = 𝑃 (𝑎) 1 - 𝜆' 𝑄 (𝑎) 𝜆'$ と置く．どちらも正で， $𝑎$ について足すと $\sum 𝑎 𝑐 𝑎 = Z (𝜆)$ ， $\sum 𝑎 𝑑 𝑎 = Z (𝜆')$ である．指数法則から

(𝑐 𝑎 Z (𝜆)) 1 - 𝜃 (𝑑 𝑎 Z (𝜆')) 𝜃 = 𝑃 (𝑎) 1 - ((1 - 𝜃) 𝜆 + 𝜃 𝜆') 𝑄 (𝑎) (1 - 𝜃) 𝜆 + 𝜃 𝜆' Z (𝜆) 1 - 𝜃 Z (𝜆') 𝜃

である．左辺に補題 11.5.4 の第 $1$ の主張を当て， $𝑎$ について足すと， $𝑐 𝑎 / Z (𝜆)$ の総和も $𝑑 𝑎 / Z (𝜆')$ の総和も $1$ だから

\sum 𝑎 (𝑐 𝑎 Z (𝜆)) 1 - 𝜃 (𝑑 𝑎 Z (𝜆')) 𝜃 \leq \sum 𝑎 ((1 - 𝜃) 𝑐 𝑎 Z (𝜆) + 𝜃 𝑑 𝑎 Z (𝜆')) = 1

である．右辺の式と見比べると，これは

Z ((1 - 𝜃) 𝜆 + 𝜃 𝜆') \leq Z (𝜆) 1 - 𝜃 Z (𝜆') 𝜃

と同じことである．両辺は正だから，対数をとって $l o g Z ((1 - 𝜃) 𝜆 + 𝜃 𝜆') \leq (1 - 𝜃) l o g Z (𝜆) + 𝜃 l o g Z (𝜆')$ を得る．これが凸性である．

最小値の存在に移る． $[0, 1]$ は $ℝ$ の空でない有界閉集合で， $- l o g Z$ はその上で連続だから，借りた Weierstrass の最大値定理より $- l o g Z$ は $[0, 1]$ で最大値をとる．すなわち $l o g Z$ は $[0, 1]$ で最小値をとり，定義 11.5.3 の下限はその最小値である．最後に，最小値は $l o g Z (0) = l o g 1 = 0$ 以下だから，符号を変えて $𝐶 * (𝑃, 𝑄) \geq 0$ である． $◼$

形式化上の注記. 命題 11.5.7 の内容は，形式化ではそれぞれ別の宣言になっている． $Z (0) = Z (1) = 1$ は chernoffZSum_lam_zero と chernoffZSum_lam_one，連続性は chernoffLogZ_continuous，凸性は convexOn_chernoffLogZ，最小値が達成されることは chernoffInfo_attained，非負性は chernoffInfo_nonneg（どれも InformationTheory/Shannon/Chernoff/Basic.lean）である．ただし連続性の宣言が述べるのは $ℝ$ 全体での連続性で，本文の $[0, 1]$ の上の連続性より広い．これらを一つにまとめた形の単独の宣言は無い．

系 11.5.8（Chernoff 限界の達成可能性）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし， $𝑃 (𝑛) 𝑒$ を定義 11.5.1， $𝐶 *$ を定義 11.5.3 のとおりとすると

l i m i n f 𝑛 \to \infty (- 1 𝑛 l o g 𝑃 (𝑛) 𝑒) \geq 𝐶 * (𝑃, 𝑄)

である．

証明. まず $𝑃 (𝑛) 𝑒 > 0$ を見る． $𝑃$ と $𝑄$ は全点で正だから，どの $𝑥 \in X 𝑛$ でも $𝑃 𝑛 ({𝑥})$ と $𝑄 𝑛 ({𝑥})$ は正で，その小さいほうも正である． $X 𝑛$ は空でないから，定義 11.5.1 の和は正の数の和で正である．

命題 11.5.7 より $l o g Z$ は $[0, 1]$ で最小値をとる．それを与える $𝜆$ を一つとると $l o g Z (𝜆) = - 𝐶 * (𝑃, 𝑄)$ であり，定理 11.5.6 より

𝑃 (𝑛) 𝑒 \leq 12 Z (𝜆) 𝑛 = 12 𝑒 - 𝑛 𝐶 * (𝑃, 𝑄)

である．両辺は正で，対数は単調だから，対数をとって $- 𝑛$ で割ると

- 1 𝑛 l o g 𝑃 (𝑛) 𝑒 \geq 𝐶 * (𝑃, 𝑄) + l o g 2 𝑛 \geq 𝐶 * (𝑃, 𝑄)

である．どの $𝑛 \geq 1$ でもこれが成り立つから，下極限も $𝐶 * (𝑃, 𝑄)$ 以上である． $◼$

形式化: chernoff_lemma_achievability (ソース)

指数が $𝐶 * (𝑃, 𝑄)$ に届くことは，これで分かった．残るのはそれを超えないことである．超えないことを示すには誤り確率を下から抑えなければならず，そのために $Z (𝜆)$ を分母にして作る分布を導入する．

中間分布

定義 11.5.9（Chernoff の中間分布）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし，べき乗を定義 11.5.2， $Z$ を定義 11.5.3 のとおりとする．実数 $𝜆$ に対し

𝑃 𝜆 (𝑎) : = 𝑃 (𝑎) 1 - 𝜆 𝑄 (𝑎) 𝜆 Z (𝜆) (𝑎 \in X)

で定まる $X$ 上の関数を Chernoff の中間分布 と呼ぶ．分子は正で， $𝑎$ について足したものが分母 $Z (𝜆)$ だから， $𝑃 𝜆$ は $X$ 上の全点で正の分布である．

形式化: chernoffMediator，chernoffMediator_pos，chernoffMediator_sum_eq_one (ソース)

両端の値を見ておく． $𝜆$ を $0$ から $1$ へ動かすと $𝑃 𝜆$ が $𝑃$ から $𝑄$ へ移る，というのが次の命題である．

命題 11.5.10. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし， $𝑃 𝜆$ を定義 11.5.9 のとおりとすると $𝑃 0 = 𝑃$ かつ $𝑃 1 = 𝑄$ である．

証明. 命題 11.5.7 より $Z (0) = Z (1) = 1$ である．定義 11.5.2 より，どの文字でも $𝑃 (𝑎) 1 - 0 𝑄 (𝑎) 0 = 𝑃 (𝑎)$ だから，定義 11.5.9 より $𝑃 0 (𝑎) = 𝑃 (𝑎) / Z (0) = 𝑃 (𝑎)$ である．同じく $𝑃 (𝑎) 1 - 1 𝑄 (𝑎) 1 = 𝑄 (𝑎)$ だから $𝑃 1 (𝑎) = 𝑄 (𝑎) / Z (1) = 𝑄 (𝑎)$ である． $◼$

形式化: chernoffMediator_lam_zero，chernoffMediator_lam_one (ソース)

移り方は各点での値を幾何的に混ぜるもので，二つの分布を線分で結ぶ混ぜ方とは別である．定義 11.5.2 と指数法則から $𝑃 (𝑎) 1 - 𝜆 𝑄 (𝑎) 𝜆 = 𝑃 (𝑎) e x p (𝜆 l o g 𝑄 (𝑎) 𝑃 (𝑎))$ である．すなわち $𝑃 𝜆$ は， $𝑃$ の各点の値に指数の重みを掛けて総和が $1$ になるように割ったものであり，この作り方は大偏差論で指数傾斜と呼ばれる．

この中間分布が，次の命題で Chernoff 情報に意味を与える．

命題 11.5.11. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし， $Z$ ， $𝐶 *$ を定義 11.5.3， $𝑃 𝜆$ を定義 11.5.9 のとおりとする．このとき $𝜆 \mapsto l o g Z (𝜆)$ は $ℝ$ の上で微分可能で，どの実数 $𝜆$ でもその導関数は

𝑑 𝑑 𝜆 l o g Z (𝜆) = \sum 𝑎 \in X 𝑃 𝜆 (𝑎) l o g 𝑄 (𝑎) 𝑃 (𝑎)

である．さらに， $l o g Z$ の $[0, 1]$ 上の最小値を与える $𝜆 *$ が開区間 $(0, 1)$ に属するならば，この和は $𝜆 = 𝜆 *$ で $0$ になり

𝐶 * (𝑃, 𝑄) = 𝐷 (𝑃 𝜆 * ∥ 𝑃) = 𝐷 (𝑃 𝜆 * ∥ 𝑄)

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

証明. $𝑃$ は全点で正だから，定義 11.5.2 と指数法則より $𝑃 (𝑎) 1 - 𝜆 𝑄 (𝑎) 𝜆 = 𝑃 (𝑎) e x p (𝜆 l o g 𝑄 (𝑎) 𝑃 (𝑎))$ である． $𝑄 (𝑎) / 𝑃 (𝑎)$ は正だから $l o g 𝑄 (𝑎) 𝑃 (𝑎)$ は $𝜆$ に依らない有限な数である．微積分の計算規則より， $1$ 次式と指数関数の合成は微分可能で， $𝜆$ についての導関数は同じ関数に $l o g 𝑄 (𝑎) 𝑃 (𝑎)$ を掛けたものである．有限和も微分可能だから

Z' (𝜆) = \sum 𝑎 𝑃 (𝑎) e x p (𝜆 l o g 𝑄 (𝑎) 𝑃 (𝑎)) l o g 𝑄 (𝑎) 𝑃 (𝑎)

である． $Z (𝜆) > 0$ だから，合成関数の微分の法則と $(l o g 𝑠)' = 1 / 𝑠$ より $l o g Z$ も微分可能で，その導関数は $Z' (𝜆) / Z (𝜆)$ である．各項を $Z (𝜆)$ で割ると定義 11.5.9 の $𝑃 𝜆 (𝑎)$ になるから，導関数は主張の和に等しい．

後半に移る． $𝜆 * \in (0, 1)$ が $[0, 1]$ 上の最小値を与えるとし， $l o g Z$ の導関数を $𝜆 *$ で評価する． $0 < 𝑟 < 1 - 𝜆 *$ を満たす実数 $𝑟$ をとると $𝜆 * + 𝑟 \in [0, 1]$ だから $l o g Z (𝜆 * + 𝑟) \geq l o g Z (𝜆 *)$ であり，差分商 $(l o g Z (𝜆 * + 𝑟) - l o g Z (𝜆 *)) / 𝑟$ は非負である． $𝑟$ を $0$ に近づけると，微積分の計算規則より差分商の極限は $𝜆 *$ での微分係数であり，極限は広義の不等号を保つから，微分係数は非負である．同じことを $- 𝜆 * < 𝑟 < 0$ で行うと，分子は非負で分母が負だから差分商は非正であり，微分係数は非正である．よって微分係数は $0$ ，すなわち前半の和は $𝜆 *$ で $0$ になる．

最後に二つの相対エントロピーを計算する．定義 11.5.9 と指数法則から

𝑃 𝜆 (𝑎) 𝑃 (𝑎) = 1 Z (𝜆) e x p (𝜆 l o g 𝑄 (𝑎) 𝑃 (𝑎)), 𝑃 𝜆 (𝑎) 𝑄 (𝑎) = 1 Z (𝜆) e x p (- (1 - 𝜆) l o g 𝑄 (𝑎) 𝑃 (𝑎))

である．対数をとって $𝑃 𝜆 (𝑎)$ を掛け， $𝑎$ について足すと，1.6 節の相対エントロピーの定義と $𝑃 𝜆$ の総和が $1$ であることから

𝐷 (𝑃 𝜆 ∥ 𝑃) = 𝜆 \sum 𝑎 𝑃 𝜆 (𝑎) l o g 𝑄 (𝑎) 𝑃 (𝑎) - l o g Z (𝜆), 𝐷 (𝑃 𝜆 ∥ 𝑄) = - (1 - 𝜆) \sum 𝑎 𝑃 𝜆 (𝑎) l o g 𝑄 (𝑎) 𝑃 (𝑎) - l o g Z (𝜆)

である． $𝜆 = 𝜆 *$ では和が $0$ だから，どちらも $- l o g Z (𝜆 *)$ に等しい． $𝜆 *$ は最小値を与えるので，定義 11.5.3 より $- l o g Z (𝜆 *) = 𝐶 * (𝑃, 𝑄)$ である． $◼$

形式化上の注記. 導関数の式は chernoffLogZ_hasDerivAt，最小値を与える $𝜆 *$ で和が $0$ になることは chernoffMediator_balance， $𝐶 * (𝑃, 𝑄)$ が中間分布から $𝑃$ への相対エントロピーに等しいことは chernoffInfo_eq_mediator_div（どれも InformationTheory/Shannon/Chernoff/Converse.lean）である．ただし三つの主張を束ねた単独の宣言は無く， $𝐶 * (𝑃, 𝑄) = 𝐷 (𝑃 𝜆 * ‖ 𝑄)$ のほうに対応する宣言も無い．

等式 $𝐶 * (𝑃, 𝑄) = 𝐷 (𝑃 𝜆 * ‖ 𝑃) = 𝐷 (𝑃 𝜆 * ‖ 𝑄)$ は，Chernoff 情報の読み方を与える． $𝜆$ を $0$ から $1$ へ動かすと中間分布は $𝑃$ から $𝑄$ へ移る（命題 11.5.10）から，両端では二つの隔たりの一方が $0$ になる． $𝜆 = 0$ では $𝑃$ からの隔たりが $0$ で $𝑄$ からの隔たりが $𝐷 (𝑃 ‖ 𝑄)$ ， $𝜆 = 1$ では $𝑄$ からの隔たりが $0$ で $𝑃$ からの隔たりが $𝐷 (𝑄 ‖ 𝑃)$ である．中間分布のうち $𝑃$ からの隔たりと $𝑄$ からの隔たりが等しくなる点がとれるとき，その共通の値が Chernoff 情報である．二つの分布のちょうど中ほどまでの距離だ，と読みたくなるが，相対エントロピーは距離ではない（1.6 節）ので，そう読むのは言い過ぎである．言えるのは，二つの隔たりが釣り合う点での値だということである．

この等式が使えるのは，最小値を与える $𝜆 *$ が端点でないときだった．その条件は， $𝑃$ と $𝑄$ が違う分布でありさえすれば満たされる．

命題 11.5.12. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし， $Z$ を定義 11.5.3 のとおりとする． $𝑃 \neq 𝑄$ ならば， $l o g Z$ の $[0, 1]$ 上の最小値を与える実数 $𝜆$ はすべて開区間 $(0, 1)$ に属する．

証明. まず両端での微分係数の符号を見る．命題 11.5.11 の導関数の式に命題 11.5.10 を当てると， $𝑃 0 = 𝑃$ だから $𝜆 = 0$ での微分係数は $\sum 𝑎 𝑃 (𝑎) l o g 𝑄 (𝑎) 𝑃 (𝑎) = - 𝐷 (𝑃 ‖ 𝑄)$ であり， $𝑃 1 = 𝑄$ だから $𝜆 = 1$ での微分係数は $\sum 𝑎 𝑄 (𝑎) l o g 𝑄 (𝑎) 𝑃 (𝑎) = 𝐷 (𝑄 ‖ 𝑃)$ である（ $𝐷$ は 1.6 節の相対エントロピー）． $𝑃 \neq 𝑄$ だから定理 1.6.1 よりどちらの相対エントロピーも正で， $𝜆 = 0$ での微分係数は負， $𝜆 = 1$ での微分係数は正である．

最小値を与える $𝜆$ が $0$ だったとする． $0 < 𝑟 \leq 1$ について $l o g Z (𝑟) \geq l o g Z (0)$ だから差分商 $(l o g Z (𝑟) - l o g Z (0)) / 𝑟$ は非負であり， $𝑟$ を $0$ に近づけると，微積分の計算規則より極限は $𝜆 = 0$ での微分係数だから，それが非負となって上に反する．最小値を与える $𝜆$ が $1$ だったときも同じで， $- 1 \leq 𝑟 < 0$ について差分商 $(l o g Z (1 + 𝑟) - l o g Z (1)) / 𝑟$ をとると，分子は非負で分母は負だから差分商は非正であり， $𝜆 = 1$ での微分係数が非正となって，やはり上に反する．よって最小値を与える $𝜆$ は $(0, 1)$ に属する． $◼$

形式化上の注記. 命題 11.5.12 に対応する宣言は無い．形式化は，最小値を与える $𝜆$ が開区間 $(0, 1)$ に属することを仮定として受け取る形をとっており，それが $𝑃 \neq 𝑄$ から出ることは述べていない．

逆

定理 11.5.13（Chernoff 限界の逆）. $X$ を空でない有限アルファベット， $𝑃$ ， $𝑄$ を $X$ 上の全点で正の分布とし， $𝑃 (𝑛) 𝑒$ を定義 11.5.1， $Z$ ， $𝐶 *$ を定義 11.5.3， $𝑃 𝜆$ を定義 11.5.9 のとおりとする． $l o g Z$ の $[0, 1]$ 上の最小値を与える $𝜆 *$ が開区間 $(0, 1)$ に属するならば

l i m s u p 𝑛 \to \infty (- 1 𝑛 l o g 𝑃 (𝑛) 𝑒) \leq 𝐶 * (𝑃, 𝑄)

である．

証明. $˜ 𝑃 : = 𝑃 𝜆 *$ と置く．定義 11.5.9 より $˜ 𝑃$ は $X$ 上の全点で正の分布であり，命題 11.5.11 より $𝐷 (˜ 𝑃 ‖ 𝑃) = 𝐷 (˜ 𝑃 ‖ 𝑄) = 𝐶 * (𝑃, 𝑄)$ である．

$˜ 𝑃$ に近い型を作る． $X$ は空でないから文字 $𝑎 0$ を一つ選び， $˜ 𝑃 𝑛$ を $𝑎 0$ を端数の引き受け手とする $˜ 𝑃$ の丸め型（定義 11.3.4）とする．補題 11.3.5 より，どの $𝑛 \geq 1$ でも $˜ 𝑃 𝑛$ は長さ $𝑛$ の型であり，どの文字でも $˜ 𝑃 𝑛 (𝑎) \to ˜ 𝑃 (𝑎)$ である．

型類の中の確率で誤り確率を下から抑える．命題 11.1.4 より， $T 𝑛 (˜ 𝑃 𝑛)$ のどの点でも $𝑃 𝑛 ({𝑥})$ は同じ値をとり， $𝑄 𝑛 ({𝑥})$ も同じ値をとる．したがってその小さいほうも $𝑥$ に依らず， $T 𝑛 (˜ 𝑃 𝑛)$ にわたる和は要素数にその値を掛けたものである．要素数は非負だから，これは $𝑃 𝑛 (T 𝑛 (˜ 𝑃 𝑛))$ と $𝑄 𝑛 (T 𝑛 (˜ 𝑃 𝑛))$ の小さいほうに等しい．定義 11.5.1 の和のほかの項は非負だから

𝑃 (𝑛) 𝑒 \geq 12 m i n (𝑃 𝑛 (T 𝑛 (˜ 𝑃 𝑛)), 𝑄 𝑛 (T 𝑛 (˜ 𝑃 𝑛)))

である．右辺は正だから，対数をとって $- 1 / 𝑛$ を掛けると，不等号の向きが変わって

- 1 𝑛 l o g 𝑃 (𝑛) 𝑒 \leq l o g 2 𝑛 + m a x (- 1 𝑛 l o g 𝑃 𝑛 (T 𝑛 (˜ 𝑃 𝑛)), - 1 𝑛 l o g 𝑄 𝑛 (T 𝑛 (˜ 𝑃 𝑛)))

である（最小値の対数の符号を変えると，符号を変えた二つの対数の最大値になる）．

$˜ 𝑃 𝑛$ は長さ $𝑛$ の型で各文字で $˜ 𝑃$ に収束するから，系 11.2.3 を，参照する分布として $𝑃$ をとって当てると $1 𝑛 l o g 𝑃 𝑛 (T 𝑛 (˜ 𝑃 𝑛)) \to - 𝐷 (˜ 𝑃 ‖ 𝑃)$ であり， $𝑄$ をとって当てると $1 𝑛 l o g 𝑄 𝑛 (T 𝑛 (˜ 𝑃 𝑛)) \to - 𝐷 (˜ 𝑃 ‖ 𝑄)$ である．二つの極限はどちらも $𝐶 * (𝑃, 𝑄)$ に等しい．よってどの $𝜀 > 0$ についても，十分大きい $𝑛$ では右辺の最大値の中の二つがともに $𝐶 * (𝑃, 𝑄) + 𝜀$ 未満であり， $l o g 2 𝑛$ も $𝜀$ 未満である．したがって上極限は $𝐶 * (𝑃, 𝑄) + 2 𝜀$ 以下であり， $𝜀 > 0$ は任意だから $𝐶 * (𝑃, 𝑄)$ 以下である． $◼$

形式化: chernoff_converse (ソース)

系 11.5.8 と定理 11.5.13 を合わせると，最小値を与える $𝜆 *$ が内点にとれるときには $- 1 𝑛 l o g 𝑃 (𝑛) 𝑒$ が $𝐶 * (𝑃, 𝑄)$ に収束する．命題 11.5.12 より， $𝑃 \neq 𝑄$ でありさえすればこの条件は満たされる．次の例では，具体的な分布について最小値を与える $𝜆$ がただ一つであることまで確かめ，収束先の値を数で求める．

数値で見る

例 11.5.14（二値の Chernoff 情報）. $X = {0, 1}$ とし， $𝑃$ を $𝑃 (0) = 0.1$ ， $𝑃 (1) = 0.9$ ， $𝑄$ を $𝑄 (0) = 𝑄 (1) = 1 / 2$ で定まる分布とする． $𝑃 (𝑛) 𝑒$ を定義 11.5.1， $Z$ ， $𝐶 *$ を定義 11.5.3， $𝑃 𝜆$ を定義 11.5.9 のとおりとすると，次の四つが成り立つ．

どの実数 $𝜆$ についても $Z (𝜆) = 2 - 𝜆 (0.1 1 - 𝜆 + 0.9 1 - 𝜆)$ である．
$l o g Z$ の $[0, 1]$ 上の最小値を与える $𝜆$ はただ一つで，開区間 $(0, 1)$ に属する．それを $𝜆 *$ と書くと， $𝑃 𝜆 * (0)$ の値は約 $0.2675$ ， $𝜆 *$ の値は約 $0.5416$ である．
$𝐶 * (𝑃, 𝑄)$ の値は約 $0.1124$ ナットである．いっぽう $𝐷 (𝑃 ‖ 𝑄)$ の値は約 $0.3681$ ナット， $𝐷 (𝑄 ‖ 𝑃)$ の値は約 $0.5108$ ナットで， $𝐶 * (𝑃, 𝑄)$ はどちらよりも小さい（ $𝐷$ は 1.6 節の相対エントロピー）．
$- 1 𝑛 l o g 𝑃 (𝑛) 𝑒 ⟶ 𝐶 * (𝑃, 𝑄)$ （ $𝑛 \to \infty$ ）である．

証明.

$𝑄 (𝑎) = 1 / 2$ はどちらの文字でも同じだから $𝑄 (𝑎) 𝜆 = 𝑒 - 𝜆 l o g 2 = 2 - 𝜆$ であり，これを定義 11.5.3 の和からくくり出せばよい．
命題 11.5.7 より $l o g Z$ は $[0, 1]$ で最小値をとる．それを与える $𝜆$ を一つとる． $𝑃 \neq 𝑄$ だから命題 11.5.12 よりこの $𝜆$ は $(0, 1)$ に属し，命題 11.5.11 よりそこで微分係数は $0$ である．その微分係数を書き下す． $l o g 𝑄 (0) 𝑃 (0) = l o g 5$ ， $l o g 𝑄 (1) 𝑃 (1) = l o g 59$ だから，命題 11.5.11 の導関数の式より， $𝜆$ での微分係数は $𝑃 𝜆 (0) l o g 5 + 𝑃 𝜆 (1) l o g 59$ である． $𝑃 𝜆 (1) = 1 - 𝑃 𝜆 (0)$ と $l o g 59 = l o g 5 - l o g 9$ を使うと，これは

l o g 59 + 𝑃 𝜆 (0) l o g 9

に等しい．

微分係数が $𝜆$ について狭義単調増加であることを見る．上の式と $l o g 9 > 0$ より， $𝑃 𝜆 (0)$ が狭義単調増加であることを見れば足りる． $𝑄 (0) = 𝑄 (1)$ より

𝑃 𝜆 (1) 𝑃 𝜆 (0) = 𝑃 (1) 1 - 𝜆 𝑄 (1) 𝜆 𝑃 (0) 1 - 𝜆 𝑄 (0) 𝜆 = 9 1 - 𝜆 = 𝑒 (1 - 𝜆) l o g 9

であり， $𝑃 𝜆 (0) + 𝑃 𝜆 (1) = 1$ だから $𝑃 𝜆 (0) = 1 / (1 + 9 1 - 𝜆)$ である．指数関数は狭義単調増加だから（ $l o g$ が狭義単調増加であることと $l o g 𝑒 𝑠 = 𝑠$ から出る）， $9 1 - 𝜆$ は $𝜆$ について狭義単調減少で，正の数の逆数をとると向きが変わるから $𝑃 𝜆 (0)$ は狭義単調増加である．よって微分係数も狭義単調増加で，それが $0$ になる $𝜆$ は高々一つである．最小値を与える $𝜆$ はすべて $(0, 1)$ に属して微分係数を $0$ にするのだから，そのような $𝜆$ はただ一つであり，これを $𝜆 *$ と書く．

数値に移る．微分係数が $𝜆 *$ で $0$ になることは，上の式より $𝑃 𝜆 * (0) l o g 9 = l o g 9 - l o g 5$ と同じだから

𝑃 𝜆 * (0) = l o g 9 - l o g 5 l o g 9 = 2.19722 \dots - 1.60943 \dots 2.19722 \dots = 0.26751 \dots

である．また $𝑃 𝜆 * (0) = 1 / (1 + 9 1 - 𝜆 *)$ を $𝜆 *$ について解くと $9 1 - 𝜆 * = 0.73248 \dots / 0.26751 \dots = 2.73813 \dots$ であり，対数をとって $1 - 𝜆 * = 1.00727 \dots / 2.19722 \dots = 0.45843 \dots$ ，すなわち $𝜆 * = 0.54156 \dots$ である．

命題 11.5.11 より $𝐶 * (𝑃, 𝑄) = 𝐷 (𝑃 𝜆 * ‖ 𝑄)$ であり，補題 11.2.5 より，これは $l o g 2 - 𝐻 𝑏 (𝑃 𝜆 * (0))$ に等しい（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）．第 $2$ の主張の値を入れると $𝐻 𝑏 (0.26751 \dots) = 0.58077 \dots$ ， $l o g 2 = 0.69314 \dots$ だから $𝐶 * (𝑃, 𝑄) = 0.11237 \dots$ である．次に補題 11.2.5 より $𝐷 (𝑃 ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (0.1) = 0.69314 \dots - 0.32508 \dots = 0.36806 \dots$ である．いっぽう 1.6 節の定義から

𝐷 (𝑄 ‖ 𝑃) = 12 l o g 0.5 0.1 + 12 l o g 0.5 0.9 = 12 (l o g 5 + l o g 59) = 12 (1.60943 \dots - 0.58778 \dots) = 0.51082 \dots

である． $0.11237 \dots$ はどちらよりも小さい．

$𝑃$ と $𝑄$ はどちらも全点で正だから系 11.5.8 より下極限は $𝐶 * (𝑃, 𝑄)$ 以上であり，第 $2$ の主張より $𝜆 *$ は $(0, 1)$ に属するから定理 11.5.13 より上極限は $𝐶 * (𝑃, 𝑄)$ 以下である．よってこの数列は収束し，極限は $𝐶 * (𝑃, 𝑄)$ である．

$◼$

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

この $𝑃$ は例 11.2.6 と同じ偏ったコインである．例 11.5.14 の数を並べると，Bayes 誤り確率の指数 $0.1124$ は，第二種の誤りの指数を下から押さえた値 $𝐷 (𝑃 ‖ 𝑄) = 0.3681$ （系 11.4.7）より小さい．この例では，二つの誤りを同時に小さくすることを求めると，片方だけを見たときの速さは出ないということである．二つの立て方の間には，第一種の誤りにも指数を課すという中間の立て方がある．次節はそれを扱う．そこで現れる関数は，第一種の誤りに課す指数が $0$ のとき $𝐷 (𝑃 ‖ 𝑄)$ をとり（命題 11.6.7），例 11.6.10 では $𝐶 * (𝑃, 𝑄)$ もその関数の値として現れる．

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