Aritalab:Lecture/NetworkBiology/Zipf
m (→ランダムに 2 点をとる作業を n 回繰り返したとき、r 番目の距離の分布) |
m (→線分を s 個に分割してから順位づけした時の期待値) |
||
(9 intermediate revisions by one user not shown) | |||
Line 20: | Line 20: | ||
y から x 離れた地点を両側にとれます。2 番目の点が x と x + dx の間に落ちる確率は 2(1-2x) dx です。 | y から x 離れた地点を両側にとれます。2 番目の点が x と x + dx の間に落ちる確率は 2(1-2x) dx です。 | ||
− | 結局、2 | + | 結局、2 点間の距離の確率は以下のようになります。 |
+ | |||
+ | <math>\,f(x) dx = 2 x dx + 2 (1-2x) dx = 2(1-x)dx</math> | ||
+ | |||
+ | 平均値は 1/3 です。 | ||
:<math> | :<math> | ||
Line 36: | Line 40: | ||
</math> | </math> | ||
− | n 回繰り返したときに、r 番目に長い区間が x である確率 <math>g_r(x)</math> は r−1 個が x | + | n 回繰り返したときに、r 番目に長い区間が x である確率 <math>g_r(x)</math> は r − 1 個が x より長く、n − r 個が、より短い区間であることに相当します。 |
:<math> | :<math> | ||
Line 63: | Line 67: | ||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
− | E[g_1(x)] &= 1 - n! \cdot \frac{\Gamma(3 | + | E[g_1(x)] &= 1 - n! \cdot \frac{\Gamma(\frac{3}{2})}{\Gamma(n + \frac{3}{2})} \\ |
− | &= 1 - \frac{ | + | &= 1 - \frac{\sqrt{\pi}}{2} \frac{n!}{\Gamma(n + \frac{3}{2})} |
\end{align} | \end{align} | ||
</math> | </math> | ||
Line 78: | Line 82: | ||
==ランダムな分割== | ==ランダムな分割== | ||
− | ===線分を s | + | ===線分を s 個に分割した時の長さの期待値=== |
+ | まず、線分 [0,1] を 3 個に分割する場合を考えます。ランダムに 2 点を取ったとき、任意に選んだ断片の長さが x である確率を <math>f_3(x)</math> とします。一般性を失わずにこの断片が左端とします。2 点のうち、1 つは x の位置に固定し (2 通り)、残りは (1 − x) の中から選べます。 | ||
+ | : <math>f_3(x) = 2 (1-x)</math> | ||
+ | この値は、ランダムに 2 点を取ったときの二点間の距離に等しくなっていて、長さの期待値は 1/3 です。 | ||
+ | |||
+ | ランダムに s 点を取るときも同様に考えます。s 点のうち 1 つを x の位置に固定し、残りは (1 − 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> です。 | 線分 [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> | :<math> | ||
− | d_1 = l_2 - l_1,\ d_2 = l_3 - l_2,\ \cdots d_{s-2} = l_{s-1} - l_{s} | + | \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> | </math> | ||
Line 96: | Line 117: | ||
</math> | </math> | ||
− | + | ここで、新たに 1 点を追加する過程を考えましょう。ランダムに追加する 1 点は <math>sl_1</math> の確率で( s + 1 個に増えたときに)最短の線分を作り、<math>(s-1)d_1</math> の確率で 2 番目に短い線分を作り、<math>(s-2)d_2</math> の確率で 3 番目に短い線分を作ります。しかし、どの線分も全て等確率で生じるはずなので、結果として以下が成立します。 | |
− | + | ||
:<math>\textstyle | :<math>\textstyle | ||
E[sl_1] = E[(s-1)d_1] = E[(s-2)d_2] = \cdots = E[d_{s-1}] = \frac{1}{s} | 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 | :<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> | </math> | ||
− | + | ===線分を s 個に分割してから順位づけした時の期待値=== | |
+ | 線分の差である d<sub>i</sub> の期待値から、初めに仮定した ''l'' の期待値を求めましょう。 | ||
+ | 短い方から i 番目の長さは | ||
:<math> | :<math> | ||
\begin{align} | \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)}\\ | 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 \\ | \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} | \end{align} | ||
</math> | </math> | ||
− | + | 同様に、長いほうから順番に並べた場合は i 番目の長さは | |
− | :<math>\ | + | :<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> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Latest revision as of 22:07, 11 August 2011
Contents |
[edit] Zipf の法則とランク・サイズ則
都市毎の人口や会社の規模、個人の所得を大きさの順に並べて順位 r をつけ、その大きさを とおくと
の形になります(α の値は小さい)。一般には 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 点間の距離の確率は以下のようになります。
平均値は 1/3 です。
[edit] ランダムに 2 点をとる作業を n 回繰り返したとき、r 番目の距離の分布
ランダムにとった区間長が w より長い確率 p 、短い確率 q はそれぞれ以下のようになります。
n 回繰り返したときに、r 番目に長い区間が x である確率 は r − 1 個が x より長く、n − r 個が、より短い区間であることに相当します。
期待値を計算するのに と変数変換します。 微分すると です。
- 一番長い区間の期待値
- 一番短い区間の期待値
[edit] ランダムな分割
[edit] 線分を s 個に分割した時の長さの期待値
まず、線分 [0,1] を 3 個に分割する場合を考えます。ランダムに 2 点を取ったとき、任意に選んだ断片の長さが x である確率を とします。一般性を失わずにこの断片が左端とします。2 点のうち、1 つは x の位置に固定し (2 通り)、残りは (1 − x) の中から選べます。
この値は、ランダムに 2 点を取ったときの二点間の距離に等しくなっていて、長さの期待値は 1/3 です。
ランダムに s 点を取るときも同様に考えます。s 点のうち 1 つを x の位置に固定し、残りは (1 − x) の中から選びます。s 個に分割するとき、任意に選んだ断片の長さが x になる確率は
期待値は
[edit] 線分を s 個に分割した時の長さの差の期待値
線分 [0,1] をランダムに s 分割するとき、得られる線分の長さを短いものから長いものに並べ替えて と書きましょう。ここで また です。
ここで r 番目の線分と r+1 番目の線分の差を と書きます。
このとき です。全ての線分を足し合わせると長さは 1 になります。
ここで、新たに 1 点を追加する過程を考えましょう。ランダムに追加する 1 点は の確率で( s + 1 個に増えたときに)最短の線分を作り、 の確率で 2 番目に短い線分を作り、 の確率で 3 番目に短い線分を作ります。しかし、どの線分も全て等確率で生じるはずなので、結果として以下が成立します。
ここから
[edit] 線分を s 個に分割してから順位づけした時の期待値
線分の差である di の期待値から、初めに仮定した l の期待値を求めましょう。 短い方から i 番目の長さは
同様に、長いほうから順番に並べた場合は i 番目の長さは