■格子上の確率論(その5)
横浜国大・今野紀雄先生より頂いた資料:
Peter Griffin(1990): Accelerating beyond the third dimension: Returning to the origin in simple random walk, Math. Scientist 15, 24-35
の数表をみると,小生が計算した再帰確率
d=3,n=200 → p3=0.32
d=3,n=500 → p3=0.33
d=4,n=100 → p4=0.19
とすべて一致し,私にとっては大満足の結果となりました.また,その文献からd次元格子上における酔歩の再帰確率pdを引用すると,
d pd d pd
1 1 13 .041919
2 1 14 .038657
3 .340537 15 .035869
4 .193201 16 .033458
5 .135178 17 .031352
6 .104715 18 .029496
7 .085844 19 .027848
8 .072912 20 .026375
9 .063447 30 .017257
10 .056197 40 .012827
11 .050455 100 .005050
12 .045789
再帰確率はdが大きいほど小さくなりますが,dが十分に大きいとき,第1種0次の変形ベッセル関数を使って,
Σu2n=∫(0,∞)exp(-x){I0(x/d)}^ddx
〜 1+2!/2(2d)+3!/2(2d)^2+4!/2(2d)^3+5!/2(2d)^4+5*71/2(2d)^5+・・・
より,
pd 〜 1/(2d){1+1/d+7/(4d^2)+35/(8d^3)+215/(16d^4)}
で漸近近似されることがその論文には記されています.
この式では,最初の数項の近似値でも
p1=1,p2=1,p3=0.34,p4=0.20,p5=0.13,p6=0.10
ですから,かなり正確な値がでています.
また,
1/2(d−1)=1/(2d){1+1/d+1/(d^2)+・・・}
ですから,式
pd 〜 1/2(d−1)
は簡単な割には漸近確率をよく近似し,
pd 〜 1/(2d−1) あるいは pd 〜 1/(2d)
よりも外挿した際の誤差が小さいことが理解されます.
===================================
【1】原点からの拡散距離が√nの領域内に納まる確率
ところで,d次元格子上の酔歩の挙動は,ブラウン運動などの拡散モデルとしてよく知られていますが,格子のモデルはブラウン運動の離散化とみなすことができるので,局所的にみると離散的過程であっても,大域的にみると連続空間に分布した連続的なd次元ガウス分布とみることができます.
したがって,d次元酔歩が原点(0,0,,・・・,0)を中心として拡散し,原点からの距離がσ=√nの領域内に納まる確率は,自由度dのχ^2分布で近似されることがわかります.このことは,多重ガウス積分が不完全ガンマ関数になることから計算されるのですが,この詳細についてはコラム「n次元楕円の陰と影」を参照願います.
実は,人間の直観や勘は1変量からたかだか3変量までの寡変量の世界ではよく働きますが、多変量の世界ではあまり働かないのが普通であって、われわれが3次元空間でイメージするものとは大きく異なってきます.そのため,高次元では予期せざる現象がしばしば起こるのですが,以下にその例をみてみましょう.
1次元正規分布ならば,区間
[μ−1σ,μ+1σ]に68.3%,
[μ−2σ,μ+2σ]に95.4%,
[μ−3σ,μ+3σ]に99.7%
の観測値が入ります.ほとんどの観測値が[μ−3σ,μ+3σ]に入ることを利用して,工場では品質管理を行っていますが,それが3σ法であって,有用なQCテクノロジーの1つになっています.
一方,d次元正規分布は,
p(x1,x2,x3,・・・,xd)=1/(2πσ^2)^(d/2)exp{-(x1^2+x^2+・・・+xd^2)/2σ^2}
で与えられますが,多次元正規分布の場合,低次元の場合とは対照的に密度の裾にあたる領域に大部分のデータが存在することになります.
すなわち,高次元になるほど原点の近傍にある確率は小さくなるのですが,そのこととd次元酔歩の再帰確率との間に何らかの関係が成り立つように思われます.もちろん,原点の近傍に存在する確率が少なくなるほど再帰確率が小さくなることが直観されますが,そこでまずd次元酔歩の原点からの拡散距離がσ,2σ,3σまでに含まれる確率を計算してみることにしましょう.
===================================
χ^2分布は不完全ガンマ関数と密接に関係していて,その分布関数は,超幾何関数を使って
F(x)=(x/2)^(d/2)1F1(d/2,1+d/2,-x/2)/Γ(1+d/2)
=(x/2)^(d/2)exp(-x/2)1F1(1,1+d/2,x/2)/Γ(1+d/2)
のように表現されます.
以下に確率計算に使用したプログラムと計算結果を掲げますが,たとえば,2次元酔歩の場合,自由度2のχ^2分布は指数分布ですから,全体のp%がその内側に入るような超球の半径cは
(c/σ)^2=−2ln(1−p)
によって与えられます.
c=σのときp=0.394,
c=2σのときp=0.865
となり,半径が2σの円を描くとその内側には86.5%が含まれることになります.
これらは1次元酔歩の場合の確率,
c=σのときのp=0.683,
c=2σのときのp=0.954
より小さくなるのですが,さらに,それぞれ1辺が2σ,4σの正方形の内側に入る確率,
p=(0.683)^2=0.466>0.394
p=(0.954)^2=0.910>0.865
よりも小さくなることが容易におわかり頂けるでしょう.
===================================
1000 DEFDBL A-H,J-Z
1010 FOR I=1 TO 20
1020 DF=I
1030 PRINT:PRINT DF
1040 C=1:UUX=C*C:GOSUB *CHI2.PROB.HGF:PRINT P0
1050 C=2:UUX=C*C:GOSUB *CHI2.PROB.HGF:PRINT P0
1060 C=3:UUX=C*C:GOSUB *CHI2.PROB.HGF:PRINT P0
1070 '
1080 Z=(1+DF)/2:GOSUB *LOG.GAMMA:G1#=G#
1090 Z=DF/2 :GOSUB *LOG.GAMMA:G2#=G#
1100 C=EXP(G1#-G2#)*SQR(2):UUX=C*C:GOSUB *CHI2.PROB.HGF:PRINT P0
1110 NEXT I
1120 END
1130 '
1140 ' ** CHI-SQUARE DISTRIBUTION **
1150 '
1160 *CHI2.PROB.HGF:
1170 A0=1:C0=1+DF/2
1180 A=A0:C=C0
1190 Z=UUX/2:GOSUB *CONFLUENT.HGF :G1#=G#:' [polynomial expansion]
1200 'Z=UUX/2:GOSUB *CONFLUENT.HGF1:G1#=G#:' [ continued fraction ]
1210 Z=1+DF/2:GOSUB *LOG.GAMMA:G2#=G#
1220 Z=UUX/2
1230 'P0=G1#/EXP(G2#)*Z^(DF/2)*EXP(-UUX/2)
1240 P0=LOG(G1#)-G2#+DF/2*LOG(Z)-UUX/2
1250 P0=EXP(P0)
1260 RETURN
1270 '
1280 ' *** 合流型超幾何関数 ***
1290 '
1300 *CONFLUENT.HGF:' [Kummer]
1310 EPSL=1E-09
1320 G0#=0:G#=1
1330 T#=1:K=1
1340 WHILE ABS(G0#-G#)>EPSL
1350 T#=T#*A/C*Z/K
1360 G0#=G#
1370 G#=G#+T#
1380 K=K+1
1390 A=A+1
1400 C=C+1
1410 WEND
1420 G=G#
1430 RETURN
1440 '
1450 ' *** ガウス型超幾何関数 ***
1460 '
1470 *GAUSS.HGF:
1480 EPSL=1E-09
1490 G0#=0:G#=1
1500 T#=1:K=1
1510 WHILE ABS(G0#-G#)>EPSL
1520 T#=T#*A*B/C*Z/K
1530 G0#=G#
1540 G#=G#+T#
1550 K=K+1
1560 A=A+1
1570 B=B+1
1580 C=C+1
1590 WEND
1600 G=G#
1610 RETURN
1620 '
1630 ' *** 合流型超幾何関数の連分数展開 ***
1640 '
1650 *CONFLUENT.HGF1:' 1F1(1,c,x)
1660 NZ=20
1670 G#=0
1680 'FOR ID=NZ TO 1 STEP -1
1690 ID=NZ
1700 WHILE ID>=1
1710 EVEN#=ID/(C+2*ID-1)/(C+2*ID-2)
1720 ODD#=-(C+ID-1)/(C+2*ID)/(C+2*ID-1)
1730 G#=ODD#*Z/(1#+G#)
1740 G#=EVEN#*Z/(1#+G#)
1750 ID=ID-1
1760 WEND
1770 'NEXT ID
1780 G#=-Z/C/(1#+G#)
1790 G#=1#/(1#+G#)
1800 RETURN
1810 '
1820 ' *** ガウス型超幾何関数の連分数展開 ***
1830 '
1840 *GAUSS.HGF1:' 2F1(a,1,c,x)
1850 NZ=20
1860 G#=0
1870 'FOR ID=NZ TO 1 STEP -1
1880 ID=NZ
1890 WHILE ID>=1
1900 ODD#=-(A+ID-1)*(C+ID-2)/(C+2*ID-2)/(C+2*ID-3)
1910 EVEN#=-ID*(C-A+ID-1)/(C+2*ID-1)/(C+2*ID-2)
1920 G#=EVEN#*Z/(1#+G#)
1930 G#=ODD#*Z/(1#+G#)
1940 ID=ID-1
1950 WEND
1960 'NEXT ID
1970 G#=1#/(1#+G#)
1980 RETURN
1990 '
2000 ' *** 対数ガンマ関数 (HASTINGSの多項式近似) ***
2010 '
2020 *LOG.GAMMA:
2030 A1#=-.577191652#
2040 A2#= .988205891#
2050 A3#=-.897056937#
2060 A4#= .918206857#
2070 A5#=-.756704078#
2080 A6#= .482199394#
2090 A7#=-.193527818#
2100 A8#= .035868343#
2110 X=Z:G#=0
2120 IF X<1 THEN G#=-LOG(X):GOTO 2150
2130 WHILE X>2:X=X-1:G#=G#+LOG(X):WEND
2140 X=X-1
2150 G#=G#+LOG(1+X*(A1#+X*(A2#+X*(A3#+X*(A4#+X*(A5#+X*(A6#+X*(A7#+X*A8#))))))))
2160 L.GAMMA=G#
2170 G=G#
2180 RETURN
===================================
d σ 2σ 3σ
1 .682689 .954499 .997300
2 .393469 .864664 .988891
3 .198748 .738535 .970709
4 .090204 .593994 .938900
5 .037434 .450584 .890935
6 .014387 .323323 .826421
7 5.171463E-3 .220222 .747343
8 1.751622E-3 .142876 .655770
9 5.624972E-4 .088587 .562725
10 1.721156E-4 .052653 .467896
11 5.038994E-5 .030082 .378107
12 1.416493E-5 .016563 .297069
13 3.834734E-6 .008808 .227056
14 1.002379E-6 4.533805E-3 .168949
15 2.535644E-7 2.262655E-3 .122482
16 6.219690E-8 1.096718E-3 .086586
17 1.481974E-8 5.170670E-4 .059738
18 3.435490E-9 2.374473E-4 .040257
19 7.759389E-10 1.063403E-4 .026520
20 1.709670E-10 4.649807E-5 .017092
30 1.461050E-17 3.871230E-9 7.366052E-5
40 2.435465E-25 6.443731E-14 6.716488E-8
50 1.188185E-33 3.170786E-19 1.850098E-11
100 0 0 1.833433E-34
1次元であれば3σを外れる確率はわずか千に三つにすぎないのですが,高次元化に伴い次第に中心部は過疎化し,10次元では半分以上が3σの郊外に移り住み,30次元では99%以上が裾の領域に集まるという結果になるのです.
===================================
【2】原点からの拡散が平均距離までに納まる確率
d次元正規分布において,原点からのユークリッド距離の確率分布は,χ^2分布の平方根分布であるχ分布になります.コラム「標的問題の解とχ分布」にはその導き方を紹介していますが,周辺分布がともに平均0,分散σ^2の正規分布となるd次元正規分布を極座標変換して,rとr+drの間に落ちる確率を導きだします.
とくに,自由度1のχ分布は,半正規分布:
f(x)=1/σsqr(2/π)exp(-x^2/2σ^2)
であり,この分布は期待値が0の正規分布:
f(x)=1/σsqr(2π)exp(-x^2/2σ^2)
をy軸で折り返した分布になっています.また,自由度2のχ分布はレイリー分布:
f(x)=x/σ^2exp(-x^2/2σ^2)
自由度3のχ分布はマクスウェル分布:
f(x)=2^(3/2)/σ^3x^2exp(-x^2/2σ^2)
と命名されています.また,自由度dのχ分布の平均値は
Γ((d+1)/2))/Γ(d/2)√(2)σ
で与えられます.
この節では,原点からの拡散が平均距離までに納まる確率を求めてみることにしますが,ガンマ関数の漸近展開式(スターリングの公式)
Γ(t)=√(2π/t)t^texp(-t){1+1/(12t(+1/(288t^2)-139/(51840t^3)-571/(2488320t^4)+・・・}
より,
Γ((d+1)/2))/Γ(d/2)√2=√(d){1-1/(4d)+1/(32d^2)+5/(128d^3)-21/(2048d^4)-399/(8192d^5)+869/(65536d^6)+・・・}
と漸近展開されますから,dが大きい領域ではほぼ√(d)σまでに納まる確率に一致します.
d 平均距離 d 平均距離
1 .575062 13 .513665
2 .540061 14 .513124
3 .533050 15 .512642
4 .527316 16 .512210
5 .523730 17 .511818
6 .521238 18 .511463
7 .519383 19 .511137
8 .517937 20 .510838
9 .516769 30 .508756
10 .515801 40 .507547
11 .514983 50 .506730
12 .514279 100 .504730
いまのところ,再帰確率との間に明示的な関係は見いだせませんが,計算の結果,原点からの拡散が平均距離までに納まる確率は60%から50%で,この後単調に減少し,いずれ一定の値に収束するかのように見えました.
F(x)=(x/2)^(d/2)1F1(d/2,1+d/2,-x/2)/Γ(1+d/2)
=(x/2)^(d/2)exp(-x/2)1F1(1,1+d/2,x/2)/Γ(1+d/2)
において
x=2*{Γ((d+1)/2))/Γ(d/2)}^2 〜 d
とおいた値はd→∞のとき,はたして一定値に収束するのでしょうか? 当該関数は単調減少関数で下限≧0なので,数学的には収束しますし,グラフを描くと極限値は0.5であろうと思われます.
問題はその証明です.χ^2分布の分布関数は,
F(x)=γ(d/2,x/2)/Γ(d/2)=1-Γ(d/2,x/2)/Γ(d/2)
=(x/2)^(d/2)exp(-x/2)Σ(x/2)^k/(k+n/2)!
とも書けるのですが,スターリングの法則
Γ(1+d/2)=(d/2)! 〜 √(πd)(d/2)^(d/2)exp(-d/2)
あるいは,不完全ガンマ関数の漸近展開
Γ(a,x)=exp(-x)U(1-a,1-a,x)
〜 x^(1-a)exp(-x)2F0(1-a,1,-1/x)
=x^(a-1)exp(-x){1+(a-1)/x+(a-1)(a-2)/x^2+・・・}
=x^(a-1)exp(-x){1+O(1/x)}
を用いても最終収束値が0.5になることを示すことができませんでした.式の形をみる限り,何とか極限値の厳密解は求められそうな気はするのですが,・・・.
酔歩が平均距離以内に滞在する確率が0.5に収束するといっても,インパクトは少ないでしょうが,これらが正方格子のパーコレーション閾値pc:0.593(サイト過程)と0.5(ボンド過程)の間に納まるといったらそうではないでしょう.これは単なる偶然なのでしょうか?
また,十分に次元の高い超立方格子のボンド過程では,
pc 〜 1/(2d−1)
正方格子と単純立方格子のボンド過程の閾値は
pc 〜 1/(2d−2)
で漸近近似されますが,これと再帰確率の漸近近似式
pd 〜 1/2(d−1)
に何か関係があるに違いないと推測することは荒唐無稽なことなのでしょうか?
以上のような数々の課題が残される結果となりましたが,これらについては引き続き検討していきたいと考えています.
===================================
【3】Wilson-Hilfertyの近似式
「格子上の確率論」をめぐる一連のコラムでは,これまでいくつかの漸近評価式,たとえば,
u2n 〜 2^(1-d)d^(d/2)(πn)^(-d/2)
もっと正確には
u2n 〜 2^(1-d)d^(d/2)(πn)^(-d/2)[1-d/(8n)+(4d-3d^2+2d^3/(384n^2)+O(1/n^3)]
あるいは
pd 〜 1/(2d){1+1/d+7/(4d^2)+35/(8d^3)+215/(16d^4)}
などをみてきました.
そこで,χ^2分布の分布関数:
F(x)=(x/2)^(d/2)exp(-x/2)1F1(1,1+d/2,x/2)/Γ(1+d/2)
において,dが十分に大きいとき,どのように漸近近似されるかを考えてみるのは自然な発想でしょう.
前節でも述べましたが,式を展開すると,
F(x)=(x/2)^(d/2)exp(-x/2){1/Γ(1+d/2)+1/Γ(2+d/2)(x/2)+1/Γ(3+d/2)(x/2)^2+1/Γ(4+d/2)(x/2)^3+・・・}
=(x/2)^(d/2)exp(-x/2)Σ1/Γ(1+d/2+k)(x/2)^k
ここで,スターリングの公式:
n! 〜 √(2πn)n^nexp(-n){1+O(1/n)}
を用いても,dに関するローラン級数展開のような便利な形には変形できそうにありません.不完全ガンマ関数:Γ(a,x)のx→∞に対する漸近展開式:
Γ(a,x)=x^(a-1)exp(-x)Σ(-1)^k(1-a)k/x^k
=x^(a-1)exp(-x){1+O(1/x)}
および,その連分数展開式はよく知られているのですが,・・・.
しかし,打つ手がないわけではありません.χ^2分布では,簡便さと適当な精度をもつ近似関数がWilson-Hilfertyにより求められているのです.Wilson-Hilfertyは,自由度νのχ^2について,(χ^2/ν)^(1/3)が,平均値(1-2/9ν),分散2/9νの正規分布で近似できることを示しました.したがって,
Φ(x)=1/2+1/√2πxexp(-x^2/2)1F1(1,3/2,x^2/2)
=1/2+1/√2π{x-x^3/2・1!・3+x^5/2^2・2!・5-・・・+(-1)^(2k+1)x^(2k+1)/2^k・k!・(2k+1)+・・・}
に
x={(χ^2/d)^(1/3)-(1-2/9d)}/√{2/(9d)}
を代入すればdに関するローラン級数展開が得られます.
この近似関数を利用して計算するプログラムと計算結果を以下に示しますが,近似式とはいっても,相対誤差は%オーダーですから,実用的には十分な有効数字があります.
===================================
3000 DEFDBL A-H,J-Z
3010 FOR I=1 TO 20
3020 DF=I
3030 PRINT:PRINT DF
3040 C=1:UUX=C*C:GOSUB *CHI2.PROB:PRINT P0
3050 C=2:UUX=C*C:GOSUB *CHI2.PROB:PRINT P0
3060 C=3:UUX=C*C:GOSUB *CHI2.PROB:PRINT P0
3070 '
3080 Z=(1+DF)/2:GOSUB *LOG.GAMMA:G1#=G#
3090 Z=DF/2 :GOSUB *LOG.GAMMA:G2#=G#
3100 C=EXP(G1#-G2#)*SQR(2):UUX=C*C:GOSUB *CHI2.PROB:PRINT P0
3110 NEXT I
3120 END
3130 '
3140 ' ** NORMAL DISTRIBUTION **
3150 '
3160 *NORMAL.PROB:
3170 AA1=.196854
3180 AA2=.115194
3190 AA3=.000344
3200 AA4=.019527
3210 W=ABS(UUN)
3220 P0=1+W*(AA1+W*(AA2+W*(AA3+W*AA4)))
3230 P0=P0^4
3240 P0=1-.5/P0
3250 P0=.5+(P0-.5)*SGN(UUN)
3260 PP=1-P0
3270 RETURN
3280 '
3290 ' ** CHI-SQUARE DISTRIBUTION **
3300 '
3310 *CHI2.PROB:
3320 AA1=2/(9*DF)
3330 AA2=UUX/DF
3340 W=AA2^(1/3)
3350 W1=W+AA1-1
3360 UUN=W1/SQR(AA1)
3370 GOSUB *NORMAL.PROB
3380 PP=1-P0
3390 RETURN
===================================
d σ 2σ 3σ 平均距離
1 .681555 .957270 .996913 .569273
2 .387574 .866939 .988883 .540086
3 .196530 .739686 .971316 .530393
4 .091143 .593105 .939849 .525393
5 .039092 .448822 .891882 .522250
6 .015907 .320934 .827326 .520047
7 .006332 .218627 .748232 .518393
8 2.531766E-3 .142288 .658165 .517093
9 1.035646E-3 .088539 .562235 .516036
10 4.382970E-4 .052826 .467376 .515154
11 1.929900E-4 .030395 .377027 .514403
12 8.858393E-5 .016998 .295805 .513755
13 4.237375E-5 .009322 .226141 .513187
14 2.109001E-5 5.057111E-3 .168482 .512685
15 1.089753E-5 2.734290E-3 .122296 .512235
16 5.831338E-6 1.482940E-3 .086497 .511831
17 3.223235E-6 8.107520E-4 .059667 .511464
18 1.835813E-6 4.484581E-4 .040217 .511130
19 1.074900E-6 2.516119E-4 .026557 .510823
20 6.456170E-7 1.434266E-4 .017237 .510540
30 1.120323E-8 1.293484E-6 1.797174E-4 .508562
40 6.421157E-10 4.303265E-8 3.649673E-6 .507396
50 7.172079E-11 3.218466E-9 1.723605E-7 .506605
100 9.396650E-14 1.512470E-12 2.388288E-11 .504656
ここに掲げた計算結果は,この節で解説した方法で計算したものではなく,Hastingsの近似式を使って簡便に求めたものです.正規分布の分布関数を求めるための近似式は多数提案されていますが,なかでもHastingsの近似式はよく知られています.Hastingsの近似式と呼ばれるものには,もっと精度の良い関数近似もあるのですが,ここでは,それほど高精度ではない近似式を用いています.なお,
3370 GOSUB *NORMAL.PROB → 3370 GOSUB *NORMAL.PROB.HGF
と変更すれば,解説どおりの計算となります.
===================================