ジャンケンで決着がつくまでの回数（7）

期待値E(n)をもう一度代数的に検討してみよう。

(P(n, 1) + ... + P(n, n-1))E(n) = 1 + P(n, 1)E(n) + ... + P(n, n-1)E(n-1)

の左辺は、

(2ⁿ - 2)/3ⁿE(n)

整理して、

$(2^n - 2)\frac{E(n)}{n!} = \frac{3^{n-1}}{n!} + \frac{1}{(n-1)!}\frac{E(1)}{1!} + ... + \frac{1}{1!}\frac{E(n-1)}{(n-1)!}$

ここで、

$f(x) = \sum_n{\frac{E(n)}{n!}x^n}$

という母関数を考えると、

$f(2x) - (e^x + 1)f(x) = \frac{1}{3}e^{3x} - x - \frac{1}{3}$

となる。
これを解くのは難しそうだが、
とりあえず、
xが大きくなると、e^3/2xが支配的になる。
すなわち、

$E(n) \sim \frac{1}{3}(\frac{3}{2})^n$

となり、nが1増すごとに、約1.5倍になることが分かる。