Aritalab:Lecture/NetworkBiology/Percolation

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (一次元の場合)
m (パーコレーションとは)
 
(11 intermediate revisions by one user not shown)
Line 3: Line 3:
 
==パーコレーションとは==
 
==パーコレーションとは==
  
パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率''p''で占有されるときに生成されるクラスターを解析する。
+
パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率 p で占有されるときに生成されるクラスターを解析します。
様々な格子において、確率 ''p'' がある閾値 <math>p_c</math> に達すると、無限に大きなクラスターが存在し始める(臨界現象)。この値を浸透閾値 (percolation threshold) と呼ぶ。浸透閾値 <math>p_c</math> はほとんどの場合について厳密解が求まっていないが、数値シミュレーション等で解析されている。
+
様々な格子において、確率 p がある閾値 p<sub>c</sub> に達すると、無限に大きなクラスターが存在し始めます。これを臨界現象といい、臨界点を浸透閾値 (percolation threshold) と呼びます。ある格子点が無限大のクラスターに含まれる確率を浸透確率 (percolation probability) とよびます。浸透閾値 p<sub>c</sub> はほとんどの場合について厳密解が求まっていませんが、数値シミュレーション等で解析されています。
  
上記のように格子点が確率 ''p'' で占有される過程を、正確にはサイト過程と呼ぶ。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 ''p'' で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼ぶ。
+
上記のように格子点が確率 p で占有される過程を、正確にはサイト過程と呼びます。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 p で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼びます。
  
 
{| class="wikitable" style="float:right"
 
{| class="wikitable" style="float:right"
 
|-
 
|-
!colspan=3| 主な浸透閾値<math>p_c</math> (*は厳密解)
+
!colspan=4| 格子の主な浸透閾値 p<sub>c</sub> (*のみ厳密解。<br/>ほとんどの場合解析的に解けない。)
 
|-
 
|-
! 格子の種類 || サイト || ボンド
+
! 格子の種類 || 配位数 || サイト || ボンド
 
|-
 
|-
| 蜂の巣 || 0.697043 || 0.65271<sup>*</sup>
+
| 蜂の巣 || 3 || 0.697043 || 0.65271<sup>*</sup>
 
|-
 
|-
| 正方 || 0.5927462 || 1/2 <sup>*</sup>
+
| 正方 || 4 || 0.5927462 || 1/2 <sup>*</sup>
 
|-
 
|-
| 三角 || 1/2 <sup>*</sup> || 0.34729<sup>*</sup>
+
| 三角 || 6 || 1/2 <sup>*</sup> || 0.34729<sup>*</sup>
 
|-
 
|-
| ダイヤモンド || 0.4301 || 0.3893
+
| ダイヤモンド || 4 || 0.4301 || 0.3893
 
|-
 
|-
| 単純立方 || 0.311608 || 0.248813
+
| 単純立方 || 6 || 0.311608 || 0.248813
 
|-
 
|-
| 体心立方 || 0.245691 || 0.180287
+
| 体心立方 || 8 || 0.245691 || 0.180287
 
|-
 
|-
| 面心立方<ref>同半径の球を敷き詰めたときの最密充填</ref> || 0.199236 || 0.120163  
+
| 面心立方<ref>同半径の球を敷き詰めたときの最密充填</ref> || 12 || 0.199236 || 0.120163  
 +
|}
 +
<!---
 
|-
 
|-
| d=4 超立方 || 0.196885 || 0.160131
+
| d=4 超立方 || || 0.196885 || 0.160131
 
|-
 
|-
| d=5 超立方 || 0.140797 || 0.118172
+
| d=5 超立方 || || 0.140797 || 0.118172
 
|-
 
|-
| d=6 超立方 || 0.109018 || 0.094202
+
| d=6 超立方 || || 0.109018 || 0.094202
 
|-
 
|-
| d=7 超立方 || 0.088951 || 0.078675
+
| d=7 超立方 || || 0.088951 || 0.078675
|}
+
--->
  
