Aritalab:Lecture/NetworkBiology/Zipf

Latest revision as of 22:07, 11 August 2011

[edit] Zipf の法則とランク・サイズ則

都市毎の人口や会社の規模、個人の所得を大きさの順に並べて順位 r をつけ、その大きさを $x_r$ とおくと

$x_r = C r^{-(1+\alpha)}\ \,(C, \alpha: const.)$

の形になります（α の値は小さい）。一般には Zipf の法則として知られる関係は、Rank-Size Rule とも呼ばれます。

[edit] ランダムな区画取り

[edit] ランダムに 2 点をとったとき、 2 点間の距離の分布

線分 [0,1] 上にランダムにとる点を y とします。 y から距離 x と x + dx の間に 2 点目を取る確率を計算しましょう。

0 または 1 から幅 x 以内に y をとるとき (確率 2 x)

y から x 離れた地点は片側にしかとることができません。2 番目の点が x と x + dx の間に落ちる確率は 2x dx です。

残りの範囲に y をとるとき (確率 1 - 2x)

y から x 離れた地点を両側にとれます。2 番目の点が x と x + dx の間に落ちる確率は 2(1-2x) dx です。

結局、2 点間の距離の確率は以下のようになります。

$\,f(x) dx = 2 x dx + 2 (1-2x) dx = 2(1-x)dx$

平均値は 1/3 です。

$\int^1_0 x f(x) dx = \int^1_0 -2x^2 + 2x dx = 1/3$

[edit] ランダムに 2 点をとる作業を n 回繰り返したとき、r 番目の距離の分布

ランダムにとった区間長が w より長い確率 p 、短い確率 q はそれぞれ以下のようになります。

$\begin{align} p(w) &=\textstyle \int^1_{w} f(x) dx = (1 - w)^2 \\ q(w) &= 1 - p(w) \end{align}$

n 回繰り返したときに、r 番目に長い区間が x である確率 $g_r(x)$ は r − 1 個が x より長く、n − r 個が、より短い区間であることに相当します。

$\begin{align} g_r(x) &= \frac{n!}{(n-r)!(r-1)!}p(x)^{r-1}q(x)^{n-r} f(x) \\ &= \frac{n!}{(n-r)!(r-1)!} (1 - x)^{2(r-1)}[1-(1 - x)^2]^{n-r} \cdot 2(1-x) \end{align}$

期待値を計算するのに $(1-x)^2 = z$ と変数変換します。微分すると $dz/dx = 2(x-1)$ です。

$\begin{align} E[g_r(x)] &= \int^1_0 x g_r(x) dx\\ &= \frac{n!}{(n-r)!(r-1)!} \int^0_1 (1-z^{1/2}) z^{r-1}(1-z)^{n-r} \cdot 2(1-x) dz (dx/dz) \\ &= \frac{n!}{(n-r)!(r-1)!} \int^1_0 (1-z^{1/2}) z^{r-1}(1-z)^{n-r} dz \\ &= \frac{n!}{(n-r)!(r-1)!}\big[ \int^1_0 z^{r-1}(1-z)^{n-r} dz - \int^1_0 z^{r-1/2}(1-z)^{n-r} dz\big] \\ &= \frac{n!}{(n-r)!(r-1)!}\big[ \frac{\Gamma(r)\Gamma(n-r+1)}{\Gamma(n+1)} - \frac{\Gamma(r+\frac{1}{2})\Gamma(n-r+1)}{\Gamma(n+\frac{3}{2})} \big] \\ &= \frac{n!}{(n-r)!(r-1)!}\big[ \frac{(r-1)!(n-r)!}{n!} - \frac{\Gamma(r+\frac{1}{2})}{\Gamma(n+\frac{3}{2})} (n-r)! \big] \\ &= 1 - \frac{n!}{(r-1)!}\frac{\Gamma(r+\frac{1}{2})}{\Gamma(n+\frac{3}{2})} \end{align}$

一番長い区間の期待値: $\begin{align} E[g_1(x)] &= 1 - n! \cdot \frac{\Gamma(\frac{3}{2})}{\Gamma(n + \frac{3}{2})} \\ &= 1 - \frac{\sqrt{\pi}}{2} \frac{n!}{\Gamma(n + \frac{3}{2})} \end{align}$

