ベルヌーイ測度・マルコフ測度のエントロピー

ベルヌーイシフトの測度論的エントロピー $h_{μ} = - \sum_{i} p_{i} lo g p_{i}$ と、定常分布 $π$ をもつマルコフ測度のエントロピー $h_{μ} = - \sum_{i, j} π_{i} P_{ij} lo g P_{ij}$ を求められる（例: $P = (\frac{1}{2} 1 \frac{1}{2} 0)$ で $π = (\frac{2}{3}, \frac{1}{3})$ , $h_{μ} = \frac{2}{3} lo g 2$ ）

前提

エントロピー（大学数学情報理論・符号理論）
定常分布（大学数学確率・統計）

この技能までの道筋（28 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
エントロピー（大学数学情報理論・符号理論）
条件付き確率と乗法定理（数学A 場合の数と確率）
等間隔にならんだ数の和（算数計算と数のきまり）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
マルコフ連鎖と推移確率（大学数学確率・統計）
定常分布（大学数学確率・統計）

説明

有限個の記号 ${1, \dots, k}$ を並べた両側（または片側）無限列の空間にシフト写像 $σ$ を考え、そこに独立同分布の測度（ベルヌーイ測度）や、定常なマルコフ連鎖から決まる測度（マルコフ測度）を入れたとき、その力学系の測度論的エントロピー $h_{μ} (σ)$ を具体的な数として計算できるようになります。測度論的エントロピーは「1 ステップあたり平均して何だけ新しい不確かさが生まれるか」を表す量で、二つの力学系が同型でないことを示したり、記号列の情報量を比べたりする場面で使います。この技能では対数は自然対数 $lo g$ を使います（底 2 にすると値が $lo g 2$ で割った値になるだけです）。

なぜそうしてよいのか

シフトのエントロピーは、最初の $n$ 個の記号 $X_{0}, X_{1}, \dots, X_{n - 1}$ の組のエントロピーを $n$ で割った極限 $h_{μ} = lim_{n \to \infty} \frac{1}{n} H (X_{0}, \dots, X_{n - 1})$ として求まります（第 0 座標の値で空間を分ける分割は生成分割なので、コルモゴロフ–シナイの定理によりこの極限が $h_{μ} (σ)$ に一致します。ここではこの事実を認めて使います）。ここで $H (X_{0}, \dots, X_{n - 1})$ は、長さ $n$ の語 $w = x_{0} \dots x_{n - 1}$ が現れる確率 $μ [w]$ について $- \sum_{w} μ [w] lo g μ [w]$ で、言い換えると確率変数 $- lo g μ [X_{0} \dots X_{n - 1}]$ の期待値です。

ベルヌーイ測度では各記号が独立に確率 $p_{i}$ で現れるので $μ [x_{0} \dots x_{n - 1}] = p_{x_{0}} p_{x_{1}} \dots p_{x_{n - 1}}$ です。対数をとると積が和になり、 $- lo g μ [X_{0} \dots X_{n - 1}] = \sum_{k = 0}^{n - 1} (- lo g p_{X_{k}})$ 。期待値の線形性から各項の期待値は $- \sum_{i} p_{i} lo g p_{i}$ なので、 $H (X_{0}, \dots, X_{n - 1}) = n (- \sum_{i} p_{i} lo g p_{i})$ 、 $n$ で割って $h_{μ} = - \sum_{i} p_{i} lo g p_{i}$ となります。

マルコフ測度では、推移確率行列 $P$ と $π P = π$ をみたす定常分布 $π$ を使って $μ [x_{0} \dots x_{n - 1}] = π_{x_{0}} P_{x_{0} x_{1}} P_{x_{1} x_{2}} \dots P_{x_{n - 2} x_{n - 1}}$ と定めます（ $π$ が定常だからこの測度はシフトで不変です）。同じく対数をとると $- lo g μ [\dots] = - lo g π_{X_{0}} + \sum_{k = 0}^{n - 2} (- lo g P_{X_{k} X_{k + 1}})$ 。定常性より $(X_{k}, X_{k + 1}) = (i, j)$ となる確率はどの $k$ でも $π_{i} P_{ij}$ なので、各項の期待値は $- \sum_{i, j} π_{i} P_{ij} lo g P_{ij}$ です。よって $H (X_{0}, \dots, X_{n - 1}) = H (π) + (n - 1) (- \sum_{i, j} π_{i} P_{ij} lo g P_{ij})$ となり、 $n$ で割って $n \to \infty$ とすると最初の $H (π)$ の寄与は消え、 $h_{μ} = - \sum_{i, j} π_{i} P_{ij} lo g P_{ij}$ が残ります。直観的には「今いる状態 $i$ から次の状態を選ぶときの不確かさ $- \sum_{j} P_{ij} lo g P_{ij}$ を、状態 $i$ にいる割合 $π_{i}$ で平均したもの」です。 $P$ のすべての行が同じ $(p_{1}, \dots, p_{k})$ ならベルヌーイの場合に戻ります。

手順

