プロセスを全て殺すには何回かかるか（3）

数学

昨日アップする順番間違えた。

前回の結果、プロセスは2つの子プロセスを発生させるとき、

N E
1 1.0
2 1.5
3 2.0
4 2.33333333333
5 2.66666666667
6 3.0
7 3.33333333333
8 3.58333333333
9 3.83333333333
10 4.08333333333

となりました。さらに、

      0
    ／
   1
 ／
2

こんなプロセスツリーのときを計算すると11/6となりました。これはもう明らかですね。プロセスpの階層をrank(p)（上から1、2、3…）と書くと、

E = Σp1/rank(p)

こうですね。上の例だと1+1/2+1/3=11/6です。
数学的にもそんなに難しくないです。数学的帰納法で証明できます。まず、プロセスが0個のときは明らかにE=0です。プロセスが1個以上のときを考えます。そのときのプロセスツリーをTとし、このプロセスツリーよりプロセスの数が少ないときに上の式が成り立つと仮定します。このプロセスツリーからプロセスpkを殺したツリーをT(k)と書くことにします。そうすると、ツリーの期待値E(T)は、Tのプロセス数をnとして、

E(T) = 1 + ΣkE(T(k))/n = 1 + ΣkΣp1/rank(p)/n

と書けます）。Σを入れ替えて、

E(T) = 1 + ΣpΣk1/rank(p)/n

ここで、2つ目Σはkの個数で決まります。これはどう数えればよいでしょう。例えば、プロセスpの階層が3だとすると、プロセスを1個殺したときpがなくなっているのは、まずpを殺したとき、そして、階層2、1にも一つずつあることがわかります。すなわち、

E(T) = 1 + Σp(n - rank(p))/rank(p)/n = 1 + Σp1/rank(p) - Σp1/n = Σp1/rank(p)

となります。
ここでは子プロセスの個数を使っていません。すなわち、子プロセスの数はいくつでも上の式は成り立ちます。
上の式に基づいてコードを書いておきましょう

def E(n, m, k = 0, r = 1):
    if n == k:
        return 0
    else:
        nr = min(1 << (r - 1), n - k)
        return float(nr) / r + E(n, m, k + nr, r + 1)

for n in (10 ** e for e in xrange(1, 8)):
    print n, E(n, 2)

これを動かすと、

10 4.08333333333
100 19.1523809524
1000 116.353968254
10000 826.702752803
100000 6450.25093207
1000000 53142.4372238
10000000 450330.887087

素数の個数、π(n)に似ていますね。なるほど。