一番短い区間の期待値: $\begin{align} E[g_n(x)] &= 1 - n \cdot \frac{\Gamma(n+\frac{1}{2})}{\Gamma(n+\frac{3}{2})}\\ &= 1 - \frac{2n}{2n+1} \end{align}$

[edit] ランダムな分割

[edit] 線分を s 個に分割した時の長さの期待値

まず、線分 [0,1] を 3 個に分割する場合を考えます。ランダムに 2 点を取ったとき、任意に選んだ断片の長さが x である確率を $f_3(x)$ とします。一般性を失わずにこの断片が左端とします。2 点のうち、1 つは x の位置に固定し (2 通り)、残りは (1 − x) の中から選べます。

$f_3(x) = 2 (1-x)$

この値は、ランダムに 2 点を取ったときの二点間の距離に等しくなっていて、長さの期待値は 1/3 です。

ランダムに s 点を取るときも同様に考えます。s 点のうち 1 つを x の位置に固定し、残りは (1 − x) の中から選びます。s 個に分割するとき、任意に選んだ断片の長さが x になる確率は

$f_s(x) = (s-1) (1-x)^{s-2}$

期待値は

$\int^1_0 x f_s(x) dx = - \int^1_0 (1-x)^{s-1} dx = - \frac{1}{s} \Big[ (1-x)^s \Big]^1_0 = \frac{1}{s}$

[edit] 線分を s 個に分割した時の長さの差の期待値

線分 [0,1] をランダムに s 分割するとき、得られる線分の長さを短いものから長いものに並べ替えて $l_1, l_2, \cdots, l_s$ と書きましょう。ここで $l_1< l_2 < \cdots < l_s$ また $\textstyle \sum^s_{i=1} l_i =1$ です。

ここで r 番目の線分と r+1 番目の線分の差を $d_r$ と書きます。

$\begin{align} d_1 &= l_2 - l_1,\\ d_2 &= l_3 - l_2,\\ &\cdots\\ d_{s-2} &= l_{s-1} - l_{s-2}\\ d_{s-1} &= l_s - l_{s-1} \end{align}$

このとき $\textstyle l_r = l_1 + \sum^{r-1}_{i=1} d_i$ です。全ての線分を足し合わせると長さは 1 になります。

$\begin{align} 1 &= l_1 + l_2 + l_3 + \cdots + l_{s-1} + l_s\\ &= sl_1 + (s-1)d_1 + (s-2)d_2 + \cdots + 2 d_{s-2} + d_{s-1} \end{align}$

ここで、新たに 1 点を追加する過程を考えましょう。ランダムに追加する 1 点は $sl_1$ の確率で（ s + 1 個に増えたときに）最短の線分を作り、 $(s-1)d_1$ の確率で 2 番目に短い線分を作り、 $(s-2)d_2$ の確率で 3 番目に短い線分を作ります。しかし、どの線分も全て等確率で生じるはずなので、結果として以下が成立します。

$\textstyle E[sl_1] = E[(s-1)d_1] = E[(s-2)d_2] = \cdots = E[d_{s-1}] = \frac{1}{s}$

ここから

$\textstyle E[l_1] = \frac{1}{s^2},\ E[d_1] = \frac{1}{s(s-1)},\ E[d_2] = \frac{1}{s(s-2)},\ \cdots$

$\textstyle E[d_i] = \frac{1}{s(s-i)},\ \cdots \ E[d_{s-1}] = \frac{1}{s}$

[edit] 線分を s 個に分割してから順位づけした時の期待値

線分の差である d_i の期待値から、初めに仮定した l の期待値を求めましょう。短い方から i 番目の長さは

$\begin{align} E[l_2] &= \textstyle l_1 + d_1 = \frac{1}{s^2} + \frac{1}{s(s-1)}\\ E[l_3] &= \textstyle l_1 + d_1 + d_2 = \frac{1}{s^2} + \frac{1}{s(s-1)} + \frac{1}{s(s-2)}\\ \cdots \\ E[l_i] &= \textstyle \frac{1}{s}\sum^{i-1}_{j=0}\frac{1}{s-j}\\ &= \textstyle \frac{1}{s} (\sum^{s}_{j=1}\frac{1}{j} - \sum^{s-i}_{j=1}\frac{1}{j})\\ &\simeq \textstyle \frac{1}{s} \log\frac{s}{s-i} \end{align}$

同様に、長いほうから順番に並べた場合は i 番目の長さは