測度の種類を確認する。各記号が独立に確率 $p_{i}$ で出るならベルヌーイ測度、推移確率行列 $P$ で決まるならマルコフ測度である
ベルヌーイ測度なら $h_{μ} = - \sum_{i} p_{i} lo g p_{i}$ を計算して終わり（ $p_{i} = 0$ の項は $0 lo g 0 = 0$ として除く）
マルコフ測度なら、 $π P = π$ , $\sum_{i} π_{i} = 1$ を解いて定常分布 $π$ を求める
各行 $i$ について、その行の分布のエントロピー $H_{i} = - \sum_{j} P_{ij} lo g P_{ij}$ を計算する（ $P_{ij} = 0$ の項は 0）
$π$ で重み付けして足し合わせる: $h_{μ} = \sum_{i} π_{i} H_{i} = - \sum_{i, j} π_{i} P_{ij} lo g P_{ij}$ 。対数の性質で整理する

例題

記号 ${1, 2}$ 上のシフトに、推移確率行列 $P = (\frac{1}{2} \frac{1}{4} \frac{1}{2} \frac{3}{4})$ と、その定常分布から定まるマルコフ測度 $μ$ を考える。測度論的エントロピー $h_{μ} (σ)$ を求めよ。ただし $lo g$ は自然対数とする。

例題の解答

【手順 1】推移確率行列で与えられているのでマルコフ測度である。

【手順 3】定常分布 $π = (π_{1}, π_{2})$ を求める。 $π P = π$ の第 1 成分は $\frac{1}{2} π_{1} + \frac{1}{4} π_{2} = π_{1}$ より $\frac{1}{4} π_{2} = \frac{1}{2} π_{1}$ 、すなわち $π_{2} = 2 π_{1}$ 。 $π_{1} + π_{2} = 1$ と合わせて $π = (\frac{1}{3}, \frac{2}{3})$ 。

【手順 4】各行のエントロピーを計算する。
第 1 行: $H_{1} = - \frac{1}{2} lo g \frac{1}{2} - \frac{1}{2} lo g \frac{1}{2} = lo g 2$ 。
第 2 行: $H_{2} = - \frac{1}{4} lo g \frac{1}{4} - \frac{3}{4} lo g \frac{3}{4} = \frac{1}{4} \cdot 2 lo g 2 + \frac{3}{4} (2 lo g 2 - lo g 3) = 2 lo g 2 - \frac{3}{4} lo g 3$ 。

【手順 5】 $π$ で重み付けして足す。
$h_{μ} = \frac{1}{3} lo g 2 + \frac{2}{3} (2 lo g 2 - \frac{3}{4} lo g 3) = \frac{1}{3} lo g 2 + \frac{4}{3} lo g 2 - \frac{1}{2} lo g 3 = \frac{5}{3} lo g 2 - \frac{1}{2} lo g 3.$
（数値では約 $0.606$ 。2 状態での最大値 $lo g 2 \approx 0.693$ より小さく、妥当である。）

答え: $\frac{5}{3} lo g 2 - \frac{1}{2} lo g 3$

よくある誤り

定常分布で重み付けせず、各行のエントロピーを単純平均してしまう誤り。上の例で $\frac{1}{2} (H_{1} + H_{2})$ とするのは誤りで、正しくは $h_{μ} = π_{1} H_{1} + π_{2} H_{2} = \frac{1}{3} H_{1} + \frac{2}{3} H_{2}$ 。
マルコフ測度のエントロピーを定常分布そのもののエントロピー $- \sum_{i} π_{i} lo g π_{i}$ としてしまう誤り。これは 1 記号の分布の不確かさで、1 ステップごとに生まれる不確かさではない。正しくは $- \sum_{i, j} π_{i} P_{ij} lo g P_{ij}$ （例: $P = (0110)$ では $π = (\frac{1}{2}, \frac{1}{2})$ で $H (π) = lo g 2$ だが、列は交互に決まるので $h_{μ} = 0$ ）。
$lo g$ の中を $π_{i} P_{ij}$ にしてしまう誤り。 $- \sum_{i, j} π_{i} P_{ij} lo g (π_{i} P_{ij})$ は 2 文字の組 $(X_{0}, X_{1})$ のエントロピーで、 $H (π)$ だけ多い。正しくは重みが $π_{i} P_{ij}$ 、対数の中は $P_{ij}$ だけ。
底を取り違える誤り。前提で使った $lo g_{2}$ のまま計算して自然対数の答えと混同しないこと。 $- \sum p_{i} lo g_{2} p_{i}$ で得た値に $lo g 2$ を掛けたものが自然対数での値になる（例: 公平なコインのベルヌーイシフトは底 2 で $1$ 、自然対数で $lo g 2$ ）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
記号の集合 ${0, 1, 2}$ 上の片側シフト $σ : {0, 1, 2}^{N} \to {0, 1, 2}^{N}$ , $(σ x)_{n} = x_{n + 1}$ を考える。各座標が独立に、確率 $p_{0} = \frac{1}{2}$ , $p_{1} = \frac{1}{4}$ , $p_{2} = \frac{1}{4}$ で記号 $0, 1, 2$ をとるベルヌーイ測度を $μ$ とする。 $σ$ の $μ$ に関する測度論的エントロピー $h_{μ} (σ)$ を求めよ。ただし $lo g$ は自然対数とする。

この技能を使う問題

この技能の次に学べること

誘導写像とカッツの補題・アブラモフの公式（大学院数学力学系・エルゴード理論）