Aritalab:Lecture/NetworkBiology/Zipf
(→ランダムに 2 点をとる作業を n 回繰り返したとき、r 番目の距離の分布) |
m |
||
Line 12: | Line 12: | ||
===ランダムに 2 点をとったとき、 2 点間の距離の分布=== | ===ランダムに 2 点をとったとき、 2 点間の距離の分布=== | ||
− | 線分 [0,1] 上にランダムにとる点を | + | 線分 [0,1] 上にランダムにとる点を y とします。一般性を失わずに <math>0 \leq y \leq 1/2</math> とします。 y から距離 x と x + dx の間に 2 点目を取る確率を計算します。 |
* 0 または 1 から幅 ''x'' 以内に <math>y</math> をとるとき | * 0 または 1 から幅 ''x'' 以内に <math>y</math> をとるとき | ||
Line 50: | Line 50: | ||
:<math> | :<math> | ||
\begin{align} | \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^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)!} \int^1_0 (1-z^{1/2}) z^{r-1}(1-z)^{n-r} dz \\ | ||
Line 63: | Line 63: | ||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
− | + | E[g_1(x)] &= 1 - n! \cdot \frac{\Gamma(3/2)}{\Gamma((n+1)+ 1/2)} \\ | |
&= 1 - \frac{ 2^{2n+1} n! (n+1)!}{(2n + 2)!}\\ | &= 1 - \frac{ 2^{2n+1} n! (n+1)!}{(2n + 2)!}\\ | ||
\end{align} | \end{align} | ||
Line 70: | Line 70: | ||
:<math> | :<math> | ||
\begin{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} | &= 1 - \frac{2n}{2n+1} | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
+ | |||
+ | ==ランダムな分割== | ||
+ | |||
+ | 線分 [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> です。 | ||
+ | |||
+ | ここで r 番目の線分と r+1 番目の線分の差を <math>d_r</math> と書きます。 | ||
+ | |||
+ | :<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} | ||
+ | </math> | ||
+ | |||
+ | このとき <math>\textstyle l_r = l_1 + \sum^{r-1}_{i=1} d_i </math> です。全ての線分を足し合わせると長さは 1 になります。 | ||
+ | |||
+ | :<math> | ||
+ | \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} | ||
+ | </math> | ||
+ | |||
+ | ここで全ての線分は等しい仮定の下に置かれていて期待値が等しいことを利用します<ref>Whitworth WA (1934) Choice and Chance ''Steicher'' New York</ref><ref>Pielou (1975) Ecologial Diversity ''Wiley'' New York</ref>。 | ||
+ | |||
+ | :<math>\textstyle | ||
+ | E[sl_1] = E[(s-1)d_1] = E[(s-2)d_2] = \cdots = E[d_{s-1}] = \frac{1}{s} | ||
+ | </math> | ||
+ | |||
+ | ここから | ||
+ | |||
+ | :<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} | ||
+ | </math> | ||
+ | |||
+ | 初めに仮定した ''l'' の形に戻しましょう。 | ||
+ | |||
+ | :<math> | ||
+ | \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} | ||
+ | \end{align} | ||
+ | </math> | ||
+ | |||
+ | 同様に長いほうから順番に並べた場合は i 番目の長さは | ||
+ | :<math>\textstyle | ||
+ | E[l_i] = \frac{1}{s}\sum^{s-i}_{j=0}\frac{1}{s-j} | ||
+ | </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/> |
Revision as of 06:35, 21 July 2011
Contents |
Zipf の法則とランク・サイズ則
都市毎の人口や会社の規模、個人の所得を大きさの順に並べて順位 r をつけ、その大きさを とおくと
の形になります(α の値は小さい)。一般には Zipf の法則として知られる関係は、Rank-Size Rule とも呼ばれます。
ランダムな区画取り
ランダムに 2 点をとったとき、 2 点間の距離の分布
線分 [0,1] 上にランダムにとる点を y とします。一般性を失わずに とします。 y から距離 x と x + dx の間に 2 点目を取る確率を計算します。
- 0 または 1 から幅 x 以内に をとるとき
確率 2 x で から x 離れた地点は片側にしかとることができません。2 番目の点が x と x + dx の間に落ちる確率は です。
- 残りの範囲に をとるとき
確率 1 - 2 x で から x 離れた地点を両側にとることができます。2 番目の点が x と x + dx の間に落ちる確率は となります。
結局、2 点間の距離の確率は で与えられます。平均値は 1/3 になります。
ランダムに 2 点をとる作業を n 回繰り返したとき、r 番目の距離の分布
ランダムにとった区間長が より長い確率 p 、短い確率 q はそれぞれ
となります。n 回繰り返したときに、r 番目の区間長が である期待値 は 個が より短く、 個が より長い区間を得ることに相当します。
期待値を計算するのに と変数変換します。 微分すると です。
一番長い区間の期待値
一番短い区間の期待値
ランダムな分割
線分 [0,1] をランダムに s 分割するとき、得られる線分の長さを短いものから長いものに並べ替えて と書きましょう。ここで また です。
ここで r 番目の線分と r+1 番目の線分の差を と書きます。
このとき です。全ての線分を足し合わせると長さは 1 になります。
ここで全ての線分は等しい仮定の下に置かれていて期待値が等しいことを利用します[1][2]。
ここから
初めに仮定した l の形に戻しましょう。
同様に長いほうから順番に並べた場合は i 番目の長さは
以上をまとめます。
- 各線分の長さの期待値
- 一番短い線分の期待値
- 一番長い線分の期待値