==クラスターと周縁==
+
==クラスター・周縁という概念==
各格子点は確率 ''p'' で占有されるとし、占有された格子点の集まりをクラスターと呼ぶ。特に、大きさが ''s'' のクラスターを ''s-''クラスターと呼ぶ。クラスターの周囲の格子点は空でなくてはならない。クラスターに隣接する空の格子点群を周縁 (perimeter) と呼ぶ。クラスターが大きくなると内部にも周縁が存在しうるので、周縁と周囲は異なることに注意しよう。
+
各格子点が確率 ''p'' で占有されるとし、占有された格子点の集まりをクラスターと呼びます。特に、大きさが ''s'' のクラスターを ''s-''クラスターと呼びます。クラスターの周囲の格子点は空でなくてはなりません。クラスターに隣接する空の格子点群を周縁 (perimeter) と呼びます。クラスターが大きくなると内部にも周縁が存在しうるので、周縁と周囲は異なることに注意します。
  
ある格子点を含む、大きさ ''s'' 、周縁 ''t'' の異なるクラスターの数を <math>a_{s,t}</math> であらわす。2次元格子の場合、以下のようになる。
+
ある格子点を含む、大きさ ''s'' 、周縁 ''t'' の異なるクラスターの数を <math>a_{s,t}</math> であらわします。2次元格子の場合は以下のようになります。占有点を黒、非占有点を白、注目している格子点を灰色であらわしています。
  
<math>a_{1,4} = 1 \quad a_{2,6} = 4 \quad a_{3,7} = 12 \quad a_{3,8} = 6</math>
+
<math>a_{1,4} = 1 \quad a_{2,6} = 4 \quad a_{3,8} = 6 \quad a_{3,7} = 12 </math>
  
==母関数とよく使う記法==
+
[[File:Lecture-NetworkBiology-Percolation.png]]
これからよく使う記法を[[Aritalab:Lecture/Basic/Generating_Function|母関数]] <math>\textstyle A(x,y) = \sum_{s,t} a_{s,t} x^s y^t</math> を使ってまとめておく。
+
 
+
* ある格子点が、大きさ''s''、周縁''t''のクラスターに含まれる確率
+
:<math>\textstyle p_{s,t} = a_{s,t} p^s (1-p)^t</math>
+
* ある格子点が、''s''-クラスターに含まれる確率
+
:<math>\textstyle P_s = \sum_t p_{s,t}</math>
+
* ある格子点が、有限の大きさのクラスターに含まれる確率
+
:<math>\textstyle F = \sum_{s,t} p_{s,t} = \sum_s P_s = A(p, 1-p)</math>
+
* ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)
+
:<math>\textstyle P_{\infty} = p - F</math>
+
* ある格子点が含まれる、有限の大きさのクラスターの平均サイズ
+
:<math>S = \frac{\sum_{s,t} s p_{s,t}}{F} = \frac{\sum_s s P_s}{\sum_s P_s} = x\frac{\partial}{\partial x}\log A(x,y) \Bigg|_{x=p,\ y=1-p}</math>
+
* 個々のクラスターを1回だけ数えたときの、クラスターの平均サイズ
+
:<math>\langle s \rangle = \frac{\sum_s P_s}{\sum_s (1/s)P_s}</math>
+
  
 
==一次元の場合==
 
==一次元の場合==
一次元の場合は、無限に長い直線上に、定められた間隔で格子点をおく。
 
無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので<math>p_c=1</math>である。
 
また、周縁サイズは常に<math>t=2</math>の1パターンのみとなる。
 