$\begin{align} E[l_i] &= \textstyle\frac{1}{s}\sum^{s-i}_{j=0}\frac{1}{s-j}\\ &= \textstyle\frac{1}{s}(\sum^{s}_{j=1}\frac{1}{j} - \sum^{i-1}_{j=1}\frac{1}{j})\\ &\simeq \textstyle\frac{1}{s} \log\frac{s}{i-1} \end{align}$

@@ Line 20: / Line 20: @@
 y から x 離れた地点を両側にとれます。2 番目の点が x と x + dx の間に落ちる確率は 2(1-2x) dx です。
-結局、2 点間の距離の確率は <math>\,f(x) dx = 2 x dx + 2 (1-2x) dx = 2(1-x)dx</math> で与えられます。平均値は 1/3 になります。
+結局、2 点間の距離の確率は以下のようになります。
+<math>\,f(x) dx = 2 x dx + 2 (1-2x) dx = 2(1-x)dx</math>
+平均値は 1/3 です。
 :<math>
@@ Line 36: / Line 40: @@
 </math>
-n 回繰り返したときに、r 番目の区間長が x である確率 <math>g_r(x)</math> は r&minus;1 個が x より短く、n &minus; r 個が、より長い区間を得ることに相当します。
+n 回繰り返したときに、r 番目に長い区間が x である確率 <math>g_r(x)</math> は r &minus; 1 個が x より長く、n &minus; r 個が、より短い区間であることに相当します。
 :<math>
@@ Line 63: / Line 67: @@
 :<math>
 \begin{align}
-E[g_1(x)] &= 1 - n! \cdot \frac{\Gamma(3/2)}{\Gamma((n+1)+ 1/2)} \\
+E[g_1(x)] &= 1 - n! \cdot \frac{\Gamma(\frac{3}{2})}{\Gamma(n + \frac{3}{2})} \\
-&= 1 - \frac{ 2^{2n+1} n! (n+1)!}{(2n + 2)!}\\
+&= 1 - \frac{\sqrt{\pi}}{2} \frac{n!}{\Gamma(n + \frac{3}{2})}
 \end{align}
 </math>
@@ Line 78: / Line 82: @@
 ==ランダムな分割==
-===線分を s 個に分割したときの長さの期待値===
+===線分を s 個に分割した時の長さの期待値===
+まず、線分 [0,1] を 3 個に分割する場合を考えます。ランダムに 2 点を取ったとき、任意に選んだ断片の長さが x である確率を <math>f_3(x)</math> とします。一般性を失わずにこの断片が左端とします。2 点のうち、1 つは x の位置に固定し (2 通り)、残りは (1 &minus; x) の中から選べます。
+: <math>f_3(x) = 2 (1-x)</math>
+この値は、ランダムに 2 点を取ったときの二点間の距離に等しくなっていて、長さの期待値は 1/3 です。
+ランダムに s 点を取るときも同様に考えます。s 点のうち 1 つを x の位置に固定し、残りは (1 &minus; x) の中から選びます。s 個に分割するとき、任意に選んだ断片の長さが x になる確率は
+: <math>f_s(x) = (s-1) (1-x)^{s-2}</math>
+期待値は
+: <math>\int^1_0 x f_s(x) dx = - \int^1_0 (1-x)^{s-1} dx
+= - \frac{1}{s} \Big[ (1-x)^s \Big]^1_0 = \frac{1}{s}</math>
+===線分を s 個に分割した時の長さの差の期待値===
 線分 [0,1] をランダムに s 分割するとき、得られる線分の長さを短いものから長いものに並べ替えて <math>l_1, l_2, \cdots, l_s</math> と書きましょう。ここで <math>l_1< l_2 < \cdots < l_s </math> また <math>\textstyle \sum^s_{i=1} l_i =1</math> です。
@@ Line 84: / Line 99: @@
 :<math>
-d_1 = l_2 - l_1,\ d_2 = l_3 - l_2,\ \cdots d_{s-2} = l_{s-1} - l_{s}, d_{s-1} = l_s - l_{s-1}
+\begin{align}
+d_1 &= l_2 - l_1,\\
+d_2 &= l_3 - l_2,\\
+&\cdots\\
+d_{s-2} &= l_{s-1} - l_{s-2}\\
+d_{s-1} &= l_s - l_{s-1}
+\end{align}
 </math>
@@ Line 96: / Line 117: @@
 </math>
