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

期待値は再帰的に計算することができます。例えば、N=4、M=2なら、

となりますが、各プロセスを殺すと、0を殺すと全て殺せて、残りは、

1:    0     2:    0  3:    0
       ＼       ／       ／ ＼
         2     1        1     2
             ／
            3

となります。これらのプロセスツリーに対する期待値を計算して平均を取って1を足せば元のツリーに対する期待値が出ます。
これをざっくり組んでみました。ツリーのデータ構造は、そのプロセスに親と子を書いておきます。殺すときは親の子リストから消すだけです。

def create_process(a, i, k, N, M):
    if k < N:
        n = min(M, N - k)
        a[i] = a[i] + tuple(k + l for l in xrange(n))
        for l in xrange(n):
            a[k+l] = (i,)
        create_process(a, i + 1, k + n, N, M)

def travel(a, i = 0):
    yield i
    for k in a[i][1:]:
        for l in travel(a, k):
            yield l

def size(a):
    return sum(1 for i in travel(a))

def kill(a, i, k = 1):
    if i == 0:
        return [ () ]
    else:
        p = a[i][0]     # parent
        if a[p][k] == i:
            b = a[:]
            b[p] = a[p][:k] + a[p][k+1:]
            return b
        else:
            return kill(a, i, k + 1)

def E(a):
    if len(a[0]) == 0:  # all killed
        return 0.0
    else:
        return 1.0 + sum(E(kill(a, k)) for k in travel(a)) / size(a)

def solve(N, M):
    a = [ () for k in xrange(N) ]
    a[0] = (-1,)
    create_process(a, 0, 1, N, M)
    return E(a)

for N in xrange(1, 11):
    print N, solve(N, 2)

これを走らせると、

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

明らかな規則性がありますね。