確率分布を木で表し、選択の継起を継ぎ木で表す
【 確率分布を木で表し、選択の継起を継ぎ木で表す 】
確率分布を木で表し、選択の継起を継ぎ木で表すという、シャノンのエントロピーが満たすべき「第三の条件」の解釈は、新しく継ぎ木する木の確率分布の全体に元木の枝の確率を重みとして掛けることで、新らしい木の表す確率分布を計算することを可能にします。
このアプローチは、見かけは簡単なのですが、強力なものです。例えば、このアプローチをつかって、前回のセッションの最後に述べた「チャレンジ」の答えを出しておきましょう。A(mn)=A(m)+A(n)A(mn)=A(m)+A(n) を示せという問題です。
次のように考えます。
A(m)とA(n)の確率分布を表す木を考えます。A(m)の木は m個の枝を持ち、それぞれの枝は全て等しく1m の確率を表しています。A(n)の木は n個の枝を持ち、それぞれの枝は全て等しく 1nの確率を表しています。
このA(m)の木の全ての枝に A(n)の木を継ぎ木します。こうしてできた新しい木は、m×n=mn 個の枝を持ち、根から枝の端までの枝は、1m×1n=1mn の確率を表しています。要するに、継ぎ木でできた新しい木は、A(mn)の確率分布を表しています。
この新しい木に、シャノンのエントロピーが満たすべき「第三の条件」を使うと、次の式が成り立つことがわかります。
A(mn)=A(m)+1m×A(n)+1m×A(n)+⋯+1m×A(n)=A(m)+A(n)
この式で、m=n とすると、A(n2)=2A(n) がわかり、A(n3)=3A(n), ... , A(nm)=mA(n) がわかります。 このことは、前回示した、A(nm)=mA(n) よりこの式 A(mn)=A(m)+A(n) の方が、基本的なものだということを示しています。
log(xy)=log(x)+log(y) ですので、関数等式 A(xy)=A(x)+A(y) を満たす関数Aの「候補の一つ」が、A(x)=Klog(x) であることは明らかです。確かに、x,y が実数で、関数Aが微分可能だと仮定すれば、それは簡単に証明できます。(Wikipedia がしたように)
ただ、自然数 n について実数値をとる関数A(n) が、関数等式 A(mn)=A(m)+A(n) を満たす時、そうしたA(n)は、ある正の定数 K が存在して A(n)=Klog(n) である場合に限るということを証明することは、少し難しいのです。A(n)が微分可能だと要求するのは強すぎるのですが、A(n)についてもう少し条件が必要です。
関数 A(n) が、次の条件を満たす時、こうした証明が可能であることを初めて示したのは、エルデシュです。( Leinster "Entropy and Diversity"の「定理 1.2.1」)
A(1)≤A(2)≤A(3)≤…
シャノンが、エルデシュの証明を知っていたかどうかはわかりません。ただ、シャノンがエントロピーが満たすべき条件の二番目に挙げたのは、まさにこの条件でした。
このセッションでは、「第三の条件」から導かれる関数等式 A(sm)=mA(s) (これは、関数等式 A(mn)=A(m)+A(n) から派生したものです)と、「第二の条件」l≤m≤n なら、A(l)≤A(m)≤A(n) から、 A(n)=Klog(n)を導いたシャノンの証明を紹介します。
ショートムービー:
https://youtu.be/ZnbovJc7CnY?list=PLQIrJ0f9gMcO_b7tZmh80ZE1T4QqAqL-A
ショートムービーのpdf:
https://drive.google.com/file/d/1RVLMht4Bun6qy0wTwAuabZT3f0Up4GwD/view?usp=sharing
5/28 マルゼミ「エントロピー論の現在」のまとめページを作りました。ほぼ毎日更新されると思います。ご利用ください。https://www.marulabo.net/docs/info-entropy5/
5/28 マルゼミの申し込みページも作成しました。
https://entropy-theory.peatix.com/
お申し込みお待ちしています。
コメント
コメントを投稿