-ここで全ての線分は等しい仮定の下に置かれていて期待値が等しいことを利用します<ref>Whitworth WA (1934) Choice and Chance ''Steicher'' New York</ref><ref>Pielou (1975) Ecologial Diversity ''Wiley'' New York</ref>。
+ここで、新たに 1 点を追加する過程を考えましょう。ランダムに追加する 1 点は <math>sl_1</math> の確率で（ s + 1 個に増えたときに）最短の線分を作り、<math>(s-1)d_1</math> の確率で 2 番目に短い線分を作り、<math>(s-2)d_2</math> の確率で 3 番目に短い線分を作ります。しかし、どの線分も全て等確率で生じるはずなので、結果として以下が成立します。
 :<math>\textstyle
 E[sl_1] = E[(s-1)d_1] = E[(s-2)d_2] = \cdots = E[d_{s-1}] = \frac{1}{s}
@@ Line 105: / Line 125: @@
 :<math>\textstyle
-E[l_1] = \frac{1}{s^2},\ E[d_1] = \frac{1}{s(s-1)},\ E[d_2] = \frac{1}{s(s-2)},\ \cdots E[d_i] = \frac{1}{s(s-i)},\ \cdots E[d_{s-1}] = \frac{1}{s}
+E[l_1] = \frac{1}{s^2},\ E[d_1] = \frac{1}{s(s-1)},\ E[d_2] = \frac{1}{s(s-2)},\ \cdots
+</math>
+:<math>\textstyle
+E[d_i] = \frac{1}{s(s-i)},\ \cdots \ E[d_{s-1}] = \frac{1}{s}
 </math>
-初めに仮定した ''l'' の形に戻しましょう。
+===線分を s 個に分割してから順位づけした時の期待値===
+線分の差である d<sub>i</sub> の期待値から、初めに仮定した ''l'' の期待値を求めましょう。
+短い方から i 番目の長さは
 :<math>
 \begin{align}
@@ Line 115: / Line 140: @@
 E[l_3] &= \textstyle l_1 + d_1 + d_2 = \frac{1}{s^2} + \frac{1}{s(s-1)} + \frac{1}{s(s-2)}\\
 \cdots \\
-E[l_i] &= \textstyle \frac{1}{s}\sum^{i-1}_{j=0}\frac{1}{s-j}
+E[l_i] &= \textstyle \frac{1}{s}\sum^{i-1}_{j=0}\frac{1}{s-j}\\
+&= \textstyle \frac{1}{s} (\sum^{s}_{j=1}\frac{1}{j} - \sum^{s-i}_{j=1}\frac{1}{j})\\
+&\simeq \textstyle \frac{1}{s} \log\frac{s}{s-i}
 \end{align}
 </math>
-同様に長いほうから順番に並べた場合は i 番目の長さは
+同様に、長いほうから順番に並べた場合は i 番目の長さは
-:<math>\textstyle
+:<math>
-E[l_i] = \frac{1}{s}\sum^{s-i}_{j=0}\frac{1}{s-j}
+\begin{align}
+E[l_i] &= \textstyle\frac{1}{s}\sum^{s-i}_{j=0}\frac{1}{s-j}\\
+&= \textstyle\frac{1}{s}(\sum^{s}_{j=1}\frac{1}{j} - \sum^{i-1}_{j=1}\frac{1}{j})\\
+&\simeq \textstyle\frac{1}{s} \log\frac{s}{i-1}
+\end{align}
 </math>
-以上をまとめます。
-:各線分の長さの期待値 <math>\textstyle \frac{1}{s}</math>
-:一番短い線分の期待値 <math>\textstyle \frac{1}{s^2}</math>
-:一番長い線分の期待値 <math>\textstyle \frac{1}{s}\sum^{s}_{j=1}\frac{1}{j} \sim \frac{1}{s}\log s</math>
-<references/>

Aritalab:Lecture/NetworkBiology/Zipf

Latest revision as of 22:07, 11 August 2011

Contents

[edit] Zipf の法則とランク・サイズ則

[edit] ランダムな区画取り

[edit] ランダムに 2 点をとったとき、 2 点間の距離の分布

[edit] ランダムに 2 点をとる作業を n 回繰り返したとき、r 番目の距離の分布

[edit] ランダムな分割

[edit] 線分を s 個に分割した時の長さの期待値

[edit] 線分を s 個に分割した時の長さの差の期待値

[edit] 線分を s 個に分割してから順位づけした時の期待値

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox