NO.1654 平均は強力だった 2007.2.11 DDT
最近平均について、面白い講義を受けました。バーコフの個別エルゴード定理に関することです。
でもその前に、ポアンカレの再帰定理の話があります。
１．測度と可測集合に関する注意
以下の話では、測度と可測集合という言葉を度々使いますが、自分は測度論の初歩というか、
誰でもが知っている事しか知れません。よって以下で、測度，可測集合と言い出したら、
次のようなものを指していると、割り引いて読んで下さい。
測度の定義
集合Ｘ上の測度Ｐとは、Ｘから実数Ｒへの写像Ｐ：Ｘ→Ｒで、次の条件を満たすもの。
(1) Ｐ(φ)＝0。ここでφは空集合．
(2) ＡとＢ⊂Ｘで、Ａ∩Ｂ＝φなら、Ｐ(Ａ∪Ｂ)＝Ｐ(Ａ)＋Ｐ(Ｂ)．
(3) Ｐ(Ｘ)＜∞．
可測集合
Ｘ上の測度Ｐに関する可測集合全体Βとは、Ａ⊂Ｘとして、
(1) Ａ＝φである．
(2) Ａ≠φなら、Ｐ(Ａ)≠0である．
を満たすＡ⊂Ｘの全体Βのこと。特に、(2)を満たすＡ⊂Ｘが一つでも存在すれば、Ｘは可測集合になります。
以上のような、アマチュアの範囲です。
２．力学におけるポアンカレの再帰定理
次の定理は、アーノルドの「古典力学の数学的方法」に載っているものなので、本当です。
古典力学におけるポアンカレの再帰定理
Ｘを質点系の配位空間とし（n個の質点なら、Ｒ3nの部分集合）で、Ｘ⊂Ｒ3nは有界とする。
このとき、Ｘの任意の点の任意の近傍Ｕについて、有限時間の内にＵに戻ってくる、x∈Ｕが存在する。
[証明]
古典力学を問題にしているので、x∈Ｘの時間発展は運動方程式に従う（微分方程式に支配される）。
ただし1秒後のxの位置をＴ(x)と表した場合、k秒後の位置はＴk(x)で表す。1.5秒後とかも同様とする。
Ａ⊂Ｘの時間発展を考えた場合、Ａの時間発展は微分方程式に従うので、微分方程式の一般論から、
Ｔ：Ｘ→Ｘは単射である。よって、
Ａ＝Ｔ-1(Ｔ(Ａ)) (a)
が成り立つ。またＴが運動方程式の流れを表すという事から、
Ｖ(Ａ)＝Ｖ(Ｔ(Ａ)) (b)
も成り立つ。ここでＶは、領域ＡやＴ(Ａ)の体積（測度）です。この結果はリュービルの定理と言われます。「古典力学の数学的方法」の中で実際に証明されています。
ＵをＸの任意の点の任意の近傍とした場合、Ｘ⊂Ｒ3nなので、Ｖ(Ｕ)＞0です。Ｕについて、次の無限列を考えます：
Ｕ，Ｔ(Ｕ)，Ｔ2(Ｕ)，Ｔ3(Ｕ)，･･･
しかも、任意のi，j∈Ｎについて、
Ｔi(Ｕ)∩Ｔj(Ｕ)＝φ
と仮定します。１．の測度の定義(2)と、この証明の式(b)より、
Ｖ(Ｕ∪Ｔ(Ｕ)∪Ｔ2(Ｕ)∪Ｔ3(Ｕ)∪･･･)
＝Ｖ(Ｕ)＋Ｖ(Ｕ)＋Ｖ(Ｕ)＋Ｖ(Ｕ)＋･･･ (c)
です。ところがＸ⊂Ｒ3nは有界なので、Ｖ(Ｘ)＜∞より、式(c)は、いつかはＶ(Ｘ)＜∞を越えます。
従って、あるk，l∈Ｎ（k≧l）があり、
Ｔk(Ｕ)∩Ｔl(Ｕ)≠φ
となる必要があります（１．の測度の定義(2)から）。よって式(a)より、
Ｔk-l(Ｕ)∩Ｕ≠φ
が得られます。ここで、
x∈Ｔk-l(Ｕ)∩Ｕ⊂Ｕ
とすれば、
Ｔk-l(Ｕ)∈Ｕ
は明らかです。即ち(k−l)秒後に、x∈Ｕは、Ｕに戻ります。
[証明終]
３．複雑系におけるポアンカレの再帰定理
じつは受けた講義は「カオス・フラクタルを目指して」という趣旨だったのですが、
その準備として、ポアンカレの再帰定理を紹介されました。本当の事を言うと、
この部分は聞いていなかったのですが、後で期末レポートを出題されて、
ポアンカレの再帰定理を焼き直せる事に気づきました。まず、セッティングは以下となります。
セッティング：
Ｘ： 状態空間（何らかの集合）。Ｘの点は可測な近傍の基本系を持つとする．
Β： Ｘの可測集合全体．
Ｔ： Ｘ上の可測変換で、点x∈Ｘの時間発展を表し、Ｔは微分方程式に支配されるとする．
従ってＴは、微分方程式の流れを表すので、単射．
Ｐ： Ｔに関する不変測度で、Ｐ(Ｘ)＜∞．
ポアンカレの再帰定理
Ａ∈Β，Ｐ(Ａ)＞0（Ａ≠φ）とする。Ａにある密集合Ｄがあり、任意のx∈Ｄについて、
xの軌道{Ｔnx}は、無限回Ａに戻る。
補題1．
任意のＡ⊂Ｘについて、Ａ＝Ｔ-1(Ｔ(Ａ))とＰ(Ａ)＝Ｐ(Ｔ(Ａ))が成り立つ。
［証明］
Ｔが単射だから。［証明終］
補題2．
Ｘの任意の点の任意の近傍Ｕに関して、Ｕには、その軌道が十分長い時間の内に再びＵに戻ってくる、
点x∈Ｕが存在する。ただしＸの点は、可測な近傍の基本系を持つので、Ｐ(Ｕ)＞0である。
［証明］
力学における再帰定理の証明と同じ［証明終］
補題3．
補第2の点x全体Ｄ'は、Ｘで密。
［証明］
補題2が、Ｘの任意の点の任意の近傍で言えるから。［証明終］
ポアンカレの再帰定理の証明．
Ａ∈Β，Ｐ(Ａ)＞0（Ａ≠φ）とする。Ａにある密集合Ｄがあり、任意のx∈Ｄについて、
xの軌道{Ｔnx}は、無限回Ａに戻る。
［証明］
Ａ⊂Ｘは明らか。ＡにＸからの導入位相を定義すれば、密集合の推移性より、
補題2のＤ'はＡでも密。それをＤ＝Ａ∩Ｄ'とすれば良い。
無限回戻るのは、補題2（古典力学の再帰定理）のＴk-l(x)を出発点として、何回でも繰り返せるから。［証明終］
４．ポアンカレの再帰定理を解釈すると
アーノルドの「古典力学の数学的方法」に載っていた再帰定理では、Ｔは運動方程式の流れを表し、
リュービルの定理から、ルベーグ測度ＰがＴ不変となっています。
このときＰは体積を表し、Ｔは体積不変な写像です。当然全空間Ｘは有限体積を持ち、
Ｘの有界性が本質にあります。しかし焼き直しによれば、Ｘ上の測度Ｐが有界性を持てば、
Ｘに有界性を要求しなくても再帰定理が成り立ちます（大筋では正しいと思います）。
x∈Ｘの軌道が無限の彼方に飛び去れば永遠に帰ってこない事を考えると、
これは、測度Ｐの有界性と可測性（任意のＡ∈ΒでＰ(Ａ)＞0）が、
結果としてＸに有界性を課すように思えます。もちろん再帰時間と、
その時点までに観測されたＸの拡がりが、時間とともにじりじり拡大する事は考えられますが。
ここで測度Ｐを観測と考え、また観測には確率も含まれるとすれば、以上の事は普通の言葉で言えば、
「一度でも見れたものは、何回でも見れる。何回でも起こる可能性がある」
（Ａ∈ΒでＰ(Ａ)＞0） （Ｐ(Ａ)＝Ｐ(Ｔ(Ａ)だから)
となるように思えます。一度でも見れた（Ａ∈ΒでＰ(Ａ)＞0）とは、Ｘの有界性の現われです。
ここで問題になるのが、ＰがＴ不変である事です。例えばＸを人間の社会や歴史とした場合、
Ｘの定常性は危ういので、Ｐの不変性は？です。しかし私はもともと土木出身ですが、
土木では大雨の再現確率を問題にして、河川計画などを行います。今まで再現確率は、
たんなる観測上の統計値にすぎないと思っていたのですが、じつはこんなところに成立根拠が潜んでいたのかも
しれないと考え直しました。
自然は人間よりもずっと定常性があるので、案外再帰定理が成り立つ格好のモデルになるような気はします。
ところで余談ですが、少なくとも気象に関しては、定常性が危うくなっているかもしれません。
理由は、もちろん理由は温暖化です。とはいえ、例えば宇宙論の最先端分野なんかを考えると、
自然はやっぱり定常的なのかもしれず、一般化された再帰定理は有効な気がします。
再帰定理について、もっと卑近な例を考えます。定常性ということで、
「三つ子の魂百までも」はどうでしょう？。Ｐを「三つ子の行動の再現確率」とした場合、
再帰定理はけっこう成り立ってる気がします。
５．エルゴード定理
これは証明できません。証明すると唱っていた講義の回も聞き逃しました。
でも、次のような定性論は間違いでしょうか？
これも定常性が成り立つという条件下と思いますが、
バーコフのエルゴード定理は、空間平均は時間平均に等しいです。次のような例を考えます。
私は現在プログラマーをやっています。プログラムには、非常に豊かに開発者の個性が現れます。
ところがプログラムにはBugがつきものです。Bugとは（間違い方とは）、
開発者の個性の発露でもあります。結果としてBugは、プログラマーの残業時間の最大の原因になります。
さらに残業は経験上、酒量の最大原因の一つです。
そこでＲ3に、点(Bugの発生回数，残業時間，酒量)を毎日プロットし、
「ddtの状態空間」をつくります。プロットを1年続ければ、「ddtの生活軌道」を描けます。
空間平均が時間平均に等しければ、この1年間の生活軌道の平均点のまわりで、
ddtは、向こう百年間うろうろしていることになります。何故ならddtには、
「三つ子の魂百までも」の定常性が成り立っているから、です。
「平均点のまわりでうろうろする」とは、再帰定理に見えます。もちろん平均は積分量なので、
全空間一様に生活軌道が拡がっていても平均は出るので、平均に再帰しやすいとは厳密には言えません。
しかし平均のまわりに正規分布するが、通説です。これを信じれば、定常性があれば、
軌道は平均に再帰しやすく、ある一瞬の観測結果をもって、
平均量については遥か未来まで見通せることになります。
このように考えると、初等的な統計量である平均という考えが、
通常思われているより、ずっと強力な道具なんだと気づかされます。
NO.1651 部分集合の個数(2) 2007.2.5 夜ふかしのつらいおじさん
問題１
具体的に書き出して個数を数えます。
f(8,1)=8
( {1},{2},{3},{4},{5},{6},{7},{8} )
f(8,2)=21
( {1,3},{1,4},{1,5},{1,6},{1,7},{1,8},
{2,4},{2,5},{2,6},{2,7},{2,8},
{3,5},{3,6},{3,7},{3,8},
{4,6},{4,7},{4,8},
{5,7},{5,8},
{6,8} )
f(8,3)=20
( {1,3,5},{1,3,6},{1,3,7},{1,3,8},
{1,4,6},{1,4,7},{1,4,8},
{1,5,7},{1,5,8},
{1,6,8},
{2,4,6},{2,4,7},{2,4,8},
{2,5,7},{2,5,8},
{2,6,8},
{3,5,7},{3,5,8},
{3,6,8},
{4,6,8} )
f(8,4)=5
( {1,3,5,7},{1,3,5,8},
{1,3,6,8},
{1,4,6,8}
{2,4,6,8} )
問題２
1つおきに数を取っていくときがsの最大になります。
f(n,s) において
nが偶数のとき、1≦s≦n/2
nが奇数のとき、1≦s≦(n+1)/2
問題３
f(n,s)を具体的に数えて計算します。
F(1)=f(1,0)+f(1,1)=1+1=2
F(2)=f(2,0)+f(2,1)=1+2=3
F(3)=f(3,0)+f(3,1)+f(3,2)=1+3+1=5
F(4)=f(4,0)+f(4,1)+f(4,2)=1+4+3=8
F(5)=f(5,0)+f(5,1)+f(5,2)+f(5,3)=1+5+6+1=13
F(6)=f(6,0)+f(6,1)+f(6,2)+f(6,3)=1+6+10+4=21
F(7)=f(7,0)+f(7,1)+f(7,2)+f(7,3)+f(7,4)=1+7+15+10+1=34
F(8)=f(8,0)+f(8,1)+f(8,2)+f(8,3)+f(8,4)=1+8+21+20+5=55
この結果はパスカルの三角形のなかで次のような値を意味します。
F(n)=f(n,0)+f(n,1)+f(n,2)+･･･+f(n,s-1)+f(n,s)
=n-(0-1)Ｃ0+n-(1-1)Ｃ1
+n-(2-1)Ｃ2+･･･+n-(s-1-1)Ｃs-1+n-(s-1)Ｃs
ここでＦ(n)の各項は、
f(n,s)=n-(s-1)Ｃs= 
これについて例をあげて説明します。
例えば、f(8,3)=20を次のように考えます。
| 1 | {1,3,5} → oxoxoxxxX
|
|---|
| 2 | {1,3,6} → oxoxxoxxX
|
|---|
| 3 | {1,3,7} → oxoxxxoxX
|
|---|
| 4 | {1,3,8} → oxoxxxxoX
|
|---|
| 5 | {1,4,6} → oxxoxoxxX
|
|---|
| 6 | {1,4,7} → oxxoxxoxX
|
|---|
| 7 | {1,4,8} → oxxoxxxoX
|
|---|
| 8 | {1,5,7} → oxxxoxoxX
|
|---|
| 9 | {1,5,8} → oxxxoxxoX
|
|---|
| 10 | {1,6,8} → oxxxxoxoX
|
|---|
| 11 | {2,4,6} → xoxoxoxxX
|
|---|
| 12 | {2,4,7} → xoxoxxoxX
|
|---|
| 13 | {2,4,8} → xoxoxxxoX
|
|---|
| 14 | {2,5,7} → xoxxoxoxX
|
|---|
| 15 | {2,5,8} → xoxxoxxoX
|
|---|
| 16 | {2,6,8} → xoxxxoxoX
|
|---|
| 17 | {3,5,7} → xxoxoxoxX
|
|---|
| 18 | {3,5,8} → xxoxoxxoX
|
|---|
| 19 | {3,6,8} → xxoxxoxoX
|
|---|
| 20 | {4,6,8} → xxxoxoxoX
|
|---|
矢印の右のoxの並びは左から数えた数字の位置をo、それ以外をxにしたものです。
これは、数字が連続しないので{ox}と{x}の順列と同じです。
最後をX(大文字)にしているのは、oとxの合計の個数がnより1つ多いことを意味しています。
{ox}：3個、{x}：(8-2×3+1)=8-(2×3-1)個の合計3+8-(2×3-1)=8-(3-1)個の同じものを含む順列なので
f(8,3)={8-(3-1)}！/[3！×{8-(2×3-1)}！]=
8-(3-1)Ｃ
3
問題４
f(n,s)=n-(s-1)Ｃs
問題５
nが奇数のとき(n=2s-1)
| F(n)+F(n+1) | =f(n,0)+f(n,1)+f(n,2)+･･･+f(n,s-1)+f(n,s)
|
| =f(n+1,0)+f(n+1,1)+f(n+1,2)+･･･+f(n+1,s-1)+f(n+1,s)
|
| =n-(0-1)Ｃ0+n-(1-1)Ｃ1+n-(2-1)Ｃ2+･･･+n-(s-1-1)Ｃs-1+n-(s-1)Ｃs
|
| +n+1-(0-1)Ｃ0+n+1-(1-1)Ｃ1+n+1-(2-1)Ｃ2+･･･+n+1-(s-1-1)Ｃs-1+n+1-(s-1)Ｃs
|
| = n+1Ｃ0+nＣ1
+･･･+n-s+2Ｃs-1+n-s+1Ｃs （あ）
|
| +n+2Ｃ0+n+1Ｃ1+nＣ2
+･･･+n-s+2Ｃs (同じ色のものを縦にまとめる）
|
| =n+2Ｃ0+n+2Ｃ1+n+1Ｃ2
+･･･+n-s+3Ｃs+n-s+2Ｃs+1（い）
|
| =n+3Ｃ0+n+2Ｃ1+n+1Ｃ2
+･･･+n-s+3Ｃs+n-s+2Ｃs+1
|
※ まとめるのは、nＣr-1+nＣr=n+1Ｃr
※ 最初の項は、組み合わせで取る個数が0なので左の添え字を変えても問題ない。
※ 最後の項について、（あ）の最後の式はsＣs （い）の最後の式はs+1Ｃs+1となり値は等しい。
| F(n)+F(n+1) | =f(n+2,0)+f(n+2,1)+f(n+2,2)+･･･+f(n+2,s)+f(n+2,s+1)
|
| =F(n+2)
|
nが偶数のとき(n=2s)
| F(n)+F(n+1) | =f(n,0)+f(n,1)+f(n,2)+･･･+f(n,s)
|
| =f(n+1,0)+f(n+1,1)+f(n+1,2)+･･･+f(n+1,s+1)
|
| F(n)+F(n+1) | =n-(0-1)Ｃ0+n-(1-1)Ｃ1+n-(2-1)Ｃ2+･･･+n-(s-1-1)Ｃs-1+n-(s-1)Ｃs
|
| +n+1-(0-1)Ｃ0+n+1-(1-1)Ｃ1+n+1-(2-1)Ｃ2+･･･+n+1-(s-1)Ｃs+n+1-(s+1-1)Ｃs+1
|
| = n+1Ｃ0+nＣ1
+･･･+n-s+1Ｃs
|
| +n+2Ｃ0+n+1Ｃ1+nＣ2
+･･･+n-s+1Ｃs+1 (同じ色のものを縦にまとめる）
|
| =n+3Ｃ0+n+2Ｃ1+n+1Ｃ2
+･･･+n-s+2Ｃs+1
|
| =f(n+2,0)+f(n+2,1)+f(n+2,2)+･･･+f(n+2,s+1)
|
| =F(n+2)
|
F(n)+F(n+1)=F(n+2)となりフィボナッチ数列になります。
t2=t+1とすると
t=(1±√5)/2なので
a=(1−√5)/2、b=(1−√5)/2とすると、まず
F(n+1)-bF(n)=a{F(n)-bF(n-1)}とおくと
F(n+1)-bF(n)は初項F(2)-bF(1)、公比aの等比数列なので
F(n+1)-bF(n)={F(2)-bF(1)}×an-1 ･･･ (1)
次に
F(n+1)-aF(n)=b{F(n)-aF(n-2)}とおくと
F(n+1)-aF(n)は初項F(2)-aF(1)、公比bの等比数列なので
F(n+1)-aF(n)={F(2)-aF(1)}×bn-1 ･･･ (2)
(1)-(2)より
(a-b)F(n)={F(2)-bF(1)}×an-1-{F(2)-aF(1)}×bn-1
これを整理すると
（０＜ｘ＜ｙ） ・・・式．２
・・・式．３
・・・式．４
（証明は後述）であるから、
関数ｆ(ｘ)のグラフの概形を描くと、fig.1のようになる。
が成立している。
（証明終わり）
を証明する。
（ｎ＞１）とおく。
だから、二項定理により、
・・・式．５
となり、 
が成り立つ。
を考えると、
が成り立ち、 
となる。
が成り立つ。
が明らかですが、極限値が求められません。