Aritalab:Lecture/NetworkBiology/Zipf

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

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

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

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

ランダムな区画取り

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

線分 [0,1] 上にランダムにとる点を $y$ とします。一般性を失わずに $0 \leq y \leq 1/2$ とします。 $y$ から距離 x と x + dx の間に 2 点目を取る確率を計算します。

• 0 または 1 から幅 x 以内に $y$ をとるとき

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

• 残りの範囲に $y$ をとるとき

確率 1 - 2 x で $y$ から x 離れた地点を両側にとることができます。2 番目の点が x と x + dx の間に落ちる確率は $(1-2x) \cdot 2 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$

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

ランダムにとった区間長が $w$ より長い確率 p 、短い確率 q はそれぞれ

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

となります。n 回繰り返したときに、r 番目の区間長が $x_r$ である期待値 $g_r(x)$ は $r-1$ 個が $x_r$ より短く、$n - r$ 個が $x$ より長い区間を得ることに相当します。

$\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} \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}$