この簡便さから、多くの問いに対して厳密解を求めることができる。
 
  
: 母関数 <math>\textstyle A(x,y) = \sum_s s x^s y^2 = \frac{xy^2}{(1-x)^2}</math>
+
無限に長い直線上に一定間隔で格子点がある場合を考えます。
* ある格子点が、''s''-クラスターに含まれる確率
+
無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので、浸透閾値 p<sub>c</sub> = 1、周縁サイズは常に t = 2 です。この簡便さから、多くの問いに対して厳密解を求められます。
 +
 
 +
 
 +
* ある格子点が、s-クラスターに含まれる確率
 +
ある格子点は、大きさ s のクラスターのどの位置にもなりうるので s 通りの可能性があります。
 
:<math>\textstyle P_s = s p_{s,t} = s p^s (1-p)^2</math>
 
:<math>\textstyle P_s = s p_{s,t} = s p^s (1-p)^2</math>
* ある格子点が、有限の大きさのクラスターに含まれる確率
+
* 浸透確率(格子点が無限大のクラスターに含まれる確率)、クラスターの平均サイズ
:<math>\textstyle F = \sum_{s,t} p_{s,t} = \sum_s P_s = p</math>
+
{| class="wikitable"
* ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)
+
|valign="top"|
:<math>\textstyle P_{\infty} = p - F = 0</math>
+
|
* ある格子点が含まれる、有限の大きさのクラスターの平均サイズ
+
; p < p<sub>c</sub> = 1 の場合
:<math>
+
|
 +
; p = p<sub>c</sub> = 1 の場合
 +
|-
 +
|valign="top"|
 +
浸透確率
 +
|
 +
: 0
 +
|valign="top"|
 +
: 1
 +
|-
 +
|valign="top"|
 +
平均サイズ
 +
|
 +
:( 1 + p ) / ( 1 - p )
 +
|
 +
: 0
 +
|}
 +
 
 +
平均サイズの計算は説明が必要でしょう。それぞれの s-クラスターが出現する確率 P<sub>s</sub> にサイズ s をかけたものを、s-クラスターが出現する確率の総和で割れば平均サイズが求まります。
 +
<math>
 
\begin{align}
 
\begin{align}
S &= \textstyle \frac{\sum_{s,t} s p_{s,t}}{F} = \frac{\sum_s s P_s}{\sum_s P_s}
+
S &= \frac{\sum_s s P_s}{\sum_s P_s}
= \frac{x}{p} \frac{\partial}{\partial x} A(x,y) \Big|_{x=p,\ y=1-p}\\
+
&= \textstyle \frac{(1-p)^4 + 2p(1-p)^2(1-p)}{(1-p)^4} = \frac{1+p}{1-p}
+
 
\end{align}
 
\end{align}
 
</math>
 
</math>
* 個々のクラスターを1回だけ数えたときの、クラスターの平均サイズ
+
分母は各点がクラスターに含まれる確率に等しいので p になります。面倒なのは分子の計算です。
:<math>\textstyle \langle s \rangle = \frac{\sum_s P_s}{\sum_s (1/s)P_s}</math>
+
  
===相関関数と相関距離===
+
<math>
ある占有された格子点から <math>r</math> だけ離れた格子点が同じクラスターに属する確率を <math>g(r)</math> であらわし、相関関数とよぶ。
+
\begin{align}
 +
\sum_s s P_s &= (1-p)^2 \sum_s s^2 p^s \\
 +
&= (1-p)^2 \big(p \frac{d}{dp} \big)^2 \sum_s p^s\\
 +
&= (1-p)^2 \big(p \frac{d}{dp} \big) \big(p \frac{d}{dp} \big) \frac{p}{1-p}\\
 +
&= (1-p)^2 \big(p \frac{d}{dp} \big) \frac{p}{(1-p)^2}\\
 +
&= (1-p)^2 p \frac{(1-p)^2 + 2p(1-p)}{(1-p)^4} \\
 +
&= p \frac{1+p}{1-p}
 +
\end{align}
 +
</math>
  
<math>\textstyle g(r) = p^r = \exp( -r / \xi )</math>
+
お疲れ様でした。
  
ここで<math>\textstyle \xi = -\frac{1}{\log(p)} \sim \frac{1}{1 - p} = \frac{1}{p_c-p}</math>。この <math>\xi</math> を相関距離という。
+
==木またはベーテ格子の場合==
  
大まかにいうと、相関距離はクラスターの差し渡しに比例する。 占有確率 ''p'' が大きくなると <math>\xi</math> も増え、''p'' が小さくなると<math>\xi</math> も減る。一次元の場合、 1列に並ぶだけなので <math>\textstyle S \propto \xi  (p \rightarrow p_c)</math> が成立、つまり相関距離はクラスターの平均サイズに比例する。
+
次数が一定で無限に大きな木をベーテ格子と呼びます(有限の場合はケーリー木とも呼びます。
さらに <math>\textstyle \Sigma_r g(r) = S</math> も成立する。
+
磁性を扱う方法の一つであるベーテ近似によりこの木の厳密解が求まるため、ベーテ格子と呼ぶようになりました。)
 +
ベーテ格子はサイクルを持たない一次元の場合は、次数が2のベーテ格子です。
  
;証明
+
;特徴
:一次元の場合、''r'' ステップ離れた箇所まで全ての点が占有されねばならないから <math>\textstyle g(0) = 1,\ g(1)= p,\ g(2) = p^2, g(r) = p^r</math>が成立。
+
* 次数が d の木の場合、原点は d 本の枝を持つ。
:<math>\textstyle \Sigma_r g(r) = \Sigma_0^{\infty}g(r) + \Sigma_0^{-\infty}g(r) - g(0) = 2 \frac{1-p^{\infty}}{1-p} - 1 = \frac{1+p}{1-p} = S</math>。(証明終)
+
* 残りの点は通ってきた点のほかに d &minus; 1 本の枝を持ち、それらの先に確率 p で占有される格子点が存在する。
  
==木またはベーテ格子の場合==
+
先に進める確率は (d &minus; 1) p になるので、無限大のクラスターが存在し始める値は p<sub>c</sub> = 1 / (d - 1)、つまり各点に平均 d / (d - 1) 本の枝があれば、無限に大きなクラスターが存在します。
次数が一定で無限に大きな木をベーテ格子と呼ぶ(有限の場合はケーリー木と呼んでもよい)。
+
逆に、これより低い p の値では、無限に大きなクラスターは存在しません。
磁性を扱う方法の一つであるベーテ近似によりこの木の厳密解が求まるため、ベーテ格子と呼ぶようになった。
+
以降、簡単のため d = 3 ( p<sub>c</sub> = 1/2 ) に話を限定します。
一次元の場合は、次数が2のベーテ格子と考えられる。
+
  
次数が ''d'' の木の場合、原点は ''d'' 本の枝を持つ。
+
=== d = 3 の木===
残りの点は通ってきた点のほかに <math>d-1</math> 本の枝を持ち、それらの先に確率 ''p'' で占有される格子点が存在する。
+
ここまでの議論から、浸透閾値は 1/2 であり、浸透確率が 1/2 を超えると、その頂点にたどり着いた枝を除いた残り 2 本のうちどちらかがつながっているから、無限大のクラスターが存在します。
先に進める確率は <math>(d-1)p</math> になるので、無限大のクラスターが存在し始める値は <math>\textstyle p_c=\frac{1}{d-1}</math>。
+
つまり各点からみて平均 <math>\textstyle \frac{d}{d-1}</math> 本つながっていれば、無限に大きなクラスターになる。
+
逆に、これより低い ''p'' の値では、無限に大きなクラスターは存在しない。
+
以降、簡単のため <math>\textstyle d=3\ (p_c = 1/2)</math> に話を限定する。
+
母関数を求めるのはややこしいが、興味のある人は「パーコレーションの科学」(小田垣 孝著 裳華房)を参照してほしい。
+
  
===浸透確率 ''P''<sub>∞</sub>===
+
===格子点が無限大のクラスターに含まれる確率 P<sub>∞</sub>===
ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)を求めよう。
+
p > p<sub>c</sub> = 1 / 2 のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を Q と書きます。
<math>p > p_c = 1/2</math> のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を''Q''とする。
+
 
ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。
 
ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。
これは''Q''に等しいはずなので<math>Q = (1-p) + pQ^2</math>。これを解くと<math>Q = 1,\ (1-p)/p</math>。
+
これは Q に等しいはずなので
  
<math>Q=1</math>の場合は無限遠に決してつながらず、<math>p < 1/2</math> のときの <math>P=0</math> に対応する。
+
:Q = (1 - p) + p Q<sup>2</sup>
<math>p > 1/2</math> のとき、 <math>Q = (1-p)/p</math> を考える。
+
 
原点が占有されていても無限遠につながらない確率は <math>p-P_{\infty} = pQ^3</math>
+
を満たします。これを解くと Q = 1, (1 - p) / p。
これより<math>P_{\infty} = p(1-Q^3) = p - (1-p)^3/p^2</math>
+
 
 +
* Q = 1 の場合
 +
無限遠に決してつながらず、p < 1/2 のときに対応します。
 +
* Q = (1 - p) / p の場合
 +
p > 1/2 に相当します。 原点が占有されていても無限遠につながらない確率は
 +
: p -P<sub>∞</sub> = p Q<sup>3</sup>
 +
 
 +
これより P<sub>∞</sub> = p (1-Q<sup>3</sup>) = p - (1-p)<sup>3</sup> / p<sup>2</sup> です。
  
 
まとめると
 
まとめると
 
{| class ="wikitable" style="text-align:center"
 
{| class ="wikitable" style="text-align:center"
! || <math>p < 1/2</math> || <math>p > 1/2</math>
+
! || <math>\textstyle p < \frac{1}{2}</math> || <math>\textstyle p > \frac{1}{2}</math>
 
|-
 
|-
| ある点が有限のクラスターに含まれる確率 ''F'' || ''p'' || <math>(1-p)^3/p^2</math>
+
| 有限のクラスターに含まれる確率  || p || <math>\textstyle \frac{(1-p)^3}{p^2}</math>
 
|-
 
|-
| ある点が無限のクラスターに含まれる確率 ''P''<sub>∞</sub> || 0 || <math>p - (1-p)^3/p^2</math>
+
| 無限大のクラスターに含まれる確率  || 0 || <math>\textstyle p - \frac{(1-p)^3}{p^2}</math>
 
|}
 
|}
  
===クラスターの平均サイズ ''S''===
+
===クラスターの平均サイズ S===
ある枝の先につながっている格子点数の期待値を <math>T</math> と書く。
+
ある枝の先につながっている格子点数の期待値を T とします。
まず <math>p < p_c = 1/2</math> の場合を考える。
+
まず p < p<sub>c</sub> = 1/2 の場合を考えます。
どの格子点もサイズが無限大のクラスターには属さない。
+
どの格子点もサイズが無限大のクラスターには属しません。(そうしないと平均サイズが計算できない。)
従って、枝の先にある格子点が占有されていればその格子点プラス二つの枝の平均サイズが付け加わるから <math>T = (1-p)0 +p(1+2T)</math>。
+
枝の先にある格子点が占有されていれば、その格子点プラス二つの枝の平均サイズが付け加わるので
これを解くと <math>T=p/(1-2p)</math>。
+
 
従って、ある頂点が属するクラスターの平均サイズは <math>S = 1 + 3T = (1+p)/(1-2p)</math>
+
: T = (1 - p) 0 + p (1 + 2T)
この議論は容易に一般化できる。
+
 
次数 ''d'' の場合 <math>p < p_c = 1/(d-1)</math> なら <math>S = (1+p)/(1-dp)</math>。
+
これを解いて T = p / (1 - 2p) です。従って、ある頂点が属するクラスターの平均サイズは
 +
 
 +
: S = 1 + 3T = (1 + p) / (1 - 2p)
 +
 
 +
まとめると
 +
{| class ="wikitable" style="text-align:center"
 +
! || p < 1/2 || p >= 1/2
 +
|-
 +
| 平均サイズ || <math>\frac{(1+p)}{(1-2p)}</math> || <math>\infty</math>
 +
|}
 +
 
 +
この議論は容易に一般化できます。次数 d の場合 p < p<sub>c</sub> = 1 / (d - 1) なら S = (1 + p) / (1 - dp) です。
 +
 
 +
 
  
 +
;参考
 
<references/>
 
<references/>

Latest revision as of 14:49, 3 August 2016

Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

[edit] パーコレーションとは

パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率 p で占有されるときに生成されるクラスターを解析します。 様々な格子において、確率 p がある閾値 pc に達すると、無限に大きなクラスターが存在し始めます。これを臨界現象といい、臨界点を浸透閾値 (percolation threshold) と呼びます。ある格子点が無限大のクラスターに含まれる確率を浸透確率 (percolation probability) とよびます。浸透閾値 pc はほとんどの場合について厳密解が求まっていませんが、数値シミュレーション等で解析されています。

上記のように格子点が確率 p で占有される過程を、正確にはサイト過程と呼びます。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 p で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼びます。

格子の主な浸透閾値 pc (*のみ厳密解。
ほとんどの場合解析的に解けない。)
格子の種類 配位数 サイト ボンド
蜂の巣 3 0.697043 0.65271*
正方  4 0.5927462 1/2 *
三角 6 1/2 * 0.34729*
ダイヤモンド 4 0.4301 0.3893
単純立方 6 0.311608 0.248813
体心立方 8 0.245691 0.180287
面心立方[1] 12 0.199236 0.120163

[edit] クラスター・周縁という概念

各格子点が確率 p で占有されるとし、占有された格子点の集まりをクラスターと呼びます。特に、大きさが s のクラスターを s-クラスターと呼びます。クラスターの周囲の格子点は空でなくてはなりません。クラスターに隣接する空の格子点群を周縁 (perimeter) と呼びます。クラスターが大きくなると内部にも周縁が存在しうるので、周縁と周囲は異なることに注意します。

ある格子点を含む、大きさ s 、周縁 t の異なるクラスターの数を a_{s,t} であらわします。2次元格子の場合は以下のようになります。占有点を黒、非占有点を白、注目している格子点を灰色であらわしています。

a_{1,4} = 1 \quad a_{2,6} = 4 \quad a_{3,8} = 6 \quad a_{3,7} = 12

Lecture-NetworkBiology-Percolation.png

[edit] 一次元の場合

無限に長い直線上に一定間隔で格子点がある場合を考えます。 無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので、浸透閾値 pc = 1、周縁サイズは常に t = 2 です。この簡便さから、多くの問いに対して厳密解を求められます。


  • ある格子点が、s-クラスターに含まれる確率

ある格子点は、大きさ s のクラスターのどの位置にもなりうるので s 通りの可能性があります。

\textstyle P_s = s p_{s,t} = s p^s (1-p)^2
  • 浸透確率(格子点が無限大のクラスターに含まれる確率)、クラスターの平均サイズ
p < pc = 1 の場合
p = pc = 1 の場合

浸透確率

0
1

平均サイズ

( 1 + p ) / ( 1 - p )
0

平均サイズの計算は説明が必要でしょう。それぞれの s-クラスターが出現する確率 Ps にサイズ s をかけたものを、s-クラスターが出現する確率の総和で割れば平均サイズが求まります。 
\begin{align}
S &= \frac{\sum_s s P_s}{\sum_s P_s}
\end{align}
分母は各点がクラスターに含まれる確率に等しいので p になります。面倒なのは分子の計算です。


\begin{align}
\sum_s s P_s &= (1-p)^2 \sum_s s^2 p^s \\
&= (1-p)^2 \big(p \frac{d}{dp} \big)^2 \sum_s p^s\\
&= (1-p)^2 \big(p \frac{d}{dp} \big) \big(p \frac{d}{dp} \big) \frac{p}{1-p}\\
&= (1-p)^2 \big(p \frac{d}{dp} \big) \frac{p}{(1-p)^2}\\
&= (1-p)^2 p \frac{(1-p)^2 + 2p(1-p)}{(1-p)^4} \\
&= p \frac{1+p}{1-p}
\end{align}

お疲れ様でした。

[edit] 木またはベーテ格子の場合

次数が一定で無限に大きな木をベーテ格子と呼びます(有限の場合はケーリー木とも呼びます。 磁性を扱う方法の一つであるベーテ近似によりこの木の厳密解が求まるため、ベーテ格子と呼ぶようになりました。) ベーテ格子はサイクルを持たない一次元の場合は、次数が2のベーテ格子です。

特徴
  • 次数が d の木の場合、原点は d 本の枝を持つ。
  • 残りの点は通ってきた点のほかに d − 1 本の枝を持ち、それらの先に確率 p で占有される格子点が存在する。

先に進める確率は (d − 1) p になるので、無限大のクラスターが存在し始める値は pc = 1 / (d - 1)、つまり各点に平均 d / (d - 1) 本の枝があれば、無限に大きなクラスターが存在します。 逆に、これより低い p の値では、無限に大きなクラスターは存在しません。 以降、簡単のため d = 3 ( pc = 1/2 ) に話を限定します。

[edit] d = 3 の木

ここまでの議論から、浸透閾値は 1/2 であり、浸透確率が 1/2 を超えると、その頂点にたどり着いた枝を除いた残り 2 本のうちどちらかがつながっているから、無限大のクラスターが存在します。

[edit] 格子点が無限大のクラスターに含まれる確率 P

p > pc = 1 / 2 のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を Q と書きます。 ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。 これは Q に等しいはずなので

Q = (1 - p) + p Q2

を満たします。これを解くと Q = 1, (1 - p) / p。

  • Q = 1 の場合

無限遠に決してつながらず、p < 1/2 のときに対応します。

  • Q = (1 - p) / p の場合

p > 1/2 に相当します。 原点が占有されていても無限遠につながらない確率は

p -P = p Q3

これより P = p (1-Q3) = p - (1-p)3 / p2 です。

まとめると

\textstyle p < \frac{1}{2} \textstyle p > \frac{1}{2}
有限のクラスターに含まれる確率 p \textstyle \frac{(1-p)^3}{p^2}
無限大のクラスターに含まれる確率 0 \textstyle p - \frac{(1-p)^3}{p^2}

[edit] クラスターの平均サイズ S

ある枝の先につながっている格子点数の期待値を T とします。 まず p < pc = 1/2 の場合を考えます。 どの格子点もサイズが無限大のクラスターには属しません。(そうしないと平均サイズが計算できない。) 枝の先にある格子点が占有されていれば、その格子点プラス二つの枝の平均サイズが付け加わるので

T = (1 - p) 0 + p (1 + 2T)

これを解いて T = p / (1 - 2p) です。従って、ある頂点が属するクラスターの平均サイズは

S = 1 + 3T = (1 + p) / (1 - 2p)

まとめると

p < 1/2 p >= 1/2
平均サイズ \frac{(1+p)}{(1-2p)} \infty

この議論は容易に一般化できます。次数 d の場合 p < pc = 1 / (d - 1) なら S = (1 + p) / (1 - dp) です。


参考
  1. 同半径の球を敷き詰めたときの最密充填
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox